資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法學研究檢測有向圖中的環
使用深度優先搜尋 (DFS) 遍歷演算法，我們可以檢測有向圖中的環。如果任何節點存在自環，則將其視為一個環；否則，當子節點有另一條邊連線其父節點時，它也是一個環。
對於非連通圖，可能存在不同的樹，我們可以稱它們為森林。現在我們必須檢測森林中所有樹的環。
在這種方法中，我們將使用不同的集合來分配節點以執行 DFS 遍歷。有三種不同的集合：白色、灰色和黑色。最初，所有節點都將儲存在白色集合中。當遍歷一個新節點時，它將儲存在灰色集合中並從白色集合中移除。並且在完成回溯後，當該節點的任務完成時，它將從灰色集合交換到黑色集合。
輸入和輸出
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.
演算法
dfs(curr, wSet, gSet, bSet)
輸入：當前節點、白色集合、灰色集合和黑色集合。
輸出：如果存在環則返回True。
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(graph)
輸入 − 給定的圖。
輸出：當圖包含環時返回True。
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
示例
#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;
}輸出
The graph has cycle.
更新於： 2020年6月16日
2K+ 瀏覽量
廣告