Chương trình C++ áp dụng DFS để thực hiện sắp xếp topo của đồ thị có hướng không chu trình

Sắp xếp topo của đồ thị có hướng không chu trình (DAG) là một thứ tự tuyến tính của các đỉnh sao cho với mọi cạnh có hướng uv, đỉnh u xuất hiện trước đỉnh v trong thứ tự đó. Nếu đồ thị không phải là DAG, thì sắp xếp topo là không thể.

Các hàm và mã giả

Bắt đầu
  hàm topologicalSort():
    a) Đánh dấu nút hiện tại đã thăm.
    b) Đệ quy cho tất cả các đỉnh kề với đỉnh này.
    c) Đẩy đỉnh hiện tại vào ngăn xếp lưu kết quả.
  Kết thúc
  hàm topoSort() sử dụng đệ quy topologicalSort():
    a) Đánh dấu tất cả các đỉnh chưa được thăm.
    b) Gọi hàm topologicalSort().
    c) In nội dung ngăn xếp.
  Kết thúc

Ví dụ

#include <iostream>
#include <list>
#include <stack>
using namespace std;

class G {
    int n;
    list<int> *adj;
    // khai báo hàm
    void topologicalSort(int v, bool visited[], stack<int> &Stack);
public:
    G(int n); // constructor
    void addEd(int v, int w);
    void topoSort();
};

G::G(int n) {
    this->n = n;
    adj = new list<int>[n];
}

void G::addEd(int v, int w) // thêm cạnh vào đồ thị
{
    adj[v].push_back(w); // thêm w vào danh sách của v
}

void G::topologicalSort(int v, bool visited[], stack<int> &Stack) {
    visited[v] = true; // đánh dấu nút hiện tại đã thăm
    list<int>::iterator i;
    // Đệ quy cho tất cả các đỉnh kề
    for (i = adj[v].begin(); i != adj[v].end(); ++i)
        if (!visited[*i])
            topologicalSort(*i, visited, Stack);
    Stack.push(v);
}

void G::topoSort() {
    stack<int> Stack;
    bool *visited = new bool[n];
    // Đánh dấu tất cả các đỉnh chưa thăm
    for (int i = 0; i < n; i++)
        visited[i] = false;
    for (int i = 0; i < n; i++)
        if (visited[i] == false)
            topologicalSort(i, visited, Stack);
    while (Stack.empty() == false) {
        cout << Stack.top() << " "; // in phần tử
        Stack.pop();
    }
}

int main() {
    G g(6);
    g.addEd(4, 2);
    g.addEd(5, 1);
    g.addEd(4, 0);
    g.addEd(3, 1);
    g.addEd(1, 3);
    g.addEd(3, 2);
    cout << " Topological Sort of the given graph \n";
    g.topoSort();
    return 0;
}

Kết quả

Topological Sort of the given graph
5 4 1 3 2 0