拓?fù)渑判蛩惴?創(chuàng)新互聯(lián)

背景

拓?fù)渑判蚴巧兑馑迹?/p>創(chuàng)新互聯(lián)自2013年創(chuàng)立以來，先為尼河口等服務(wù)建站，尼河口等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為尼河口企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問題。

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

算法流程

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

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

此外還有很多排序方式，可見拓?fù)鋱D的排序有很多選擇，只要滿足執(zhí)行依賴要求都是可行的拓?fù)渑判?。接下來正式分析一下算法流程?/p>

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

代碼

//入度數(shù)組
vectorTopologyDfsSort(graph)
{vectorin_degree(n,0);
	init(in_degree, graph);
	//鄰接表
	unordered_map>map;
	init(map, graph);
	//當(dāng)下可執(zhí)行的節(jié)點(diǎn)集合
	vectorres;
	// 每次跟新的隊(duì)列
	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個(gè)節(jié)點(diǎn)，q中是表示該輪可以執(zhí)行的節(jié)點(diǎn)
		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，那么就可以進(jìn)入下一輪執(zhí)行
				{q.push(id);//入度為0的都可以執(zhí)行
					res.push(id);//入度為0的都可以執(zhí)行
				}
			}
		}
	}
	return res;
}

實(shí)戰(zhàn)

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

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

名稱欄目：拓?fù)渑判蛩惴?創(chuàng)新互聯(lián)
分享地址：http://muchs.cn/article30/cdisso.html

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

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

猜你還喜歡下面的內(nèi)容