拓撲排序算法-創(chuàng)新互聯(lián)

背景

拓撲排序是啥意思？

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

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

算法流程

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

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

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

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

代碼

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

實戰(zhàn)

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

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

名稱欄目：拓撲排序算法-創(chuàng)新互聯(lián)
分享地址：http://bm7419.com/article30/cdisso.html

成都網站建設公司_創(chuàng)新互聯(lián)，為您提供服務器托管、關鍵詞優(yōu)化、面包屑導航、網站排名、自適應網站、電子商務

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

猜你還喜歡下面的內容