检测无向图中的周期
为了检测无向图中是否存在任何循环，我们将对给定图使用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: Thestartvertex,thevisitedset,andtheparentnodeofthevertex.
Output: Trueacycleisfound.Begin
addvertexinthevisitedset
forallvertexvwhichisadjacentwithvertex,do
ifv=parent,then
returntrue
ifvisnotinthevisitedset,then
returntrue
ifdfs(v,visited,vertex)istrue,then
returntrue
done
returnfalse
EndhasCycle(graph)Input: Thegivengraph.Output: Truewhenacyclehasfound.Begin
forallvertexvinthegraph,do
ifvisnotinthevisitedset,then
gofornextiteration
ifdfs(v,visited,φ)istrue,then //parentofvisnull
returntrue
returnfalse
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;
}输出结果
该图具有循环。