算法與數據結構基礎10：C++實現——拓撲排序
一 定義
拓撲排序是對有向無環圖(Directed Acyclic Graph簡稱DAG)頂點的一種排序，
它使得如果存在一條從頂點A到頂點B的路徑，那麼在排序中B出現在A的後面。
二 先決條件
能夠進行拓撲排序圖有兩個先決條件：有向、無環，即有向無環圖。
三 偏序全序
連通圖：任意兩點之間都存在至少一條邊
偏序：非連通圖（有向無環圖滿足偏序關系）
全序：單連通圖
四 結果唯一性
對於僅滿足偏序關系的有向無環圖中，因為有兩個點之間的關系是不確定的，所以導致排序的結果是不唯一的。
滿足全序關系的有向無環圖，兩個點之間存在有向邊的，因此排序結果唯一。
五 入度排序
該方法的每一步總是輸出當前無前趨(即入度為零)的頂點，輸出“拓撲次序”。
其抽象算法可描述為：
NonPreFirstTopSort(G){//優先輸出無前趨的頂點
while(G中有入度為0的頂點)do{
從G中選擇一個入度為0的頂點v且輸出之；
從G中刪去v及其所有出邊；
}
if(輸出的頂點數目<|V(G)|)//若此條件不成立，則表示所有頂點均已輸出，排序成功。
Error("G中存在有向環，排序失敗！")；
}
注意：
無前趨的頂點優先的拓撲排序算法在具體存儲結構下，為便於考察每個頂點的入度，可保存各頂點當前的入度。
為避免每次選入度為0的頂點時掃描整個存儲空間，可設一個棧或隊列暫存所有入度為零的頂點：
在開始排序前，掃描對應的存儲空間，將入度為零的頂點均入棧(隊)。以後每次選入度為0的頂點時，只需做出棧(隊)操作即可。
六 出度排序
該方法的每一步均是輸出當前無後繼(即出度為0)的頂點，輸出“逆拓撲次序”。
算法的抽象描述為：
NonSuccFirstTopSort(G){//優先輸出無後繼的頂點
while(G中有出度為0的頂點)do {
從G中選一出度為0的頂點v且輸出v；
從G中刪去v及v的所有入邊
}
if(輸出的頂點數目<|V(G)|)
Error("G中存在有向環，排序失敗!")；
}
七 深度優先
當從某頂點v出發的DFS搜索完成時，v的所有後繼必定均已被訪問過(想像它們均已被刪除)，
此時的v相當於是無後繼的頂點，因此在DFS算法返回之前輸出頂點v即可得到 DAG的逆拓撲序列。
其中第一個輸出的頂點必是無後繼(出度為0)的頂點，它應是拓撲序列的最後一個頂點。
若希望得到的不是逆拓撲序列，可增加T來保存輸出的頂點。若假設T是棧，並在DFSTraverse算法的開始處將T初始化，
利用DFS求拓撲序列的抽象算法可描述為：
void DFSTopSort(G，i，T){
//在DisTraverse中調用此算法，i是搜索的出發點，T是棧
int j；
visited[i]=TRUE； //訪問i
for(所有i的鄰接點j)//即
∈E(G)
if(!visited[j])
DFSTopSort(G，j，T)；
//以上語句完全類似於DFS算法
Push(&T，i)； //從i出發的搜索已完成，輸出i
}
八 代碼
只實現了出度的，另外兩種差不多，沒有寫。
// GraphList.h（在此文的代碼基礎上修改 算法與數據結構基礎8：C++實現有向圖——鄰接表存儲）
#include
#include
#include
#include
using namespace std;
// 邊
struct Edge{
int vName;
int weight;// 權值
struct Edge* next;
};
// 頂點(鏈表頭)
struct Vertex{
int vName;
int in;// 入度
int out; // 初度
struct Edge* next;
};
// 有向圖
class GraphList
{
public:
~GraphList();
void createGraph();
void printGraph();
bool topsortInDegree();
bool topsortOutDegree();
private:
// 1. 輸入定點數
void inputVertexCount();
// 2. 生成定點數組
void makeVertexArray();
// 3. 輸入邊數
void inputEdgeCount();
// 4. 輸入邊的起始點
void inputEdgeInfo();
// 5. 添加邊節點至對應的鏈表中
void addEdgeToList(int vFrom, int weight, int vTo);
private:
int m_vCount;
int m_eCount;
Vertex* m_vVertex;
};
GraphList::~GraphList(){
for (int i = 0; i < m_vCount; ++i){
Edge* tmp = m_vVertex[i].next;
Edge* edge = NULL;
while(tmp){
edge = tmp;
tmp = tmp->next;
delete edge;
edge = NULL;
}
}
delete[] m_vVertex;
}
void GraphList::inputVertexCount()
{
cout << "please input count of vertex:";
cin >> m_vCount;
}
void GraphList::makeVertexArray()
{
m_vVertex = new Vertex[m_vCount];
// 初始化
for (int i = 0; i < m_vCount; ++i){
m_vVertex[i].vName = i;
m_vVertex[i].next = NULL;
m_vVertex[i].in = 0;
m_vVertex[i].out = 0;
}
}
void GraphList::inputEdgeCount()
{
cout << "please input count of edge:";
cin >> m_eCount;
}
void GraphList::inputEdgeInfo()
{
cout << "please input edge information:" << endl;
for (int i = 0; i < m_eCount; ++i){
cout << "the edge " << i << ":" << endl;
// 起點
int from = 0;
cout << "From: ";
cin >> from;
// 權值
int weight = 0;
cout << "Weight:";
cin >> weight;
// 終點
int to = 0;
cout << "To: ";
cin >> to;
cout << endl;
addEdgeToList(from, weight, to);
}
}
void GraphList::addEdgeToList(int vFrom, int weight, int vTo)
{
Edge* edge = new Edge();
edge->vName = vTo;
edge->weight = weight;
edge->next = NULL;
Edge* tmp = m_vVertex[vFrom].next;
if (tmp){
while(tmp->next){
tmp = tmp->next;
}
tmp->next = edge;
}else{
m_vVertex[vFrom].next = edge;
}
++m_vVertex[vTo].in; // 終點入度加1
++m_vVertex[vFrom].out; // 起點初度加1
}
void GraphList::printGraph()
{
for (int i = 0; i < m_vCount; ++i){
Edge* tmp = m_vVertex[i].next;
cout << "list:" << m_vVertex[i].vName << "(in:" << m_vVertex[i].in << ")"<< "->";
while(tmp){
cout << "(weight:" << tmp->weight << ")";
cout << tmp->vName << "->";
tmp = tmp->next;
}
cout << "NULL" << endl;
}
}
bool GraphList::topsortInDegree()
{
stack vertexStack;
queue vertexQueue;
int* degree = new int[m_vCount];// 聲明一個臨時變量，保存入度值，作操作，避免影響原始節點中的數據
// 1 統計入度為0的點
for(int i = 0; i < m_vCount; ++i){
degree[i] = m_vVertex[i].in;
if(!degree[i]){
vertexStack.push(&m_vVertex[i]);
}
}
int count = 0;
while(!vertexStack.empty()){
// 保存入度為0的點
Vertex* tmp = vertexStack.top();
vertexStack.pop();
vertexQueue.push(tmp);
++count;
// 2 從圖中刪除該結點以及它的所有出邊（即與之相鄰點入度減1）
Edge* edge = tmp->next;
while(edge){
Vertex* vertex = &m_vVertex[edge->vName];
--degree[edge->vName];
if (!degree[edge->vName]){
vertexStack.push(vertex);
}
edge = edge->next;
}
}
// 判斷是否有環
if (count < m_vCount) {
return false;
}
// 輸出排序結果
while(!vertexQueue.empty()){
Vertex* tmp = vertexQueue.front();
vertexQueue.pop();
cout << tmp->vName << " ";
}
cout << endl;
delete[] degree;
return true;
}
// **************************************************************************
// 流程控制
// **************************************************************************
void GraphList::createGraph()
{
inputVertexCount();
makeVertexArray();
inputEdgeCount();
inputEdgeInfo();
}
// main.cpp
// test for GraphList
#include "GraphList.h"
#include
int main()
{
GraphList graph;
graph.createGraph();
graph.printGraph();
graph.topsort();
system("pause");
return 0;
}
假如有圖如下：（就是用的前面兩節的圖）
結果：
