17. 图环

图分为有向图（Directed Graph，Digraph）和无向图（Undirected Graph），区别在于节点之间的边是否有方向。

问题 ：检测连通图中是否有环。

17.1. 无向图

  • 深度优先遍历 （Depth-First Search Traversal）

    标记法，使用 visited 数组对图中的所有顶点定义三种状态：

    • 顶点未被访问过（0）

    • 顶点刚开始被访问（1）

    • 顶点被访问过，并且其所有邻接点也被访问过（2）

    另外，使用 father 数组记录 DFS 过程中所有顶点的父节点。

    判断：若在 DFS 过程中遇到“回边”（即指向已经访问过的顶点的边，父节点除外），则存在环。

     1void DFS(int v, Graph G)
 2{
 3    visited[v] = 1; // 开始访问节点 v
 4    for(int i = 0 ; i < G.vertexNum; i++)
 5    {
 6        if(i != v && G.arc[v][i] != INF) // 邻接矩阵中节点 v 的邻接点（邻接矩阵表示法）
 7        {
 8            if(visited[i] == 1 && father[v] != i)
 9            // i 不是父节点，而且还被访问过（状态 1，说明不是回溯过来的顶点），说明存在环
10            // visited[i] == 2 不行：
11            // 对无向图而言，v 也是 i 的邻接点，意味着 i -> v 早就访问过，不会再重复访问 v -> i，因此不会出现 visited[i] == 2
12            // 对有向图而言，说明 i 是 v 和其他节点的公共子节点，不构成环
13            {
14                cout<<"图存在环";
15                int temp = v;
16                while(temp != i)
17                {
18                    cout<< temp << " <- "; // 输出环
19                    temp = father[temp];
20                }
21                cout<< i <<endl;
22            }
23            else
24                if(visited[i] == 0)
25                {
26                    father[i] = v; // 更新 father 数组
27                    DFS(i, G);
28                }
29
30        }
31    }
32    visited[v] = 2; // 遍历完 v 所有的邻接点，变为状态 2
33}

  • 广度优先遍历 （Breadth-First Search Traversal）

    与 DFS 类似，需要使用 father 数组记录 BFS 过程中所有顶点的父节点。

    visited 数组只需要记录两种状态：未访问和已访问。

17.2. 有向图

  • 拓扑排序 （Topological Sorting）

    见本章第 10 节。

  • 深度优先遍历 （Depth-First Search Traversal）

    与无向图的 DFS 相同。

17.3. 参考资料

  1. 判断无向图/有向图中是否存在环