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

Sử dụng thuật toán duyệt theo chiều sâu (DFS) ta có thể phát hiện chu trình trong đồ thị có hướng. Nếu có bất kỳ khuyên (self-loop) nào ở bất kỳ nút nào, nó sẽ được coi là một chu trình. Ngược lại, khi nút con có cạnh khác kết nối đến nút cha của nó, đó cũng là một chu trình.

Đối với đồ thị không liên thông, có thể có nhiều cây khác nhau, ta có thể gọi chúng là một rừng. Bây giờ ta phải phát hiện chu trình cho tất cả các cây trong rừng đó.

Trong phương pháp này, ta sẽ sử dụng các tập hợp khác nhau để gán nút thực hiện duyệt DFS. Có ba tập hợp khác nhau: Trắng (White), Xám (Grey) và Đen (Black). Ban đầu, tất cả các nút sẽ được lưu trong tập trắng. Khi một nút mới được duyệt, nó sẽ được lưu trong tập xám và loại bỏ khỏi tập trắng. Sau khi hoàn thành backtracking, khi nhiệm vụ cho nút đó hoàn tất, nó sẽ được chuyển từ tập xám sang tập đen.

Đầu vào và Đầu ra

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

Thuật toán

dfs(curr, wSet, gSet, bSet)

Đầu vào: Nút hiện tại, tập trắng, tập xám và tập đen.

Đầu ra: True nếu có chu trình.

Bắt đầu
  xóa curr khỏi tập trắng và thêm vào tập xám
  với mọi nút v kết nối với curr trong đồ thị, thực hiện
    nếu v nằm trong tập đen thì
      bỏ qua phần tiếp theo, sang vòng lặp tiếp theo
    nếu v nằm trong tập xám thì
      trả về true
    nếu dfs(v, wSet, gSet, bSet) là true thì
      trả về true
  kết thúc
  xóa curr khỏi tập xám và thêm vào tập đen
  trả về false
Kết thúc

hasCycle(graph)

Đầu vào: Đồ thị cho trước.

Đầu ra: True khi đồ thị có chu trình.

Bắt đầu
  ban đầu chèn tất cả nút vào tập trắng
  trong khi tập trắng còn phần tử, thực hiện
    với mọi nút v trong đồ thị, thực hiện
      nếu v không nằm trong tập trắng thì
        nếu dfs(v, wSet, gSet, bSet) thì
          trả về true
      kết thúc
    kết thúc
  kết thúc
  trả về false
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},
  {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) {
  // di chuyển curr từ tập trắng sang tập xám
  wSet.erase(wSet.find(curr));
  gSet.insert(curr);
  
  for(int v = 0; v < NODE; v++) {
    if(graph[curr][v] != 0) { // cho tất cả đỉnh kề
      if(bSet.find(v) != bSet.end())
        continue; // nếu đỉnh nằm trong tập đen
      if(gSet.find(v) != gSet.end())
        return true; // đó là chu trình
      if(dfs(v, wSet, gSet, bSet))
        return true; // tìm thấy chu trình
    }
  }
  
  // di chuyển v từ tập xám sang tập đen
  gSet.erase(gSet.find(curr));
  bSet.insert(curr);
  return false;
}

bool hasCycle() {
  set<int> wSet, gSet, bSet; // ba tập hợp: trắng, xám và đen
  for(int i = 0; i < NODE; i++)
    wSet.insert(i); // ban đầu thêm tất cả nút vào tập trắng
  
  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;
}

Đầu ra

The graph has cycle.