背景

拓撲排序是啥意思？

創新互聯自2013年創立以來，先為尼河口等服務建站，尼河口等地企業，進行企業商務咨詢服務。為尼河口企業網站制作PC+手機+微官網三網同步一站式服務解決您的所有建站問題。

拓撲排序是指: 將有向無環圖(DAG)展開為一維的執行序列。DAG顧名思義就是有方向的圖，下面這張圖就簡單說明了啥是有向無環圖。一般人可能用到這個算法的情況不多，但是刷leetcode的課程表問題肯定遇到過，其次搞人工智能的同學靜態圖執行順序也不應該陌生。

算法流程

先簡單分析，從上面的圖可以知道，要執行3節點，依賴0，1， 所以需要先執行完0，1。依次類推可以有一下的執行順序：

• [0,1,2,3,4,5]
• [0,2,1,3,4,5]
• [0,1,2,4,3,5]

此外還有很多排序方式，可見拓撲圖的排序有很多選擇，只要滿足執行依賴要求都是可行的拓撲排序。接下來正式分析一下算法流程：

1. 入度數組：這里需要增加兩個概念：入度和出度，入度是指該節點有幾個輸入，出度是指該節點有幾個輸出。根據上面的鋪墊可以很容易想到，入度為0的節點當下是可以執行的，畢竟他沒有什么依賴。所以我們可以搞一個入度數組，記錄每個節點的入度個數，如果當下的入度個數為0，那么該節點就是當下可以執行。
2. 鄰接表：根據上面的圖我們知道，當0，1節點執行完后，節點2的入度也就變成0了，所以每個節點執行完，都應該更新一波入度數組，那么怎么更新了？這就依賴鄰接表來完成，這里鄰接表是一個map>，其中key是節點名node，value是依賴該key_node的節點們，也就是說把key_node作為入度之一的節點。

代碼

//入度數組
vectorTopologyDfsSort(graph)
{vectorin_degree(n,0);
	init(in_degree, graph);
	//鄰接表
	unordered_map>map;
	init(map, graph);
	//當下可執行的節點集合
	vectorres;
	// 每次跟新的隊列
	queueq;
	for(int i=0; iif(in_degree[i]==0) 
		{	q.push(i);//入度為0的都可以執行
			res.push(i);//入度為0的都可以執行
		}
	}
	//更新
	while(!q.empty())
	{//一輪執行size個節點，q中是表示該輪可以執行的節點
		int size = q.size();
		for(int i=0; i	int exec_node = q.front();
			q.pop();
			//一旦exec_node執行，那么依賴exec_node的node的入度值都可以減一
			vectornodes = map[exec_node];
			for(auto id:nodes)
			{		in_degree[id]--;
				if(in_degree[id]==0)//如果入度為0，那么就可以進入下一輪執行
				{q.push(id);//入度為0的都可以執行
					res.push(id);//入度為0的都可以執行
				}
			}
		}
	}
	return res;
}

實戰

可以參考paddlepaddle源碼中的實現：
paddle/fluid/framework/ir/graph_helper.cc:266L

你是否還在尋找穩定的海外服務器提供商？創新互聯www.cdcxhl.cn海外機房具備T級流量清洗系統配攻擊溯源，準確流量調度確保服務器高可用性，企業級服務器適合批量采購，新人活動首月15元起，快前往官網查看詳情吧

名稱欄目：拓撲排序算法-創新互聯
分享地址：http://vcdvsql.cn/article30/cdisso.html

成都網站建設公司_創新互聯，為您提供服務器托管、關鍵詞優化、面包屑導航、網站排名、自適應網站、電子商務

廣告

聲明：本網站發布的內容（圖片、視頻和文字）以用戶投稿、用戶轉載內容為主，如果涉及侵權請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網站立場，如需處理請聯系客服。電話：028-86922220；郵箱：631063699@qq.com。內容未經允許不得轉載，或轉載時需注明來源： 創新互聯