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

เพื่อตรวจจับวงจรในกราฟไม่มีทิศทาง ใช้ DFS traversal สำหรับโหนดที่เยี่ยมชมแล้ว v หากพบโหนดติดกัน u ที่เยี่ยมชมแล้ว และ u ไม่ใช่พ่อของ v แสดงว่าพบวงจร

สมมติว่าไม่มีเส้นเชื่อมขนาน (Parallel Edges) ระหว่างคู่โหนดใดๆ

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

Input: เมทริกซ์ตyacency
0 1 0 0 0
1 0 1 1 0
0 1 0 0 1
0 1 0 0 1
0 0 1 1 0

Output: The graph has cycle.

อัลกอริทึม

dfs(vertex, visited, parent)

Begin
  เพิ่ม vertex ใน visited set
  for ทุกโหนด v ที่ติดกับ vertex do
    if v = parent then continue
    if v ไม่อยู่ใน visited set then
      if dfs(v, visited, vertex) เป็น true then return true
    else
      return true  // พบวงจร
    end if
  done
  return false
End

hasCycle(graph)

Begin
  for ทุกโหนด v ในกราฟ do
    if v อยู่ใน visited set แล้ว then continue
    if dfs(v, visited, null) เป็น true then return true
  done
  return false
End

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

#include <iostream>
#include <set>
#define NODE 5
using namespace std;

int graph[NODE][NODE] = {
  {0, 1, 0, 0, 0},
  {1, 0, 1, 1, 0},
  {0, 1, 0, 0, 1},
  {0, 1, 0, 0, 1},
  {0, 0, 1, 1, 0}
};

bool dfs(int vertex, set<int> &visited, int parent) {
  visited.insert(vertex);
  for(int v = 0; v < NODE; v++) {
    if(graph[vertex][v]) {
      if(v == parent) continue;
      if(visited.find(v) != visited.end()) return true;
      if(dfs(v, visited, vertex)) return true;
    }
  }
  return false;
}

bool hasCycle() {
  set<int> visited;
  for(int v = 0; v < NODE; v++) {
    if(visited.find(v) != visited.end()) continue;
    if(dfs(v, visited, -1)) 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.