算法（十三） 图

建图的几种方式 邻接矩阵、邻接表、链式前向星

// 点的最大数量
	public static int MAXN = 11;

	// 边的最大数量
	// 只有链式前向星方式建图需要这个数量
	// 注意如果无向图的最大数量是m条边，数量要准备m*2
	// 因为一条无向边要加两条有向边
	public static int MAXM = 21;

	// 邻接矩阵方式建图
	public static int[][] graph1 = new int[MAXN][MAXN];

	// 邻接表方式建图
	// public static ArrayList<ArrayList<Integer>> graph2 = new ArrayList<>();
	public static ArrayList<ArrayList<int[]>> graph2 = new ArrayList<>();

	// 链式前向星方式建图
	public static int[] head = new int[MAXN];

	public static int[] next = new int[MAXM];

	public static int[] to = new int[MAXM];

	// 如果边有权重，那么需要这个数组
	public static int[] weight = new int[MAXM];

	public static int cnt;

	public static void build(int n) {
		// 邻接矩阵清空
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				graph1[i][j] = 0;
			}
		}
		// 邻接表清空和准备
		graph2.clear();
		// 下标需要支持1~n，所以加入n+1个列表，0下标准备但不用
		for (int i = 0; i <= n; i++) {
			graph2.add(new ArrayList<>());
		}
		// 链式前向星清空
		cnt = 1;
		Arrays.fill(head, 1, n + 1, 0);
	}

	// 链式前向星加边
	public static void addEdge(int u, int v, int w) {
		// u -> v , 边权重是w
		next[cnt] = head[u];
		to[cnt] = v;
		weight[cnt] = w;
		head[u] = cnt++;
	}

	// 三种方式建立有向图带权图
	public static void directGraph(int[][] edges) {
		// 邻接矩阵建图
		for (int[] edge : edges) {
			graph1[edge[0]][edge[1]] = edge[2];
		}
		// 邻接表建图
		for (int[] edge : edges) {
			// graph2.get(edge[0]).add(edge[1]);
			graph2.get(edge[0]).add(new int[] { edge[1], edge[2] });
		}
		// 链式前向星建图
		for (int[] edge : edges) {
			addEdge(edge[0], edge[1], edge[2]);
		}
	}

	// 三种方式建立无向图带权图
	public static void undirectGraph(int[][] edges) {
		// 邻接矩阵建图
		for (int[] edge : edges) {
			graph1[edge[0]][edge[1]] = edge[2];
			graph1[edge[1]][edge[0]] = edge[2];
		}
		// 邻接表建图
		for (int[] edge : edges) {
			// graph2.get(edge[0]).add(edge[1]);
			// graph2.get(edge[1]).add(edge[0]);
			graph2.get(edge[0]).add(new int[] { edge[1], edge[2] });
			graph2.get(edge[1]).add(new int[] { edge[0], edge[2] });
		}
		// 链式前向星建图
		for (int[] edge : edges) {
			addEdge(edge[0], edge[1], edge[2]);
			addEdge(edge[1], edge[0], edge[2]);
		}
	}

	public static void traversal(int n) {
		System.out.println("邻接矩阵遍历 :");
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				System.out.print(graph1[i][j] + " ");
			}
			System.out.println();
		}
		System.out.println("邻接表遍历 :");
		for (int i = 1; i <= n; i++) {
			System.out.print(i + "(邻居、边权) : ");
			for (int[] edge : graph2.get(i)) {
				System.out.print("(" + edge[0] + "," + edge[1] + ") ");
			}
			System.out.println();
		}
		System.out.println("链式前向星 :");
		for (int i = 1; i <= n; i++) {
			System.out.print(i + "(邻居、边权) : ");
			// 注意这个for循环，链式前向星的方式遍历
			for (int ei = head[i]; ei > 0; ei = next[ei]) {
				System.out.print("(" + to[ei] + "," + weight[ei] + ") ");
			}
			System.out.println();
		}
	}

课程表二（拓扑排序）

leetcode 210

思路：判断入度，每次找到入度为0的点，加入队列，然后遍历这个点的所有边，将边指向的点的入度减1，如果减1后为0，则加入队列。最后判断加入队列的数量是否等于n，如果等于n，则说明有解，否则无解。排序结果就是这个队列。

//边的编号
public static int cnt;

public static void add(int u, int v,int[] head,int[] next,int[] to,int[] weight) {
    //加边逻辑
    next[cnt] = head[u];
    to[cnt] = v;
    head[u] = cnt++;
    //入度加一
    weight[v]++;
}

public static int[] findOrder(int numCourses, int[][] prerequisites) {
    cnt = 1;
    int n = numCourses;
    int m = prerequisites.length;
    int[] head = new int[n];
    int[] next = new int[m+1];
    int[] to = new int[m+1];
    int[] weight = new int[n];


    for(int i=0;i<m;i++){
        add(prerequisites[i][1],prerequisites[i][0],head,next,to,weight);
    }

    int[] queue = new int[n];
    int l = 0;
    int r =0;
    //遍历得到所有0入度的
    for(int i =0;i<n;i++){
        if(weight[i] == 0){
            queue[r++] = i;
        }
    }
    int cnt =0;
    //开始消除所有0入度
    while(l<r){
        int i = queue[l++];
        cnt++;
        for(int ie = head[i];ie>0;ie = next[ie]){
            int toi = to[ie];
            if(--weight[toi] == 0){
                queue[r++] = toi;
            }
        }
    }
    return cnt == n ? queue : new int[0];
}

火星词典

leetcode LCR114

思路：依次比较相邻的两个字符串，从字符串开头依次比较两个的字符。直到遇到不同的字符，那么就说明就是因为这个位置上的字符让前面的字符排在前面。于是增加一条从前面的字符指向后面的字符的边。这样得到一个图之后，就可以进行拓扑排序了。拓扑排序的结果就是字典序.但返回答案之前要判断得到的字典序里面的字符个数是否等于出现的字符个数，少了说明存在环，返回空字符串。

class Solution {
    public static int cnt;

    public static void add(int u,int v,int[] head,int[] next,int[] to,int[] in){
        next[cnt] = head[u];
        to[cnt] = v;
        head[u] = cnt++;
        in[v]++;
    }

    public String alienOrder(String[] words) {
        cnt = 1;
        int n = words.length;
        int[] cnt = new int[26];
        Arrays.fill(cnt,-1);
        for(int i=0;i<n;i++){
            String s = words[i];
            for(int j=0;j<s.length();j++){
                if(cnt[s.charAt(j)-'a'] == -1){
                    cnt[s.charAt(j)-'a'] = 0;
                }
            }
        }
        int[] head = new int[26];
        int[] next = new int[26*26+10];
        int[] to = new int[26*26+10];
        //开始遍历字符串
        for(int i=0,j;i<n-1;i++){
            String cur = words[i];
            String curNext = words[i+1];
            int len = Math.min(cur.length(),curNext.length());
            j=0;
            for(;j<len;j++){
                if(cur.charAt(j)!=curNext.charAt(j)){
                    //添加边
                    add(cur.charAt(j) - 'a',curNext.charAt(j)-'a',head,next,to,cnt);
                    break;
                }
            }
            if( j<cur.length() && j == curNext.length()){
                return "";
            }
        }
        //开始拓扑排序
        //有多少个字符
        int kinds = 0;
        int[] queue = new int[26];
        int l =0;
        int r = 0;
        
        //找出初始入度为0的点
        for(int i=0;i<26;i++){
            if(cnt[i] != -1){
                kinds++;
            }
            if(cnt[i] == 0){
                queue[r++] = i;
            }
        }
        
        StringBuilder sb = new StringBuilder();
        while(l<r){
            int temp = queue[l++];
            char ansChar = (char)('a' + temp);
            kinds --;
            sb.append(ansChar);
            for(int ie = head[temp];ie>0;ie = next[ie]){
                if(--cnt[to[ie]] == 0){
                    queue[r++] = to[ie];
                }
            }
        }
        
        return kinds == 0 ? sb.toString(): "";
    }
}

最大食物链计数

思路：拓扑排序，只不过每次出队时的节点要把自己的信息告诉自己的邻居节点。(其实这道题也能用dfs,而且更简单)

public class Code01_FoodLines {

	public static int MAXN = 5001;

	public static int MAXM = 500001;

	public static int MOD = 80112002;

	// 链式前向星建图
	public static int[] head = new int[MAXN];

	public static int[] next = new int[MAXM];

	public static int[] to = new int[MAXM];

	public static int cnt;

	// 拓扑排序需要的队列
	public static int[] queue = new int[MAXN];

	// 拓扑排序需要的入度表
	public static int[] indegree = new int[MAXN];

	// 拓扑排序需要的推送信息
	public static int[] lines = new int[MAXN];

	public static int n, m;

	public static void build(int n) {
		cnt = 1;
		Arrays.fill(indegree, 0, n + 1, 0);
		Arrays.fill(lines, 0, n + 1, 0);
		Arrays.fill(head, 0, n + 1, 0);
	}

	public static void addEdge(int u, int v) {
		next[cnt] = head[u];
		to[cnt] = v;
		head[u] = cnt++;
	}

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StreamTokenizer in = new StreamTokenizer(br);
		PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
		while (in.nextToken() != StreamTokenizer.TT_EOF) {
			n = (int) in.nval;
			in.nextToken();
			m = (int) in.nval;
			build(n);
			for (int i = 0, u, v; i < m; i++) {
				in.nextToken();
				u = (int) in.nval;
				in.nextToken();
				v = (int) in.nval;
				addEdge(u, v);
				indegree[v]++;
			}
			out.println(ways());
		}
		out.flush();
		out.close();
		br.close();
	}

	public static int ways() {
		int l = 0;
		int r = 0;
		for (int i = 1; i <= n; i++) {
			if (indegree[i] == 0) {
				queue[r++] = i;
				lines[i] = 1;
			}
		}
		int ans = 0;
		while (l < r) {
			int u = queue[l++];
			if (head[u] == 0) {
				// 当前的u节点不再有后续邻居了
				ans = (ans + lines[u]) % MOD;
			} else {
				for (int ei = head[u], v; ei > 0; ei = next[ei]) {
					// u -> v
					v = to[ei];
					lines[v] = (lines[v] + lines[u]) % MOD;
					if (--indegree[v] == 0) {
						queue[r++] = v;
					}
				}
			}
		}
		return ans;
	}

}

喧闹与富有

leetcode 851

思路：拓扑排序，但出队的时候把自己的答案推送到下一个节点即可。

class Solution {
    public static int cnt;

    public static void add(int u,int v,int[] head,int[] next,int[] to,int[] in){
        next[cnt] = head[u];
        to[cnt] = v;
        head[u] = cnt++;
        in[v]++;
    }


    public int[] loudAndRich(int[][] richer, int[] quiet) {
        cnt=1;
        int n = quiet.length;
        int m = richer.length;
        int[] head = new int[n];
        int[] next = new int[m+1];
        int[] to = new int[m+1];
        int[] in = new int[n];
        int[] ans = new int[n];
        for(int i=0;i<n;i++){
            ans[i] = i;
        }
        for(int i=0;i<m;i++){
            add(richer[i][0],richer[i][1],head,next,to,in);
        }
        int[] queue = new int[n];
        int l=0;
        int r =0;
        for(int i =0;i<n;i++){
            if(in[i] == 0){
                queue[r++] = i;
            }
        }
        while(l<r){
            int pos = queue[l++];
            for(int ie = head[pos];ie>0;ie = next[ie]){
                int nextP = to[ie];
                // 如果我的答案更好，推送给你进行更新，之后我就可以出队了
                if(quiet[ans[pos]] < quiet[ans[nextP]]){
                    ans[nextP] = ans[pos];
                }
                if(--in[nextP] == 0){
                    queue[r++] = nextP;
                }
            }
        }
        return ans;
    }
}

以上就是图论基本内容，其实就是建图加拓扑排序。或者有简单的bfs或者dfs。 至于更复杂的图论，以后再学吧。