拓撲排序
簡介
拓撲排序是將偏序的資料線性化的一種排序方法，復習下偏序和全序的概念：
全序關系是偏序關系的一個子集，
全序是集合內任何一對元素都是可比較的，比如數軸上的點都具有一個線性的數值，因此根據數值就可以進行比較，
偏序是集合內不是所有元素都是可以比較的，比如平面內的點由橫坐標和縱坐標組成，是不可直接比較大小的，這是因為橫坐標和縱坐標是兩個維度，在每個維度內都可以用數值比較，但是維度之間不可量化比較（就像學習成績和身體素質之間無法量化比較），當然偏序是個數學概念，未必是多維度引發的不可比較，只需滿足以下關系即滿足偏序關系：
設 P 是集合，P 上的二元關系“≤”滿足以下三個條件，則稱“≤”是 P 上的偏序關系（或部分序關系）：
（1）自反性：a≤a，?a∈P；
（2） 反對稱性：?a，b∈P，若 a≤b 且b≤a，則 a=b；
（3） 傳遞性：?a，b，c∈P，若 a≤b 且b≤c，則 a≤c；
注意這里的“≤”是一個自定義的二元運算子，而不是通常的線性運算的大小關系，
理解了偏序關系之后，拓撲排序就是將偏序關系線性化，舉一個具體場景，在有向無環圖中，“節點 A 是否可由節點 B 到達”即是一種偏序關系，在該有向無環圖中節點，在不移動的情況下可以到達自身，因此滿足自反性，且在有向無環圖中不存在環，若 A 可到達 B 且 B可到達A，則A，B 必是相同節點，因此滿足反對稱性，當節點 A 可以到達節點 B，且節點 B 可以到達節點C 時，節點 A 也可以到達節點 C，因此滿足傳遞性，
在該場景下，拓撲排序即是將有向無環圖中所有節點按照“節點 A 是否可由節點 B 到達”來進行線性化排序，如上圖所示，對它進行拓撲排序可以使用深度優先演算法完成，深度優先演算法可以復習課件，其程序大概如下，
- 選取頂點 s（一般選取入度比較小的節點更合適，比如上圖的節點 1），標記狀態
- 若 s 有未被訪問的鄰居，則選擇鄰居標記狀態繼續訪問，否則回傳
- 如果一次深度優先搜索還有節點未被訪問，則重復步驟 1，直到所有節點被訪問到
這種方法可以將滿足偏序關系的有向無環圖線性化為??一種排序結果：1，2，4，3，5，當然對于更復雜的有向無環圖可能有多種合法的排序結果，
實作
實作代碼如下：
//
// Created by lenovo on 2022/5/1.
//
#include <utility>
#include "iostream"
#include "vector"
#include "fstream"
using namespace std;
typedef struct EdgeNode
{
int index; //鄰接點
struct EdgeNode *next; //鏈表，指向下一個鄰接點
}EdgeNode;
typedef struct PointNode //頂點表節點
{
int in; //頂點入度
int data; //頂點資訊
EdgeNode* firstEdge; //邊表頭指標
PointNode(){in=NULL;data= https://www.cnblogs.com/world-explorer/p/NULL;firstEdge= nullptr;}
}PointNode;
typedef struct Graph{
int NumPoint,NumEdge;
PointNode* arr;
}Graph;
void read_file(Graph* G){ //構造圖Graph
ifstream inputData;
string input_file_path="..\\input.txt"; //示例輸入在同級目錄input.txt
inputData.open(input_file_path, ios::in);
string line;
int tmp=0;
int i=0;
EdgeNode *e;
while (inputData>>line){
int bracketPos = line.find(',');
int from = stoi(line.substr(0, bracketPos));
int to= stoi(line.substr(bracketPos+1,line.size()-bracketPos));
G->NumEdge++; //增加邊
if(from!=tmp){tmp=from;G->NumPoint++;} //增加新的節點
/*保存邊資訊*/
e = (EdgeNode*)malloc(sizeof(EdgeNode));
e->index = to;
e->next = G->arr[from].firstEdge;
G->arr[from].firstEdge = e;
G->arr[to].in++;
}
inputData.close();
}
/*獲取輸入的邊的數量*/
int read_num(){
ifstream inputData;
string input_file_path="..\\input.txt";
inputData.open(input_file_path, ios::in);
string line;
int tmp=0;
while (inputData>>line){
tmp++;
}
inputData.close();
return tmp;
}
int ToupuSort(Graph* G){
EdgeNode* edge;
int next;
vector<int> stack;
int count=0;
for(int i=0;i<G->NumPoint;++i){ //堆疊stack存盤入度為0的節點,需排除0節點
if(G->arr[i].in==0)
stack.push_back(i);
}
int out;
while (stack[0]!=stack.back()){ //當堆疊為非空
out=stack.back();
cout<<out<<",";
stack.pop_back();
count++;
for(edge=G->arr[out].firstEdge;edge;edge=edge->next){ //更新鄰接點的入度，-1
next=edge->index;
if(!(--G->arr[next].in)) //鄰接節點入度原為1，則入堆疊
stack.push_back(next);
}
}
if(count<G->NumPoint){ //有環
return 0;
}else
return 1; //無環，且全部輸出
}
int main(){
Graph G;
PointNode arry[read_num()];
G.arr=arry;
read_file(&G); //構建圖
ToupuSort(&G); //輸出拓撲排序
return 0;
}
示例輸入：
1,2
1,4
2,4
2,3
3,5
4,3
4,5
示例輸出:
1，2，4，3，5
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/469447.html
標籤：C++