무방향 그래프에 주기가 있는지 여부를 감지하기 위해 주어진 그래프에 대해 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; }
출력
The graph has cycle.