前言#

最近面试突然被问到数据结构学得怎样，我说还行，大学数据结构99分（学校不好，考得简单），结果直接来一道 判断图中是否存在环 把我整懵圈，工作多年都没接触过，以前做过的算法题里，刚好图这个数据结构没做过一道题，完全忘了里面的结构，什么邻接表全忘了，把我尴尬死，后面都不敢说话了

邻接表#

先简单回顾一下什么是邻接表，其实就是用来记录顶点旁边有谁的一个二维结构

例如无向图中，A 的旁边有 B，B 的旁边有 A

1
graph = {
2
    'A': ['B'],
3
    'B': ['A']
4
}

有向图，A 的旁边有 B，B 的旁边没有顶点

1
directed_graph = {
2
    'A': ['B'],
3
    'B': []
4
}

同理，无向和有向加权图，只是多了权重

1
weighted_graph = {
2
    'A': [('B', 5)],
3
    'B': [('A', 5)]
4
}
5

6
weighted_directed_graph = {
7
    'A': [('B', 3)],
8
    'B': []
9
}

数据结构#

以无向图为例

1
class Graph {
2
    /** 顶点数 */
3
    private int V;
4
    /** 邻接表 */
5
    private List<List<Integer>> adj;
6

7
    public Graph(int v) {
8
        V = v;
9
        adj = new ArrayList<>(v);
10
        for (int i = 0; i < v; i++) {
11
            adj.add(new ArrayList<>());
12
        }
13
    }
14

15
    public void addEdge(int u, int v) {
16
        // u 的旁边有 v，v 的旁边有 u
17
        adj.get(u).add(v);
18
        adj.get(v).add(u);
19
    }
20
}

解决思路#

至少需要三条边才能成环，写出一个最简单成环的邻接表，符号示意：A - B - C - A

1
graph = {
2
    'A': ['B'],
3
    'B': ['A', 'C'],
4
    'C': ['B', 'A']
5
}

观察顶点 C 最后一个邻接顶点 A 有什么特性，首先它肯定是被访问过的

但顶点 B 中的邻接顶点 A 也同样被访问过，它们有什么区别？

因为这是无向图，A - B 在邻接表中会被记录成 A 的旁边有 B，B 的旁边有 A，这不会形成环

说明：当 A 的旁边（B）的旁边是 A 自己，就不会形成环

那反过来如果不是自己，是不是就会形成环？回到顶点 C 最后一个邻接顶点 A

它旁边（C）的旁边是顶点 B，不是它自己，确实会形成环

邻接顶点旁边的旁边其实就是当前顶点的父顶点

总结

在无向图中，判断图中是否存在环，需要满足两个条件

当前邻接顶点已被访问

当前顶点的父顶点不等于自己

通过深度优先搜索（DFS）或广度优先搜索（BFS）遍历图，找到符合条件的顶点即可

DFS#

1
public boolean hasCycle() {
2
    // 记录顶点是否访问过
3
    boolean[] visited = new boolean[V];
4
    for (int i = 0; i < V; i++) {
5
        if (!visited[i]) {
6
            // 起始节点没有父节点
7
            if (dfs(i, visited, -1)) {
8
                return true;
9
            }
10
        }
11
    }
12
    return false;
13
}
14

15
private boolean dfs(int v, boolean[] visited, int parent) {
16
    visited[v] = true;
17
    // 遍历当前顶点的所有邻接顶点
18
    for (int neighbor : adj.get(v)) {
19
        if (!visited[neighbor]) {
20
            // 如果邻接顶点未被访问过，递归调用 dfs 方法
21
            if (dfs(neighbor, visited, v)) {
22
                return true;
23
            }
24
        } else if (neighbor != parent) {
25
            // 如果邻接顶点已被访问过且不是当前顶点的父顶点，说明存在环
26
            return true;
27
        }
28
    }
29
    return false;
30
}

BFS#

1
public boolean hasCycle() {
2
    boolean[] visited = new boolean[V];
3
    int[] parent = new int[V];
4
    Arrays.fill(parent, -1);
5

6
    for (int i = 0; i < V; i++) {
7
        if (!visited[i]) {
8
            if (bfs(i, visited, parent)) {
9
                return true;
10
            }
11
        }
12
    }
13
    return false;
14
}
15

16
private boolean bfs(int v, boolean[] visited, int[] parent) {
17
    Queue<Integer> queue = new LinkedList<>();
18
    queue.add(v);
19
    visited[v] = true;
20

21
    while (!queue.isEmpty()) {
22
        // 遍历当前节点的所有邻居
23
        int currentVertex = queue.poll();
24
        for (int neighbor : adj.get(currentVertex)) {
25
            if (!visited[neighbor]) {
26
                visited[neighbor] = true;
27
                // 记录父节点，入队
28
                parent[neighbor] = currentVertex;
29
                queue.add(neighbor);
30
                // 已访问的邻居，如果不是父节点，说明存在环
31
            } else if (neighbor != parent[currentVertex]) {
32
                return true;
33
            }
34
        }
35
    }
36
    return false;
37
}