拓?fù)渑判蚝唵螌?shí)現(xiàn)(C語言)

2021-08-16 16:58 作者:C語言編程__Plus 0人讀過 | 我要投稿

今天刷洛谷的圖時看到好多題都要用圖的拓?fù)渑判?，索性就學(xué)一把，敲一敲代碼學(xué)學(xué)算法也復(fù)習(xí)一下圖的具體操作和棧的使用。

作者：掘金丨MCL

拓?fù)渑判?/h1>
對一個有向無環(huán)圖(Directed Acyclic Graph簡稱DAG)G進(jìn)行拓?fù)渑判?，是將G中所有頂點(diǎn)排成一個線性序列，使得圖中任意一對頂點(diǎn)u和v，若邊<u,v>∈E(G)，則u在線性序列中出現(xiàn)在v之前。通常，這樣的線性序列稱為滿足拓?fù)浯涡?Topological Order)的序列，簡稱拓?fù)湫蛄?。簡單的說，由某個集合上的一個偏序得到該集合上的一個全序，這個操作稱之為拓?fù)渑判颉?/p>

預(yù)備知識

一個較大的工程往往被劃分成許多子工程，我們把這些子工程稱作活動(activity)。在整個工程中，有些子工程(活動)必須在其它有關(guān)子工程完成之后才能開始，也就是說，一個子工程的開始是以它的所有前序子工程的結(jié)束為先決條件的，但有些子工程沒有先決條件，可以安排在任何時間開始。為了形象地反映出整個工程中各個子工程(活動)之間的先后關(guān)系，可用一個有向圖來表示，圖中的頂點(diǎn)代表活動(子工程)，圖中的有向邊代表活動的先后關(guān)系，即有向邊的起點(diǎn)的活動是終點(diǎn)活動的前序活動，只有當(dāng)起點(diǎn)活動完成之后，其終點(diǎn)活動才能進(jìn)行。通常，我們把這種頂點(diǎn)表示活動、邊表示活動間先后關(guān)系的有向圖稱做頂點(diǎn)活動網(wǎng)(Activity On Vertex network)，簡稱AOV網(wǎng)。一個AOV網(wǎng)應(yīng)該是一個有向無環(huán)圖，即不應(yīng)該帶有回路，因?yàn)槿魩в谢芈?，則回路上的所有活動都無法進(jìn)行。如圖3-6是一個具有三個頂點(diǎn)的回路，由<A,B>邊可得B活動必須在A活動之后，由<B,C>邊可得C活動必須在B活動之后，所以推出C活動必然在A活動之后，但由<C,A>邊可得C活動必須在A活動之前，從而出現(xiàn)矛盾，使每一項活動都無法進(jìn)行。這種情況若在程序中出現(xiàn)，則稱為死鎖或死循環(huán)，是必須避免的。在AOV網(wǎng)中，若不存在回路，則所有活動可排列成一個線性序列，使得每個活動的所有前驅(qū)活動都排在該活動的前面，我們把此序列叫做拓?fù)湫蛄?Topological order)，由AOV網(wǎng)構(gòu)造拓?fù)湫蛄械倪^程叫做拓?fù)渑判?Topological sort)。AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏模瑵M足上述定義的任一線性序列都稱作它的拓?fù)湫蛄小?由AOV網(wǎng)構(gòu)造出拓?fù)湫蛄械膶?shí)際意義是：如果按照拓?fù)湫蛄兄械捻旤c(diǎn)次序，在開始每一項活動時，能夠保證它的所有前驅(qū)活動都已完成，從而使整個工程順序進(jìn)行，不會出現(xiàn)沖突的情況。（以上來源百度）簡單說，就是把圖的先后順序排序，由先到后依次排序，其中不能存在環(huán)，最終得到的拓?fù)湫蛄衅鋵?shí)就是完成所有事，求中間所做事的順序。