图算法总结
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

拓扑排序

判断环

最小生成树

单源最短路径

最短路径问题

欧拉路径

最大流

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