การตรวจจับวงจรในกราฟมีทิศทาง (Detect Cycle in Directed Graph)

สามารถตรวจจับวงจร (Cycle) ในกราฟมีทิศทางได้โดยใช้ Depth First Search (DFS) หากมี self-loop ในโหนดใดถือเป็นวงจร หรือหากโหนดลูกมีเส้นเชื่อมกลับไปยังโหนดพ่อก็เป็นวงจรเช่นกัน

สำหรับกราฟที่ไม่เชื่อมต่อ อาจมีต้นไม้หลายต้น (Forest) ต้องตรวจจับวงจรในทุกต้นไม้

วิธีนี้ใช้ 3 เซตสำหรับจัดสถานะโหนด:

• White Set: โหนดที่ยังไม่ได้เยี่ยมชม
• Grey Set: โหนดที่กำลังถูกเยี่ยมชม (อยู่ใน recursion stack)
• Black Set: โหนดที่เสร็จสิ้นการเยี่ยมชมแล้ว

การรับค่าและแสดงผล

Input: เมทริกซ์ตyacency
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
  ย้าย curr จาก White Set ไป Grey Set
  for ทุกโหนด v ที่ติดกับ curr do
    if v อยู่ใน Black Set then ข้าม
    if v อยู่ใน Grey Set then return true  // พบวงจร
    if dfs(v, wSet, gSet, bSet) เป็น true then return true
  done
  
  ย้าย curr จาก Grey Set ไป Black Set
  return false
End

hasCycle(graph)

Begin
  ใส่ทุกโหนดลง White Set
  while White Set ไม่ว่าง do
    for ทุกโหนด v ในกราฟ do
      if v ไม่อยู่ใน White Set then ข้าม
      if dfs(v, wSet, gSet, bSet) แล้ว return true
    done
  done
  return false
End

ตัวอย่างโค้ด (C++)

#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) {
  wSet.erase(wSet.find(curr));
  gSet.insert(curr);
  
  for(int v = 0; v < NODE; v++) {
    if(graph[curr][v] != 0) {
      if(bSet.find(v) != bSet.end()) continue;
      if(gSet.find(v) != gSet.end()) return true;
      if(dfs(v, wSet, gSet, bSet)) return true;
    }
  }
  
  gSet.erase(gSet.find(curr));
  bSet.insert(curr);
  return false;
}

bool hasCycle() {
  set<int> wSet, gSet, bSet;
  for(int i = 0; i < NODE; i++) wSet.insert(i);
  
  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 = hasCycle();
  if(res) cout << "The graph has cycle." << endl;
  else cout << "The graph has no cycle." << endl;
}

ผลลัพธ์

The graph has cycle.