Phát hiện chu trình trong đồ thị vô hướng

Để phát hiện xem có chu trình nào trong đồ thị vô hướng hay không, ta sẽ sử dụng thuật toán duyệt DFS cho đồ thị cho trước. Đối với mọi đỉnh v đã thăm, khi ta tìm thấy bất kỳ đỉnh kề u nào, sao cho u đã được thăm, và u không phải là cha của đỉnh v. Khi đó một chu trình được phát hiện.

Ta giả định rằng không có song song cạnh cho bất kỳ cặp đỉnh nào.

Đầu vào và Đầu ra: Ma trận kề
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
Đầu ra: Đồ thị có chu trình.

Thuật toán

dfs(vertex, visited, parent)
Đầu vào: Đỉnh bắt đầu, tập visited, và nút cha của đỉnh.
Đầu ra: True khi tìm thấy chu trình.
Bắt đầu
  thêm vertex vào tập visited
  với mọi đỉnh v kề với vertex, thực hiện
    nếu v = parent thì
      trả về true
    nếu v không nằm trong tập visited thì
      trả về true
    nếu dfs(v, visited, vertex) là true thì
      trả về true
  kết thúc
  trả về false
Kết thúc

hasCycle(graph)
Đầu vào: Đồ thị cho trước.
Đầu ra: True khi tìm thấy chu trình.
Bắt đầu
  với mọi đỉnh v trong đồ thị, thực hiện
    nếu v không nằm trong tập visited thì
      sang vòng lặp tiếp theo
    nếu dfs(v, visited, ∅) là true thì
      // cha của v là null
      trả về true
    trả về false
  kết thúc
Kết thúc

Ví dụ (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) // nếu v là cha thì không đi hướng đó
        continue;
      if(visited.find(v) != visited.end()) // nếu v đã được thăm
        return true;
      if(dfs(v, visited, vertex))
        return true;
    }
  }
  return false;
}

bool hasCycle() {
  set<int> visited; // tập visited
  for(int v = 0; v < NODE; v++) {
    if(visited.find(v) != visited.end()) // khi visited chứa v, nhảy sang vòng lặp tiếp theo
      continue;
    if(dfs(v, visited, -1)) { // -1 vì không có cha của đỉnh bắt đầu
      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;
}

Đầu ra

The graph has cycle.