检测无向图中的环
要检测无向图中是否存在环,我们应该对给定的图使用 DFS 遍历。对于每个访问过的顶点 v,当我们找到任何相邻顶点 u 时,u 已被访问,并且 u 不是顶点 v 的父级。那么将检测到一个环。
我们假设对于任何一对顶点,没有平行边。
Input and Output: Adjacency matrix 0 1 0 0 0 1 0 1 1 0 0 1 0 0 1 0 1 0 0 1 0 0 1 1 0 Output: The graph has cycle.
算法
dfs(vertex, visited, parent)
Input: The start vertex, the visited set, and the parent node of the vertex.
Output: True a cycle is found.Begin add vertex in the visited set for all vertex v which is adjacent with vertex, do if v = parent, then return true if v is not in the visited set, then return true if dfs(v, visited, vertex) is true, then return true done return false End hasCycle(graph) Input: The given graph. Output: True when a cycle has found.Begin for all vertex v in the graph, do if v is not in the visited set, then go for next iteration if dfs(v, visited, φ) is true, then //parent of v is null return true return false done End
示例
#include<iostream> #include<set> #define NODE 5 using namespace std; int graph[NODE][NODE] = { {0, 1, 0, 0, 0}, {1, 0, 1, 1, 0}, {0, 1, 0, 0, 1}, {0, 1, 0, 0, 1}, {0, 0, 1, 1, 0} }; bool dfs(int vertex, set<int>&visited, int parent) { visited.insert(vertex); for(int v = 0; v<NODE; v++) { if(graph[vertex][v]) { if(v == parent) //if v is the parent not move that direction continue; if(visited.find(v) != visited.end()) //if v is already visited return true; if(dfs(v, visited, vertex)) return true; } } return false; } bool hasCycle() { set<int> visited; //visited set for(int v = 0; v<NODE; v++) { if(visited.find(v) != visited.end()) //when visited holds v, jump to next iteration continue; if(dfs(v, visited, -1)) { //-1 as no parent of starting vertex return true; } } return false; } int main() { bool res; res = hasCycle(); if(res) cout << "The graph has cycle." << endl; else cout << "The graph has no cycle." << endl; }
Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.
输出
The graph has cycle.
广告