Sử dụng thuật toán duyệt tìm kiếm theo chiều sâu (DFS), chúng tôi có thể phát hiện các chu trình trong biểu đồ có hướng. Nếu có bất kỳ vòng lặp tự nào trong bất kỳ nút nào, nó sẽ được coi là một chu trình, ngược lại, khi nút con có một cạnh khác để kết nối cha của nó, nó cũng sẽ là một chu trình.
Đối với biểu đồ không kết nối, có thể có nhiều cây khác nhau, chúng ta có thể gọi chúng là rừng. Bây giờ chúng ta phải phát hiện chu kỳ cho tất cả các cây trong rừng.
Trong cách tiếp cận này, chúng tôi sẽ sử dụng các tập hợp khác nhau để gán các nút để thực hiện truyền tải DFS. Có ba bộ khác nhau, Trắng, Xám và Đen. Ban đầu, tất cả các nút sẽ được lưu trữ bên trong tập hợp màu trắng. Khi một nút mới được duyệt qua, nó sẽ được lưu trữ trong tập hợp màu xám và bị xóa khỏi tập hợp màu trắng. Và sau khi hoàn thành backtracking, khi nhiệm vụ đó cho nút đó hoàn thành, nó sẽ được chuyển từ tập hợp màu xám sang màu đen.
Đầu vào và Đầu ra
Input: The Adjacency matrix. 0 1 0 0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 1 0 0 1 0 0 Output: The graph has cycle.
Thuật toán
dfs (curr, wSet, gSet, bSet)
Đầu vào: Nút hiện tại, tập hợp màu trắng, màu xám và màu đen.
Đầu ra: Đúng nếu có một chu kỳ.
Begin delete curr from the while set and add it to the grey set for all nodes v connected with curr in the graph, do if v is in the black set, then skip next part, and go for next iteration if v is in the grey set, then return true if dfs(v, wSet, gSet, bSet) is true, then return true done delete curr from grey set and add to black set return fasle End
hasCycle (đồ thị)
Đầu vào - Biểu đồ cho trước.
Đầu ra: Đúng khi biểu đồ đã xoay vòng.
Begin initially insert all nodes into the white set while white set has some elements, do for all nodes v in the graph, do if v is not in the white set, then if dfs(v, wSet, gSet, bSet), then return true done done return false End
Ví dụ
#include<iostream>
#include<set>
#define NODE 5
using namespace std;
int graph[NODE][NODE] = {
{0, 1, 0, 0, 0},
{0, 0, 0, 0, 0},
{1, 0, 0, 1, 0},
{0, 0, 0, 0, 1},
{0, 0, 1, 0, 0}
};
bool dfs(int curr, set<int>&wSet, set<int>&gSet, set<int>&bSet) {
//moving curr to white set to grey set.
wSet.erase(wSet.find(curr));
gSet.insert(curr);
for(int v = 0; v < NODE; v++) {
if(graph[curr][v] != 0) { //for all neighbour vertices
if(bSet.find(v) != bSet.end())
continue; //if the vertices are in the black set
if(gSet.find(v) != gSet.end())
return true; //it is a cycle
if(dfs(v, wSet, gSet, bSet))
return true; //cycle found
}
}
//moving v to grey set to black set.
gSet.erase(gSet.find(curr));
bSet.insert(curr);
return false;
}
bool hasCycle() {
set<int> wSet, gSet, bSet; //three set as white, grey and black
for(int i = 0; i<NODE; i++)
wSet.insert(i); //initially add all node into the white set
while(wSet.size() > 0) {
for(int current = 0; current < NODE; current++) {
if(wSet.find(current) != wSet.end())
if(dfs(current, wSet, gSet, bSet))
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.