Để phát hiện xem có bất kỳ chu trình nào trong đồ thị vô hướng hay không, chúng ta sẽ sử dụng đường truyền DFS cho đồ thị đã cho. Đối với mọi đỉnh đã thăm v, khi chúng ta đã tìm thấy bất kỳ đỉnh nào liền kề u, sao cho u đã được thăm và u không phải là đỉnh cha của đỉnh v. Khi đó một chu trình sẽ được phát hiện.
Chúng ta sẽ giả sử rằng không có cạnh nào song song cho bất kỳ cặp đỉnh nào.
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.
Thuật toán
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
Ví dụ
#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; }
Đầu ra
The graph has cycle.