Chương trình C++ tạo mở rộng tuyến tính ngẫu nhiên cho DAG

Chúng ta sẽ xem cách tạo mở rộng tuyến tính ngẫu nhiên (Random Linear Extension) của đồ thị có hướng không chu trình (DAG - Directed Acyclic Graph). Mở rộng tuyến thực chất là sắp xếp topo (topological sorting) của DAG. Xét đồ thị như sau:

Sắp xếp topo cho đồ thị có hướng không chu trình là thứ tự tuyến tính các đỉnh. Với mọi cạnh u-v của đồ thị có hướng, đỉnh u sẽ xuất hiện trước đỉnh v trong thứ tự.

Vì đỉnh nguồn đến sau đỉnh đích, ta cần dùng stack để lưu các phần tử trước. Sau khi duyệt hết nút, chỉ cần hiển thị từ stack.

Đầu vào

Đầu ra

Các nút sau khi sắp xếp topo: 5 4 2 3 1 0

Thuật toán

topoSort(u, visited, stack)

Đầu vào - Đỉnh bắt đầu u, mảng theo dõi nút đã thăm. Stack lưu nút.

Đầu ra - Sắp xếp các đỉnh theo trình tự topo trong stack.

Bắt đầu
  đánh dấu u là đã thăm
  với mọi đỉnh v kề với u, thực hiện
    nếu v chưa thăm, thì
      topoSort(v, visited, stack)
    done
  đẩy u vào stack
Kết thúc

performTopologicalSorting(Graph)

Đầu vào - Đồ thị có hướng không chu trình cho trước.

Đầu ra - Thứ tự các nút.

Bắt đầu
  ban đầu đánh dấu tất cả nút là chưa thăm
  với mọi nút v của đồ thị, thực hiện
    nếu v chưa thăm, thì
      topoSort(v, visited, stack)
    done
  lấy và in tất cả phần tử từ stack
Kết thúc

Ví dụ

#include<iostream>
#include<stack>
#define NODE 6
using namespace std;

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

void topoSort(int u, bool visited[], stack<int> &stk) {
  visited[u] = true; // đặt nút v là đã thăm
  for(int v = 0; v < NODE; v++) {
    if(graph[u][v]){ // với mọi đỉnh v kề u
      if(!visited[v])
        topoSort(v, visited, stk);
    }
  }
  stk.push(u); // đẩy đỉnh bắt đầu vào stack
}

void performTopologicalSort() {
  stack<int> stk;
  bool vis[NODE];
  for(int i = 0; i < NODE; i++)
    vis[i] = false; // ban đầu tất cả nút chưa thăm
  for(int i = 0; i < NODE; i++)
    if(!vis[i]) // khi nút chưa thăm
      topoSort(i, vis, stk);
  while(!stk.empty()) {
    cout << stk.top() << " ";
    stk.pop();
  }
}

int main() {
  cout << "Nodes after topological sorted order: ";
  performTopologicalSort();
  return 0;
}

Kết quả

Nodes after topological sorted order: 5 4 2 3 1 0