为了检测无向图中是否存在任何循环,我们将对给定图使用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: 该图具有循环。
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 << "该图具有循环。" << endl; else cout << "该图没有循环。" << endl; }
输出结果
该图具有循环。