유향 그래프에서 주기 감지

DFS(Depth First Search) 탐색 알고리즘을 사용하여 방향 그래프에서 주기를 감지할 수 있습니다. 임의의 노드에 자체 루프가 있으면 주기로 간주되고, 그렇지 않으면 자식 노드에 부모를 연결하는 다른 가장자리가 있는 경우에도 주기가 됩니다.

연결이 끊긴 그래프의 경우 다른 나무가 있을 수 있으며 이를 포리스트라고 부를 수 있습니다. 이제 우리는 숲의 모든 나무에 대한 주기를 감지해야 합니다.

이 접근 방식에서는 다른 집합을 사용하여 DFS 탐색을 수행할 노드를 할당합니다. 화이트, 그레이, 블랙의 3가지 세트가 있습니다. 처음에는 모든 노드가 화이트 세트 안에 저장됩니다. 하나의 새 노드가 탐색되면 회색 집합에 저장되고 흰색 집합에서 제거됩니다. 그리고 역추적을 완료한 후 해당 노드에 대한 작업이 완료되면 회색에서 검은색 세트로 교체됩니다.

입력 및 출력

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)

입력: 현재 노드, 흰색, 회색 및 검은색 집합입니다.

출력: 주기가 있는 경우 참입니다.

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(그래프)

입력 - 주어진 그래프.

출력: 그래프가 순환되면 참입니다.

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.