1拓?fù)渑判?/p>

一、概念1、有向無環(huán)圖DAG(DirectedAcyclicGraph)

無環(huán)的有向圖2、AOV(ActivityOnVertices)網(wǎng)絡(luò)：用頂點(diǎn)表示活動(dòng)，用有向弧<Vi,Vj>表示活動(dòng)間的優(yōu)先關(guān)系。Vi必須先于活動(dòng)Vj進(jìn)行。這種有向圖稱為用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)。若<vi,vj>是圖中有向邊，則vi是vj的直接前驅(qū)；vj是vi的直接后繼AOV網(wǎng)中不允許有回路，這意味著某項(xiàng)活動(dòng)不能以自己為先決條件4計(jì)劃、施工過程、生產(chǎn)流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分為若干個(gè)叫做“活動(dòng)”的子工程。完成了這些活動(dòng)，這個(gè)工程就可以完成了。例如，計(jì)算機(jī)專業(yè)學(xué)生的學(xué)習(xí)就是一個(gè)工程，每一門課程的學(xué)習(xí)就是整個(gè)工程的一些活動(dòng)。其中有些課程要求先修課程，有些則不要求。這樣在有的課程之間有領(lǐng)先關(guān)系，有的課程可以并行地學(xué)習(xí)。5例課程代號(hào)課程名稱先修棵C1C2C3C4C5C6C7C8C9C10C11C12無C1C1,C2C1C3,C4C11C3.C5C3,C6無C9C9C1,C9,C10程序設(shè)計(jì)基礎(chǔ)離散數(shù)學(xué)數(shù)據(jù)結(jié)構(gòu)匯編語言語言的設(shè)計(jì)和分析計(jì)算機(jī)原理編譯原理操作系統(tǒng)高等數(shù)學(xué)線性代數(shù)普通物理數(shù)值分析C1C2C3C4C5C6C7C8C9C10C11C1261、在AOV中拓?fù)溆行蛐蛄校簩⒏鱾€(gè)頂點(diǎn)(代表各個(gè)活動(dòng))排列成一個(gè)線性有序的序列，使得AOV網(wǎng)絡(luò)中所有應(yīng)存在的前驅(qū)和后繼關(guān)系都能得到滿足。拓?fù)渑判颉袮OV網(wǎng)絡(luò)中各頂點(diǎn)按照它們相互之間的優(yōu)先關(guān)系排列成一個(gè)線性序列的過程。檢測(cè)AOV網(wǎng)中是否存在環(huán)方法：對(duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐蛄校艟W(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄校瑒t該AOV網(wǎng)必定不存在環(huán)。二、拓?fù)渑判?C1C2C3C4C5C6C7C8C9C10C11C12拓?fù)湫蛄校篊1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8或：C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8一個(gè)AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏?BDAC對(duì)于有向圖不能求得它的拓?fù)溆行蛐蛄小Ｒ驗(yàn)閳D中存在一個(gè)回路{B,C,D}9

輸入AOV網(wǎng)絡(luò)。有n個(gè)頂點(diǎn)。

1在AOV網(wǎng)絡(luò)中選一個(gè)沒有直接前驅(qū)的頂點(diǎn)，并輸出之。2從圖中刪去該頂點(diǎn),同時(shí)刪去所有它發(fā)出的有向邊。3重復(fù)以上1、2

步,直到全部頂點(diǎn)均已輸出，拓?fù)溆行蛐蛄行纬桑負(fù)渑判蛲瓿桑换驁D中還有未輸出的頂點(diǎn)，再也找不到?jīng)]有前驅(qū)的頂點(diǎn)了。這時(shí)AOV網(wǎng)絡(luò)中必定存在有向環(huán)。abcghdfeabhcdgfe

沒有前驅(qū)的頂點(diǎn)刪除頂點(diǎn)及以它為尾的弧

弧頭頂點(diǎn)的入度減1abcghdfe需要設(shè)一個(gè)數(shù)組indegree[w]，記錄頂點(diǎn)的入度數(shù)

入度為零的頂點(diǎn)113、AOV網(wǎng)絡(luò)的存儲(chǔ)方式--鄰接表表示C0C1C2C3C4C5

C0C1C2C30C4C50012345ind

datafirstarc

1301031adjvexnext305150015012鄰接表結(jié)點(diǎn)：typedefstructnode{intadjvex;//頂點(diǎn)域

structnode*next;//鏈域}JD;表頭結(jié)點(diǎn)：typedefstructtnode{intind;//入度域

structnode*link;//鏈域}TD;TDg[M];

AOV網(wǎng)絡(luò)的存儲(chǔ)方式--鄰接表表示131把鄰接表中所有入度為0的頂點(diǎn)進(jìn)棧2棧非空時(shí)，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj的直接后繼Vk，把Vk的入度減1；若Vk的入度為0則進(jìn)棧3重復(fù)上述操作直至棧空為止。若棧空時(shí)輸出的頂點(diǎn)個(gè)數(shù)不是n，則有向圖有環(huán)；否則，拓?fù)渑判蛲戤叀?、拓?fù)渑判蛩惴▽?shí)現(xiàn)14例1234560122inlink5543^^^vexnext3^25^240123456^32104top16toptop150122inlink5543^^^vexnext3^25^240123456^輸出序列：63210416toptop160122inlink5543^^^vexnext3^25^240123456^輸出序列：6321041topp170122inlink5543^^^vexnext2^25^240123456^輸出序列：6321041topp180122inlink5543^^^vexnext2^25^240123456^輸出序列：6321041topp190112inlink5543^^^vexnext2^25^240123456^輸出序列：6321041topp200112inlink5543^^^vexnext2^25^240123456^輸出序列：6321041topp=NULL210112inlink5543^^^vexnext2^25^240123456^輸出序列：61321041toptop220112inlink5543^^^vexnext2^25^240123456^輸出序列：6132104topp230102inlink5543^^^vexnext2^25^240123456^輸出序列：6132104topp4240102inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top250102inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top260002inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top3270002inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top3280002inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top3290001inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p4top3300001inlink5543^^^vexnext2^25^240123456^輸出序列：6132104p=NULL4top3310001inlink5543^^^vexnext2^25^240123456^輸出序列：613321044top3320001inlink5543^^^vexnext2^25^240123456^輸出序列：613321044topp330001inlink5543^^^vexnext1^25^240123456^輸出序列：613321044topp340001inlink5543^^^vexnext1^25^240123456^輸出序列：613321044topp350000inlink5543^^^vexnext1^25^240123456^輸出序列：613321044topp2360000inlink5543^^^vexnext1^25^240123456^輸出序列：613321044topp2370000inlink5543^^^vexnext1^25^240123456^輸出序列：613321044top2p=NULL380000inlink5543^^^vexnext1^25^240123456^輸出序列：6132321044top2p=NULL390000inlink5543^^^vexnext1^25^240123456^輸出序列：6132321044topp=NULL400000inlink5543^^^vexnext1^25^240123456^輸出序列：61324321044top410000inlink5543^^^vexnext1^25^240123456^輸出序列：6132432104topp420000inlink5543^^^vexnext0^25^240123456^輸出序列：6132432104topp5430000inlink5543^^^vexnext0^25^240123456^輸出序列：61324532104topp=NULL440000inlink5543^^^vexnext0^25^240123456^輸出序列：6132432104topp=NULL5450000inlink5543^^^vexnext0^25^240123456^輸出序列：61324532104top5