在有向图中检测周期

使用深度优先搜索(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:
该图具有循环。

算法

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（图）

输入-给定图。

输出：图形循环后为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) {
   //移动curr到white set到gray 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
      }
   }

   //将v移至灰色设置为黑色设置。
   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 << "该图具有循环。" << endl;
   else
      cout << "该图没有循环。" << endl;
}

输出结果

该图具有循环。