假設你有n個任務要做，其中某些任務需要在另外一些任務之前完成，你該如何規劃你的任務，使得按照你的規劃依次做下去就能完成你的所有任務？
定義
拓撲排序（Topological sorting, toposort）：給定一個有向無環圖，將所有節點排成一個線性序列，在這個序列中只有從前面的節點指向后面的節點的邊，
條件
有向圖中沒有環，如果有環的話就無法進行拓撲排序，因為如果嘗試將所有節點排成一個線性序列的話，就必然會出現這種情況：
必然有從后面的節點指向前面的節點的有向邊，不符合拓撲排序的定義，所以無法對有環的有向圖進行拓撲排序，
假如你手邊有兩個任務A和B，要完成任務A你得先完成任務B，要完成任務B你又得先完成任務A，你一定會覺得這很刁鉆，對吧？
注意一張圖的拓撲排序并不是唯一的，比如下面這張圖：
序列 0 1 2 3 和 0 2 1 3 均是合法的拓撲排序序列，只要1和2出現在0之后3之前即可，內部的順序無所謂，
方法
以下面這張圖為例：
最先完成的任務之前沒有需要完成的任務，用圖論的語言來說就是拓撲排序序列的第一個節點沒有入邊，入度為0，在這張圖中，入度為0的節點有兩個：節點0和節點1，將這兩個節點添加到序列中，
任務完成之后，就不需要考慮了，我們可以直接將這兩個節點從圖中移除，
這時，節點2就變成0入度節點了，繼續同樣的步驟，一直這樣重復下去，直到圖中沒有剩余的節點為止，這樣，我們就得到了這樣一個拓撲排序序列：
0 1 2 3 4 5 6 7
所以，整個拓撲排序演算法如下：
- 尋找0入度節點，從圖中移除并添加到拓撲排序序列，
- 重復上述步驟，直到圖中沒有剩余的節點，
演算法及代碼實作
為了使語意更加明確，我們先定義型別別名node_t，代表unsigned long long：
using node_t = unsigned long long;
因為整個演算法主要利用的是兩個節點之間的鄰接關系，我們在這里使用鄰接表來表示整個圖，同時使用鄰接表需要的空間花銷更少，
class Graph {
unsigned long long n;
vector<vector<node_t>> map;
public:
Graph(initializer_list<initializer_list<node_t>> list) : n(list.size()), map({}) {
for (auto &l : list) {
map.emplace_back(l);
}
}
vector<node_t> toposort();
};
為了不破壞整個圖的結構，我們單獨開一個陣列來存放所有節點的入度，偽代碼如下：
初始化入度陣列S
for (節點v : 節點集合V) {
for (節點v’ : 以節點V為起點的所有有向邊的終點集合V’) {
S[v’]++
}
}
代碼：
vector<node_t> inDegrees(n, 0);
for (auto &ends : map) {
for (node_t end : ends) {
inDegrees[end]++;
}
}
注意到某一時刻0入度節點可能不止1個，因此我們需要某種資料結構來“暫存”這些0入度節點，又注意到0入度節點總是先出現后被移除并加入到序列，因此我們的Mr. Right就是具有“先入后出”性質的佇列，
偽代碼：
初始化佇列Q
for (節點v : 節點集合V) {
if (節點v的入度為0) {
將節點v加入到佇列Q中
}
}
代碼：
queue<node_t> zeroInDegree;
for (node_t node = 0; node < n; node++) {
if (inDegrees[node] == 0) {
zeroInDegree.push(node);
}
}
接下來，我們只需要將佇列頭部節點移除并加入到排序序列，并相應的更新該節點指向的節點的入度，如果指向的節點的入度減為零了，那就添加到佇列中，
偽代碼：
令佇列Q的頭部節點為v’
將v’彈出佇列并加入到拓撲排序序列
for (節點v’’ : v’指向的所有節點集合) {
v''的入度減一
if (v''的入度 == 0) {
將v''加入佇列Q
}
}
代碼：
node_t v = zeroInDegree.front();
zeroInDegree.pop();
sort.push_back(v);
for (node_t end : map[v]) {
inDegrees[end]--;
if (inDegrees[end] == 0) {
zeroInDegree.push(end);
}
}
如此重復下去，如果佇列變空了，則說明已經將所有的節點都加入到序列中了，演算法結束，
整個演算法的偽代碼：
初始化入度陣列S、佇列Q和拓撲排序序列T
for (節點v : 節點集合V) {
for (節點v’ : 以節點V為起點的所有有向邊的終點集合V’) {
S[v’]++
}
}
for (節點v : 節點集合V) {
if (節點v的入度為0) {
將節點v加入到佇列Q中
}
}
令佇列Q的頭部節點為v’
將v’彈出佇列并加入到拓撲排序序列
for (節點v’’ : v’指向的所有節點集合) {
v''的入度減一
if (v''的入度 == 0) {
將v''加入佇列Q
}
}
代碼：
vector<node_t> Graph::toposort() {
vector<node_t> inDegrees(n, 0);
queue<node_t> zeroInDegree;
vector<node_t> sort;
for (auto &ends : map) {
for (node_t end : ends) {
inDegrees[end]++;
}
}
for (node_t node = 0; node < n; node++) {
if (inDegrees[node] == 0) {
zeroInDegree.push(node);
}
}
while (!zeroInDegree.empty()) {
node_t v = zeroInDegree.front();
zeroInDegree.pop();
sort.push_back(v);
for (node_t end : map[v]) {
inDegrees[end]--;
if (inDegrees[end] == 0) {
zeroInDegree.push(end);
}
}
}
return sort;
}
測驗：
int main() {
Graph graph{
{2},
{2},
{3, 4, 5},
{5},
{5},
{6, 7},
{7},
{}
};
auto sort = graph.toposort();
for (auto node : sort) {
cout << node << ' ';
}
cout << endl;
return 0;
}
復雜度分析
時間復雜度：O(n+e)，其中n為頂點數，e為邊數，這主要取決于尋找0入度節點所需要的時間花銷，
空間復雜度：O(n+e)，其中n為頂點數，e為邊數，這主要取決于鄰接表所需要的空間花銷，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/539633.html
標籤：其他
上一篇：從近世代數的角度理解補碼