图算法

图的存储：

邻接矩阵和邻接表

1
2
3
4
List<Integer> graph[]=new List[numCourses];
for(int i=0;i<numCourses;i++){
	graph[i]=new LinkedList<>();
}

首先，图的遍历和树的遍历的区别

图存在环，从一个节点遍历可能会走到自身；而树从一个节点出发，一定会走到叶子节点，所以遍历图需要辅助数组visited来记录是否被访问过。【所以，如果图一定不存在环，就可以不使用visited数组，】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// 记录被遍历过的节点
boolean[] visited;
// 记录从起点到当前节点的路径
boolean[] onPath;

/* 图遍历框架 */
void traverse(Graph graph, int s，boolean[] visited，boolean[] onPath) {
    if (visited[s]) return;
    //----前序遍历位置----
    // 经过节点 s，标记为已遍历
    visited[s] = true;
    // 做选择：标记节点 s 在路径上
    onPath[s] = true;
    //--------------------
    // 遍历所有邻接结点
    for (int neighbor : graph.neighbors(s)) {
        traverse(graph, neighbor);
    }
    //----后序遍历位置-------
    // 撤销选择：节点 s 离开路径
    onPath[s] = false;
    //----------------------
}

图遍历与回溯算法的比较 【这个还挺难的】

回溯算法做选择是在for循环里面，而图遍历是在for循环外面，两者有何区别

image-20221014111359709

image-20221121114811919 image-20221121114759456

image-20221121115220433

环检测

课程表

首先，需要将题目的输入转化成图。

  • 图有两种存储方式，邻接矩阵和邻接表，比较常用邻接表

    1
    List<Integer> []graph;

  • 图遍历算法，遍历过程中记录路径，看路径是否存在环

方法1：使用dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
    boolean isCircle;//是否存在环
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 判断一个图是否存在环
        // 初始化图
        int n=prerequisites.length;
        List<Integer> graph[]=new LinkedList[numCourses];
        for(int i=0;i<numCourses;i++){
            graph[i]=new LinkedList<Integer>();
        }
        for(int i=0;i<n;i++){
            graph[prerequisites[i][1]].add(prerequisites[i][0]);
        }
        boolean visited[]=new boolean[numCourses];
        for(int i=0;i<numCourses;i++){
            if(isCircle){
                break;
            }
            if(!visited[i]){
                boolean path[]=new boolean[numCourses];
                traverse(graph,visited,path,i);
            }
        }
        return !isCircle;
    }
    void traverse(List<Integer> graph[],boolean visited[],boolean[] path,int i){
        if(isCircle){ //图已经存在环，就不需要遍历
            return;
        }
        if(path[i]){ //存在环
            isCircle=true;
            return;
        }
        if(visited[i]){  //该结点已访问过
            return;
        }
        visited[i]=true;//访问该结点
        path[i]=true;
        // 遍历所有的邻接结点
        for(int j=0;j<graph[i].size();j++){
            traverse(graph,visited,path,graph[i].get(j));
        }
        path[i]=false; //回溯
    }
}

方法2：使用bfs

bfs记录每个结点的入度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
public boolean canFinish(int numCourses, int[][] prerequisites) {
    // 建图，有向边代表「被依赖」关系
    List<Integer>[] graph = buildGraph(numCourses, prerequisites);
    // 构建入度数组
    int[] indegree = new int[numCourses];
    for (int[] edge : prerequisites) {
        int from = edge[1], to = edge[0];
        // 节点 to 的入度加一
        indegree[to]++;
    }

    // 根据入度初始化队列中的节点
    Queue<Integer> q = new LinkedList<>();
    for (int i = 0; i < numCourses; i++) {
        if (indegree[i] == 0) {
            // 节点 i 没有入度，即没有依赖的节点
            // 可以作为拓扑排序的起点，加入队列
            q.offer(i);
        }
    }

    // 记录遍历的节点个数
    int count = 0;
    // 开始执行 BFS 循环
    while (!q.isEmpty()) {
        // 弹出节点 cur
        int cur = q.poll();
        count++;
        // 并将它指向的节点的入度减一
        for (int next : graph[cur]) {
            indegree[next]--;
            if (indegree[next] == 0) {
                // 如果入度变为 0，说明 next 依赖的节点都已被遍历
                q.offer(next);
            }
        }
    }

    // 如果所有节点都被遍历过，说明不成环
    return count == numCourses;
}

// 建图函数
List<Integer>[] buildGraph(int n, int[][] edges) {
    // 略
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        // 判断一个图是否存在环
        // 初始化图
        int n=prerequisites.length;
        List<Integer> graph[]=new LinkedList[numCourses];
        int indegree[]=new int[numCourses];  // 记录每个结点的入度数
        for(int i=0;i<numCourses;i++){
            graph[i]=new LinkedList<Integer>();
        }
        for(int i=0;i<n;i++){
            graph[prerequisites[i][1]].add(prerequisites[i][0]);
            indegree[prerequisites[i][0]]++;
        }
        Queue<Integer> q=new LinkedList<Integer>();
        // 将入度为0的结点放入队列
        for(int i=0;i<numCourses;i++){
            if(indegree[i]==0){
                q.offer(i);
            }
        }
        int count=0; //记录访问的结点数
        while(!q.isEmpty()){
            //出队
            int cur=q.poll();
            count++;
            // cur结点指向的所有结点入度减一
            for(int i=0;i<graph[cur].size();i++){
                int temp=graph[cur].get(i);
                indegree[temp]--;
                if(indegree[temp]==0){
                    q.offer(temp);
                }
            }
        }
        return count==numCourses;
    }     
}

拓扑排序

后序遍历的反转就是拓扑序列

image-20221019112437232

方法1：dfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
    boolean isCircle;
    List<Integer> res;
    int index=0;
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 后序遍历的反转就是拓扑序列
        // 初始化图
        List<Integer> graph[]=new LinkedList[numCourses];
        for(int i=0;i<numCourses;i++){
            graph[i]=new LinkedList<Integer>();
        }
        int n=prerequisites.length;
        for(int i=0;i<n;i++){
            graph[prerequisites[i][1]].add(prerequisites[i][0]);
        }
        res=new ArrayList<>();
        boolean visited[]=new boolean[numCourses];
        for(int i=0;i<numCourses;i++){
            if(isCircle){
                break;
            }
            if(!visited[i]){
                boolean[] path=new boolean[numCourses];
                traverse(graph,visited,path,i);
            }
        }
        if(isCircle){
            return new int[0];
        }else{
            Collections.reverse(res);
            int ans[]=new int[numCourses];
            for(int i=0;i<numCourses;i++){
                ans[i]=res.get(i);
            }
            return ans;
        }
    }

    void traverse(List<Integer> graph[],boolean visited[],boolean path[],int i){
        if(isCircle){
            return;
        }
        if(path[i]){
            isCircle=true;
            return;
        }
        if(visited[i]){
            return;
        }
        // 访问该结点
        path[i]=true;
        visited[i]=true;
        // 遍历该邻接结点
        for(int j=0;j<graph[i].size();j++){
            traverse(graph,visited,path,graph[i].get(j));
        }
        res.add(i);
        path[i]=false; //回溯
    }
}

方法2：bfs

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        // 后序遍历的反转就是拓扑序列  或者通过bfs
        // 初始化图
        int indegree[]=new int[numCourses]; // 记录每个结点的入度
        List<Integer> graph[]=new LinkedList[numCourses];
        for(int i=0;i<numCourses;i++){
            graph[i]=new LinkedList<Integer>();
        }
        int n=prerequisites.length;
        for(int i=0;i<n;i++){
            graph[prerequisites[i][1]].add(prerequisites[i][0]);
            indegree[prerequisites[i][0]]++;
        }
        int res[]=new int[numCourses];
        int index=0;
        Queue<Integer> q=new LinkedList<Integer>();
        // 入度为0的进队
        for(int i=0;i<numCourses;i++){
            if(indegree[i]==0){
                q.offer(i);
            }
        }
        while(!q.isEmpty()){
            int cur=q.poll();
            res[index++]=cur;
            for(int i=0;i<graph[cur].size();i++){
                int temp=graph[cur].get(i);
                indegree[temp]--;
                if(indegree[temp]==0){
                    q.offer(temp);
                }
            }
        }
        if(index==numCourses){
            return res;
        }else{
            return new int[0];
        }
    }
}

二分图判定

二分图作用：

二分图可以高效地存储数据

比如存储演员和电影之间的关系，一个演员可以参演多部电影，一个电影由多个演员参演

通过HashMap存储电影和演员之间的映射，可以快速查询到一部电影由哪些演员参演

拿如果需要快速查询一个演员参演哪些电影，我们需要通过存储另外一个HashMap,这样，需要两个哈希表分别存储「每个演员到电影列表」的映射和「每部电影到演员列表」的映射。但如果用「图」结构存储，将电影和参演的演员连接，很自然地就成为了一幅二分图

image-20221122103522287

思路：遍历一遍图，一边遍历，一边染色，看看能不能用两种颜色给所有结点染色，且相邻结点颜色不同。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
boolean ok=true; //判断是否是二分图
// dfs
void traverse(Graph graph, boolean[] visited, boolean color[],int v) {
    if(!ok){ //已经不是二分图了，无需在遍历了
        return;
    }
    visited[v] = true;
    // 遍历节点 v 的所有相邻节点 neighbor
    for (int neighbor : graph.neighbors(v)) {
        if (!visited[neighbor]) {
            // 相邻节点 neighbor 没有被访问过
            // 那么应该给节点 neighbor 涂上和节点 v 不同的颜色
            color[neighbor]=!color[v];
            traverse(graph, visited, color,neighbor);
        } else {
            // 相邻节点 neighbor 已经被访问过
            // 那么应该比较节点 neighbor 和节点 v 的颜色
            // 若相同，则此图不是二分图
            if(color[neighbor]==color[v]){
                ok=false;
                return;
            }
        }
    }
}
// bfs 也可以
void traverse(Graph graph, boolean[] visited, boolean color[],int start) {
  	Queue q;
    q.offer(start);
    visited[start]=true;
    while(!q.isEmpty()){
        int v=q.poll();
        // 遍历邻接结点
        for (int w : graph[v]) {
            if (!visited[w]) {  // 相邻节点 w 没有被访问过
                // 那么应该给节点 w 涂上和节点 v 不同的颜色
                color[w] = !color[v];
                // 标记 w 节点，并放入队列
                visited[w] = true;
                q.offer(w);
            } else {
                // 相邻节点 w 已经被访问过
                // 根据 v 和 w 的颜色判断是否是二分图
                if (color[w] == color[v]) {
                    // 若相同，则此图不是二分图
                    ok = false;
                    return;
                }
            }
        }
    }
}

判断二分图

可能的二分法

并查集Union-Find算法

使用森林（若干棵树）来表示图的连通性。 树的每个结点有一个指针都指向其父结点，若为根结点则指向自己。

image-20221123103024994

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class UF {
    // 记录连通分量
    private int count;
    // 节点 x 的父节点是 parent[x]
    private int[] parent;

    /* 构造函数，n 为图的节点总数 */
    public UF(int n) {
        // 一开始互不连通
        this.count = n;
        // 父节点指针初始指向自己
        parent = new int[n];
        for (int i = 0; i < n; i++)
            parent[i] = i;
    }

    public void union(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        if (rootP == rootQ)
            return;
        // 将两棵树合并为一棵
        parent[rootP] = rootQ;
        // parent[rootQ] = rootP 也一样
        count--; // 两个分量合二为一
    }
    
    public boolean connected(int p, int q) {
        int rootP = find(p);
        int rootQ = find(q);
        return rootP == rootQ;
	}

    /* 返回某个节点 x 的根节点 */
    private int find(int x) {
        // 根节点的 parent[x] == x
        while (parent[x] != x)
            x = parent[x];
        return x;
    }

    /* 返回当前的连通分量个数 */
    public int count() { 
        return count;
    }
}

时间复杂度取决于find()方法，也就是树的高度，最坏情况是一个不平衡树，时间复杂度为O(n)

优化：通过路径压缩，在O(1)时间找到某个结点的根节点

1
2
3
4
5
6
7
// 路径压缩的 find 方法
public int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

被围绕的区域

方法1：dfs

image-20221123113436944

方法2：Union-Find算法

image-20221124094800649

与dummy相连的’O’不需要被替换成’X’

等式方程的可满足性

让元素分门别类，建立连通关系