拓撲排序（Topological Sort）

         一個比較大的工程往往會被劃分成多個子工程進行， 我們把這些子工程稱之為活動。在整個工程中，有些子工程必須在其他一些相關的子工程完成之後才能開始，就是說一個子工程的開始依賴于另外一個子工程的結果，使得一個子工程的結束成為了另外一個子工程開始的先決條件。但是也有一些子工程沒有這樣的制約性的先決條件，它可以在整個工期的任何時候開始和結束。我們可以通過一個有向圖來表示出整個工程中所有子工程之間的先後關系，用圖中的頂點表示子工程，圖中的有向邊代表子工程之間的先後關系，即圖中有向邊的起點所代表的活動是有向邊終點所代表活動的先決工程，隻有當起點的工程完成後才能開始終點對應的工程，沒有邊相連接配接的兩個子工程之間代碼沒有先後關系。我們把這種頂點表示活動， 邊表示活動之間的先後關系的有向圖叫做頂點活動網（Activity On Vertex network）也叫AOV網。 如下圖是一個電影制作的AOV網：

  在上面電影制作的全過程被分解成很多的小工程進行處理， 其中有些工程，比如人員到位進駐場地之前必須确定好場地，演員等。這就是先決條件，而劇本完善和演員确定之間可以同時進行，他們并沒有直接的先後連接配接關系。這樣一張圖就反應了一個電影制作的過程，這也是一張标準的AOV網。

AOV網是一個有向的無環圖，不應該帶有回路也就是環，否則就會出現自己是自己的先決條件的笑話，使得每一個活動都無法進行進而形成死鎖。對于一個AOV網，我們可以把所有的子活動都排列成一個線性的序列， 使其嚴格滿足每個活動的先決活動都排在該活動的前面，這樣一個序列叫做拓撲序列（Topological order），通過AOV網構造拓撲序列的過程叫做拓撲排序，注意拓撲排序後的拓撲序列并不是唯一的，因為有很多活動是可以同時執行的。拓撲排序隻能保證有先後順序關系的活動嚴格按照先後順序執行。

拓撲排序（Topological sort）的過程是這樣的：

1>從所有頂點中找到一個頂點入度為0的頂點。這個要依賴于前期有對每個頂點的入度有所記錄。

2>删除第一步找到的入度為0的頂點為出發點的所有弧，并且将弧所指向的的頂點的入度減一。

3>重複以上兩步，直到所有的頂點的入度均為0即停止。在上述過程中每次找到入度為0的頂點将其輸出，最終輸出的便是一個拓撲序列。此過程可以借助stack或者queue進行。

鄰接表表示的拓撲排序過程如下所示：

typedef struct edge
{
	int AdjVertex;
	edge* Next;
}EdgeNode;

typedef struct vertex
{
	int InDegree;
	int Infos;
	EdgeNode* FirstEdge;
}VertexNode, AdjList[100];

typedef struct graph
{
	AdjList adjlist;
	int vernum, edgenum;
}Graph;

void TopologicalSort(Graph* g)
{
	int count  = 0;
	VertexNode node;
	EdgeNode* tmp = NULL;
	stack<VertexNode> stackver;		// 輔助棧結構

	// 周遊所有頂點，将頂點入度為0的所有頂點都加入棧
	for (int i = 0; i < g->vernum; i++)
	{
		if (g->adjlist[i].InDegree == 0)
		{
			stackver.push(g->adjlist[i]);
		}
	}

	// 循環處理所有頂點入度為0的頂點
	while(!stackver.empty())
	{
		node = stackver.top();
		stackver.pop();
		count++;
		cout << node.Infos << endl;

		int index;
		tmp = node.FirstEdge;
		while(tmp != NULL)	// 周遊頂點為入度為0的頂點，并且處理和其相關的頂點
		{
			index = tmp->AdjVertex;
			g->adjlist[index].InDegree--; // 以該頂點為起點的頂點入度減1
			if (g->adjlist[index].InDegree == 0)
			{ // 判斷相關連的頂點是否成為新的入度為0的點，滿足條件進行入棧
				stackver.push(g->adjlist[index]);
			}
		}
	}

	// 當所有頂點都處理為入度為0，拓撲排序完成
	if (count == g->vernum)
	{
		cout << "Topological sort succeed" << endl;
		return;
	}
	
	// 尚有頂點無法處理說明不是AOV網，是有向帶環圖
	cout << "Topological sort failed" << endl;
}           

鄰接矩陣的拓撲排序代碼：

#define MaxNum 501

int InMark[MaxNum+1];
int map[MaxNum+1][MaxNum+1];

void TopologicalSort()
{
		int cnt = 0;
		while(cnt < MaxNum)
		{
			int index = 0;
			for(int i = 1; i <= MaxNum; i++)
			{
				// 查找入度為0的頂點
				if(InMark[i] == 0)
				{
					index = i;
					break;
				}
			}

			cnt++;
			InMark[index] = -1;	// 标記入度為0的頂點已經處理
			cout << index ;
			if (cnt != MaxNum) cout <<" ";

			// 處理入度為0的頂點相關的頂點
			for(int i = 1; i <= MaxNum; i++)
			{
				if(map[index][i] == 1)
					InMark[i]--;
			}
		}
		cout << endl;
}           

  對于有n個頂點和e條邊的有向圖，建立個頂點的入度的時間複雜度為O(e)，建立入度為0的頂點棧的時間複雜度為O(n)；在拓撲排序的過程中，若每個無向圖的無環，則每個頂點出入棧各一次，入度減一在while語句中共執行e次。是以時間複雜度總的為O(n+e)，對其優化也可以使用優先隊列替換掉stack，使得速度加快。不過當有向圖無環時們也可以利用深度優先周遊進行拓撲排序，因為沒有環，是以從圖中某個頂點進行DFS時，最先找出的頂點是頂點出度為0的頂點。也就是拓撲序列中最後一個頂點，是以DFS記錄下來的是拓撲序列的逆向

利用DFS求拓撲序列的抽象算法可描述為：

  　　　　void DFSTopSort(G，i，T){

    　　　　// i是搜尋的出發點，T是棧

   　　　　 int j；

   　　　　 visited[i]=TRUE； //通路i

   　　　　 for(所有i的鄰接點j) //即<i，j>∈E(G)

   　　　　   if(!visited[j])

    　　　　   DFSTopSort(G，j，T)；

    　　　　  

//以上語句完全類似于DFS算法

    　　　　  Push(&T，i)； //從i出發的搜尋已完成，輸出i

  　　　　  }

DFS版本拓撲排序：

typedef struct edge
{
	int AdjVertex;
	edge* Next;
}EdgeNode;

typedef struct vertex
{
	int InDegree;
	int Infos;
	EdgeNode* FirstEdge;
}VertexNode, AdjList[100];

typedef struct graph
{
	AdjList adjlist;
	int vernum, edgenum;
}Graph;

int Mark[101];			// 标記頂點狀态
stack<int> Toporder;	// 存放生成的拓撲逆序
void DFS(Graph* g, int cur_ver)
{
	Mark[cur_ver] = -1;		// -1頂點處于通路狀态
	EdgeNode* tmp = NULL;

	// tmp指向對應的頂點的鄰接頂點
	tmp = g->adjlist[cur_ver].FirstEdge;

	// 循環遞歸鄰接頂點
	while(tmp != NULL)
	{
		if(Mark[tmp->AdjVertex] == 0)// 目前頂點未被通路
		{
			DFS(g, tmp->AdjVertex);
		}
		else if (Mark[tmp->AdjVertex] == -1)
		{
			// 如果鄰接頂點正在通路 說明有環
			cout << "Graph exist loop" << endl;
			return ;
		}
	}

	// 将周遊生成的頂點加入棧儲存
	Toporder.push(cur_ver);
	Mark[cur_ver] = 1;	// 标記頂點已經處理過
}

void TopologicalSort(Graph* g)
{
	memset(Mark, 0x00, sizeof(Mark));
	for (int i = 0; i < g->vernum; i++)
	{
		if (Mark[i] == 0)
			DFS(g, 1);
	}

	// 列印拓撲序列
	while(!Toporder.empty())
	{
		cout << Toporder.top() << " ";
		Toporder.pop();
	}
	cout << endl;
}
           

當然你也可以根據上面鄰接矩陣的思想不采用遞歸的方式去實作：

#define MaxNum 501
int InMark[MaxNum+1];

for (int i - 1; i < MaxNum; i++)
{
	int j = 1;
	for (j = 1; j < MaxNum; j++)
	{
		if (InMark[j] == 0)
		{
			break;
		}
	}

	if (j == MaxNum) break;

	InMark[j] = 1;
	for (int k = 1; k <= MaxNum; k++)
	{
		if (map[j][k]>0) 
			InMark[k]--;
	}
}