图算法总结
2020-05-28 19:01:43 # leetcode # 算法 # 总结 # graph

图的基本概念

基本概念

  • 顶点
  • 顶点的度
  • 边
  • 相邻
  • 环
  • 完全图: 所有顶都相邻
  • 二分图: 对于一个图G, V(G)=X∪Y, X∩Y=∅, X中, Y 中任两顶不相邻
  • 路径
  • 圈

图的表示方式

两种，紧接矩阵和邻接表，如下。

邻接矩阵

邻接表

图的相关问题

其实对于很多非图的问题，也是可以把其看做图的，使用图遍历的方式其进行遍历。例如 LeetCode 138. Copy List with Random Pointer，以图遍历的方式遍历链表；又或者是jump game III，将数组用图遍历的方式展现出来。

图的搜索

BFS

用Queue来遍历吧，先写个样例，以邻接表为例：

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
/**
 * 模拟一下，假设给出所有的边，然后重新construct一个图，进行bfs，例如[2,3]就表示2和3之间存在一条边。

 注意！！！ 这里的BFS是考虑连通图的情况下，如果是非连通图，则在while循环外面再套一层for循环。
*/

public void bfs (int[][] edges, int n) {
    // 将边构建成邻接表，用arrayList数组存储
    ArrayList<Integer>[] graph = new ArrayList[n + 1];
    for (int i = 1; i < n + 1; i++) {
        graph[i] = new ArrayList();
    }
    for (int[] edge : edges) {
        graph[edge[0]].add(edge[1]);
        graph[edge[1]].add(edge[0]);
    }

    // BFS遍历
    boolean[] visited = new boolean[n + 1];
    Queue<Integer> queue = new LinkedList();
    queue.add(1);
    isVisited[1] = true; // 将初始设为已经遍历

    while (!queue.isEmpty()) {
        int node = queue.pop();
        for (int i = 0; i < graph[node].size(); i++) {
            if (!isVisited[graph[node].get(i)]) {
                doSomething();
                isVisited[graph[node].get(i)] = true;
                queue.offer(graph[node.get[i]]);
            }
        }
    }

    return;
}

DFS

一般情况下是递归调用DFS较多。而且需要注意的是！！！

Attention: DFS遍历时也要注意preorder还是postorder遍历（有向图的情况下要注意），前者是先遍历当前节点，再去遍历neighbor；后者是先遍历neighbor，再遍历自身。为什么无向图不需要考虑postorder的可能呢？因为无向图都是双向的，如果一个无向图存在环，那么postorder就会引起无限循环，所以对于无向图，都是preorder。

那么对于有向图的postorder遍历有什么区别呢？如果都是在遍历完neighbor以后才将其置为visited的话，那么一旦存在一个有向环，就会无限循环的，和postorder一个道理，跟无向图没有postorder遍历一个道理。因此，我们就需要设置三种状态，unvisited，visiting和visited，当遇到unvisited的时候，我们继续DFS；发现visiting节点，则说明存在环；发现visited节点，则返回，因为已经遍历过了。

下面遍历方式都是对于无向图，有向图的遍历参考：LeetCode 207，最经典的就是拓扑排序。

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
/**
 *这里用二维数组的邻接表来表示整个图，vertex即为顶点id，和数组的顺序一致，从0开始。
*/
public void testDFS(int[][] graph){
        boolean[] isVisited = new int[graph.length];
        Arrays.fill(isVisited, false);

        // 这里有可能是非连通图，对于不同的节点都要尝试。
        for (int i = 0; i < graph.length; i++) {
            if (isVisited[i] == false) {
                isVisited[i] = true;
                dfs(graph, i, isVisited);
            }
        }
}

private void dfs(int[][] graph, int vertex, boolean isVisited) {
    for (int i = 0; i < graph[i].length; i++) {
        // 如果邻居未被访问，则遍历邻居节点
        if (isVisited[graph[vertex][i]] == false) {
            isVisited[graph[vertex][i]] = true;
            dfs(graph, graph[vertex][i], isVisited);
        } else if (isVisited[graph[vertex][i]] == true) {
            // 遍历到一条路径的终点了，做点啥或者直接返回？
            doSomething();
        }
    }
}

二分图

二分图的问题本质上是相当于染色问题，有点像红黑树的感觉。如果能够顺利将整个图染成2种不同颜色，则是二分图，否则不是。实现可以用BFS或DFS均可，下面是三个例题链接。

  1. LeetCode-785-Is-Graph-Bipartite
  2. LeetCode 886. Possible Bipartition
  3. LeetCode-1042-Flower-Planting-With-No-Adjacent

深拷贝图

  1. LeetCode 138. Copy List with Random Pointer
  2. LeetCode 133. Clone Graph

拓扑排序

判断环

最小生成树

最小生成树是无向图里的概念！！！

Kruskal Algorithm

其核心思想在于按边查找。

  1. 首先将所有的边从小到大进行排序；
  2. 依次从前到后遍历所有的边，如果该条边不会使得已有的边形成“环”，加入这条边到MST里；否则，跳过；
  3. 直到有n-1条边被选出或者无边可选， MST生成。

O(T) = O(ElogE)

O(S) = O(V)

例题：LeetCode 1584

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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
class Solution {
    
    class UF {
        int size;
        int[] parent;
        int[] weight;
        public UF(int n) {
            size = n;
            parent = new int[n];
            weight = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                weight[i] = 1;
            }
        }
        
        public int find(int x) {
            if (x == parent[x]) {
                return x;
            }
            parent[x] = find(parent[x]);
            return parent[x];
        }
        
        public void union(int x, int y) {
            int rootX = find(x), rootY = find(y);
            if (rootX == rootY) {
                return;
            }
            
            if (weight[rootX] <= weight[rootY]) {
                parent[rootX] = rootY;
                weight[rootY] += weight[rootX];
            } else {
                parent[rootY] = rootX;
                weight[rootX] += weight[rootY];
            }
            
            size--;
        }
    }
    
    class Edge{
        int x, y, l;
        public Edge(int _x, int _y, int _l){
            x = _x;
            y = _y;
            l = _l;
        }
    }
    
    public int minCostConnectPoints(int[][] points) {
        int n = points.length;
        PriorityQueue<Edge> pq = new PriorityQueue<>((a, b) -> a.l - b.l);
        
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                Edge e = new Edge(i, j, Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]));
                pq.add(e);
            }
        }
        
        UF uf = new UF(n);
        int cnt = 0, res = 0;
        while (cnt < n - 1) {
            Edge e = pq.poll();
            if (uf.find(e.x) == uf.find(e.y)) {
                continue;
            }
            
            uf.union(e.x, e.y);
            res += e.l;
            cnt++;
        }
        
        return res;
    }
}

Prim Algorithm

按顶点来进行查找。

  1. 将顶点分为两个set，visited和unvisited；
  2. visited中初始化放入一个顶点，剩下的则放入unvisited中；
  3. 每次找到一条从visited到unvisited的最短的边，将其加入MST，并将该顶点加入MST（该顶点一定在unvisited中，因为边是从visited到unvisited的）；
  4. 重复3，知道全部顶点已经加入visited或者无边可加。

单源最短路径

Dijkstra

LeetCode 

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
class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        // 普通版本的dijkstra
        int[] dists = new int[n + 1];
        Arrays.fill(dists, Integer.MAX_VALUE);
        Map<Integer, List<int[]>> graph = new HashMap<>();
        dists[k] = 0;
        
        for (int[] edge : times) {
            graph.putIfAbsent(edge[0], new ArrayList<int[]>());
            graph.get(edge[0]).add(new int[]{edge[1], edge[2]});
        }
        
        // 定义一个visited数组表示该点是否有被遍历过
        boolean[] visited = new boolean[n + 1];
        // visited[k] = true;
        
        while (true) {
            // 遍历去找当前距离node k最近的点为candidate
            int candidateId = -1, minD = Integer.MAX_VALUE;
            for (int i = 1; i <= n; i++) {
                if (!visited[i] && dists[i] < minD) {
                    candidateId = i;
                    minD = dists[i];
                }
            }

            // 如果不存在，则跳出
            if (candidateId < 0) break;

            visited[candidateId] = true;

            // 这里，注意要先判断一下图里有没有candidate，因为有的点只有入度没有出度。
            if (graph.containsKey(candidateId)) {
                for (int[] nei : graph.get(candidateId)) {
                    dists[nei[0]] = Math.min(dists[candidateId] + nei[1], dists[nei[0]]);
                }
            }
        }
        
        int res = 0;
        for (int i = 1; i <= n; i++) {
            if (dists[i] == Integer.MAX_VALUE) {
                return -1;
            }
            res = Math.max(res, dists[i]);
        }
        
        return res;
    }
}

堆优化版Dijkstra

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

class Solution {
    public int networkDelayTime(int[][] times, int n, int k) {
        // 堆优化版Dijkstra算法
        Map<Integer, List<int[]>> graph = new HashMap<>();
        for (int[] edge : times) {
            graph.putIfAbsent(edge[0], new ArrayList<>());
            graph.get(edge[0]).add(new int[]{edge[1], edge[2]});
        }
        
        // 初始化距离
        int[] dist = new int[n + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[k] = 0;
        boolean[] seen = new boolean[n + 1];
        
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> (a[1] - b[1]));
        pq.add(new int[]{k, 0});
        
        while (!pq.isEmpty()) {
            int[] cand = pq.poll();
            int candidate = cand[0], minD = cand[1];
            
            // 根据candidate更新dist数组
            if (seen[candidate]) {
                continue;
            }
            dist[candidate] = minD;
            seen[candidate] = true;
            if (graph.containsKey(candidate)) {
                for (int[] nei : graph.get(candidate)) {
                    // 这里加判断是为了减少已经找到最短路的顶点，减少heap处理的数据量大小
                    if (!seen[nei[0]])
                        pq.offer(new int[]{nei[0], nei[1] + minD});
                }
            }
        }
        
        int res = 0;
        for (int i = 1; i <= n; i++) {
            if (dist[i] == Integer.MAX_VALUE) {
                return -1;
            }
            res = Math.max(dist[i], res);
        }
        return res;
    }
}

最短路径问题

欧拉路径

最大流

Prev
2020-05-28 19:01:43 # leetcode # 算法 # 总结 # graph
Next