Sắp xếp Topological (Topological Sorting)

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

Vì ta biết đỉnh nguồn sẽ đến sau đỉnh đích, nên ta cần dùng một ngăn xếp (stack) để lưu các phần tử trước. Sau khi hoàn thành tất cả các nút, ta có thể đơn giản hiển thị chúng từ ngăn xếp.

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

Đầu vào:
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
Đầu ra: Các nút sau khi sắp xếp topological: 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 hay chưa. Ngăn xếp để lưu nút.

Đầu ra: Sắp xếp các đỉnh theo trình tự topological trong ngăn xếp.

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 được thăm thì
      topoSort(v, visited, stack)
  kết thúc
  đẩy u vào ngăn xếp
Kết thúc

performTopologicalSorting(Graph)

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

Đầu ra: Trình 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 được thăm thì
      topoSort(i, visited, stack)
  kết thúc
  lấy và in tất cả phần tử từ ngăn xếp
Kết thúc.

Ví dụ (C++)

#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]) { // cho tất cả đỉnh v kề với 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();
}

Đầu ra

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