1拓撲排序

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

無環的有向圖2、AOV(ActivityOnVertices)網絡：用頂點表示活動，用有向弧<Vi,Vj>表示活動間的優先關系。Vi必須先于活動Vj進行。這種有向圖稱為用頂點表示活動的網絡。若<vi,vj>是圖中有向邊，則vi是vj的直接前驅；vj是vi的直接后繼AOV網中不允許有回路，這意味著某項活動不能以自己為先決條件4計劃、施工過程、生產流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分為若干個叫做“活動”的子工程。完成了這些活動，這個工程就可以完成了。例如，計算機專業學生的學習就是一個工程，每一門課程的學習就是整個工程的一些活動。其中有些課程要求先修課程，有些則不要求。這樣在有的課程之間有領先關系，有的課程可以并行地學習。5例課程代號課程名稱先修棵C1C2C3C4C5C6C7C8C9C10C11C12無C1C1,C2C1C3,C4C11C3.C5C3,C6無C9C9C1,C9,C10程序設計基礎離散數學數據結構匯編語言語言的設計和分析計算機原理編譯原理操作系統高等數學線性代數普通物理數值分析C1C2C3C4C5C6C7C8C9C10C11C1261、在AOV中拓撲有序序列：將各個頂點(代表各個活動)排列成一個線性有序的序列，使得AOV網絡中所有應存在的前驅和后繼關系都能得到滿足。拓撲排序——把AOV網絡中各頂點按照它們相互之間的優先關系排列成一個線性序列的過程。檢測AOV網中是否存在環方法：對有向圖構造其頂點的拓撲有序序列，若網中所有頂點都在它的拓撲有序序列中，則該AOV網必定不存在環。二、拓撲排序7C1C2C3C4C5C6C7C8C9C10C11C12拓撲序列：C1--C2--C3--C4--C5--C7--C9--C10--C11--C6--C12--C8或：C9--C10--C11--C6--C1--C12--C4--C2--C3--C5--C7--C8一個AOV網的拓撲序列不是唯一的8BDAC對于有向圖不能求得它的拓撲有序序列。因為圖中存在一個回路{B,C,D}9

輸入AOV網絡。有n個頂點。

1在AOV網絡中選一個沒有直接前驅的頂點，并輸出之。2從圖中刪去該頂點,同時刪去所有它發出的有向邊。3重復以上1、2

步,直到全部頂點均已輸出，拓撲有序序列形成，拓撲排序完成；或圖中還有未輸出的頂點，再也找不到沒有前驅的頂點了。這時AOV網絡中必定存在有向環。abcghdfeabhcdgfe

沒有前驅的頂點刪除頂點及以它為尾的弧

弧頭頂點的入度減1abcghdfe需要設一個數組indegree[w]，記錄頂點的入度數

入度為零的頂點113、AOV網絡的存儲方式--鄰接表表示C0C1C2C3C4C5

C0C1C2C30C4C50012345ind

datafirstarc

1301031adjvexnext305150015012鄰接表結點：typedefstructnode{intadjvex;//頂點域

structnode*next;//鏈域}JD;表頭結點：typedefstructtnode{intind;//入度域

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

AOV網絡的存儲方式--鄰接表表示131把鄰接表中所有入度為0的頂點進棧2棧非空時，輸出棧頂元素Vj并退棧；在鄰接表中查找Vj的直接后繼Vk，把Vk的入度減1；若Vk的入度為0則進棧3重復上述操作直至棧空為止。若棧空時輸出的頂點個數不是n，則有向圖有環；否則，拓撲排序完畢。4、拓撲排序算法實現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