1、圖,圖（Graph）是一種較線性表和樹更為復雜的非線性結(jié)構(gòu)。在線性結(jié)構(gòu)中，結(jié)點之間的關(guān)系是線性關(guān)系，除開始結(jié)點和終端結(jié)點外，每個結(jié)點只有一個直接前趨和直接后繼。在樹形結(jié)構(gòu)中，結(jié)點之間的關(guān)系實質(zhì)上是層次關(guān)系，同層上的每個結(jié)點可以和下一層的零個或多個結(jié)點（即孩子）相關(guān)，但只能和上一層的一個結(jié)點（即雙親）相關(guān)（根結(jié)點除外）。然而在圖結(jié)構(gòu)中，對結(jié)點（圖中常稱為頂點）的前趨和后繼個數(shù)都是不加限制的，即結(jié)點之間的關(guān)系是任意的。圖中任意兩個結(jié)點之間都可能相關(guān)。由此，圖的應用極為廣泛，特別是近年來的迅速發(fā)展，已滲透到諸如語言學、邏輯學、物理、化學、電訊工程、計算機科學以及數(shù)學的其它分支中。,基本定義和術(shù)語,若

2、圖G中的每條邊都是有方向的，則稱G為有向圖（Digraph）。在有向圖中，一條有向邊是由兩個頂點組成的有序?qū)?，有序?qū)νǔＳ眉饫ㄌ柋硎?。例如，vi，vj表示一條有向邊，vi是邊的始點（起點），vj是邊的終點。因此，vi，vj和vj，vi是兩條不同的有向邊。有向邊也稱為?。ˋrc），邊的始點稱為弧尾（Tail），終點稱為弧頭（Head）。 圖G由兩個集合V和E組成，記為G(V，E)，其中v是頂點的有窮非空集合，E是V中頂點偶對（稱為邊）的有窮集。通常，也將圖G的頂點集和邊集分別記為V(G)和E(G)。E(G)可以是空集，若E(G)為空，則圖G只有頂點而沒有邊，稱為空圖。,若(vi，vj)是一條無向

3、邊，則稱頂點vi和vj互為鄰接點(Adjacent)，或稱vi和vj相鄰接；稱(vi，vj)關(guān)聯(lián)(Incident)于頂點vi和vj，或稱(vi，vj)與頂點vi和vj相關(guān)聯(lián)。如圖7-1中G2，與頂點vl相鄰接的頂點是v2，v3和v4，而關(guān)聯(lián)于頂點v2的邊是(vl，v2)，(v2，v3)和(v2，v4)。若vi，vj是一條有向邊，則稱頂點vi鄰接到vj,頂點vj鄰接于頂點vi,并稱邊vi，vj關(guān)聯(lián)于vi和vj或稱vi，vj與頂點vi和vj相關(guān)聯(lián)。如圖7-1中Gl，關(guān)聯(lián)于頂點v2的邊是v1，v2，v2，vl和v2,v3。 無向圖中頂點v的度(Degree)是關(guān)聯(lián)于該頂點的邊的數(shù)目，記為D(v)。

4、若G為有向圖，則把以頂點v為終點的邊的數(shù)目，稱為v的人度(1ndegree)，記為ID(v)；把以頂點v為始點的邊的數(shù)目，稱為v的出度(outdegree)，記為OD(v)；頂點v的度則定義為該頂點的入度和出度之和，即D(v)ID(v)十OD(v)。,在無向圖G中，若存在一個頂點序列vp,vi1,vi2，vin，vq，使得(vp，vil)，(vi1,vi2)，(vin，vq)均屬于E(G)，則稱頂點vp到vq存在一條路徑(Path)。若G是有向圖，則路徑也是有向的，它由E(G)中的有向邊vp，vil，vil，vi2，vin，vq組成。路徑長度定義為該路徑上邊的數(shù)目。若一條路徑上除了vp和vq可

5、以相同外；其余頂點均不相同，則稱此路徑為一條簡單路徑。起點和終點相同(vpvq)的簡單路徑稱為簡單回路或簡單環(huán)(Cycle)。例如，在圖G2中頂點序列vl,v2，v3，v4是一條從頂點vl到頂點v4的長度為3的簡單路徑；頂點序列vl,v2，v4，vl，v3是一條從頂點vl到頂點v3的長度為4的路徑，但不是簡單路徑；頂點序列vl，v2，v4，vl是一個長度為3的簡單環(huán)。在有向圖Gl中，頂點序列vl，v2，vl是一個長度為2的有向簡單環(huán)。,在一個有向圖中，若存在一個頂點v，從該頂點有路徑可以到達圖中其它所有頂點，則稱此有向圖為有根圖，v稱作圖的根。 在無向圖G中，若從頂點vi到頂點vj有路徑(當然

6、從vj到vi也一定有路徑)，則稱vi和vj是連通的。若V(G)中任意兩個不同的頂點vi和vj都連通(即有路徑)，則稱G為連通圖(Connected Graph)。例如，圖G2和G3是連通圖。 無向圖G的極大連通子圖稱為G的連通分量(connected Component)。顯然，任何連通圖的連通分量只有一個，即是其自身，而非連通的無向圖有多個連通分量。例如，圖7-4中的G4是非連通圖，它有兩個連通分量Hl和H2。 在有向圖G中，若對于V(G)中任意兩個不同的頂點vi和vj，都存在從vi到vj以及從vj到vi的路徑，則稱G是強連通圖。有向圖G的極大強連通子圖稱為G的強連通分量。顯然，強連通圖只有

7、一個強連通分量，即是其自身。非強連通的有向圖有多個強連通分量。例如圖7-1中的Gl不是強連通圖，因為v3到v2沒有路徑，但它有兩個強連通分量，,若將圖的每條邊都賦上一個權(quán)，則稱這種帶權(quán)圖為網(wǎng)絡(Network)。通常權(quán)是具有某種意義的數(shù).,它們可以表示兩個頂點之間的距離，耗費等,圖的存儲結(jié)構(gòu),鄰接矩陣(Adjacency Matrix)是表示頂點之間相鄰關(guān)系的矩陣。設(shè)G(V，E)是具有n個頂點的圖，則G的鄰接矩陣是具有如下性質(zhì)的n階方陣：,用鄰接矩陣表示法表示圖，除了存儲用于表示頂點間相鄰關(guān)系的鄰接矩陣外，通常還需要用一個順序表來存儲頂點信息。其形式說明如下： # define n 6 / *

8、 圖的頂點數(shù) * / # define e 8 / * 圖的邊（弧）數(shù) */ typedef char vextype； / * 頂點的數(shù)據(jù)類型 * / typedef float adjtype； / * 權(quán)值類型 * / typedef struct vextype vexsn； adjtype arcsnn； graph；,若圖中頂點信息是0至n-1的編號，則僅需令權(quán)值為1，存儲一個鄰接矩陣就可以表示圖。若是網(wǎng)絡，則adjtype為權(quán)的類型。由于無向圖或無向網(wǎng)絡的鄰接矩陣是對稱的，故可采用壓縮存儲的方法，僅存儲下三角陣(不包括對角線上的元素)中的元素即可。顯然，鄰接矩陣表示法的空間復雜度

9、S(n)O(n2)。 CREATGRAPH(ga) * 建立無向網(wǎng)絡 * Graph * ga； int i，j，k； float w； for(i0；in；i+) ga -vexsigetchar()；* 讀入頂點信息，建立頂點表 * for(i0；in；i+) for(j0；jn；j+) ga -arcsij0； * 鄰接矩陣初始化* for(k0；ke；k+) * 讀入e條邊 * (scanf(”ddf”，&I,&j，&w)；*讀入邊(vi，vj)上的權(quán)w * ga -arcsijw； ga - arcsjiw； *CREATGRAPH * 該算法的執(zhí)行時間是O(n+n2+e)，其中O(

10、n2)的時問耗費在鄰接矩陣的初始化操作上。因為en2，所以，算法的時間復雜度是O(n2)。,鄰接表,這種表示法類似于樹的孩子鏈表表示法。 對于圖G中的每個頂點vi，該方法把所有鄰接于vi的頂點vj鏈成一個單鏈表，這個單鏈表就稱為頂點vi的鄰接表(Adjacency List)。鄰接表中每個表結(jié)點均有兩個域，其一是鄰接點域(Adjvex)，用以存放與vi相鄰接的頂點vj的序號；其二是鏈域(Next)，用來將鄰接表的所有表結(jié)點鏈在一起。并且為每個頂點vi的鄰接表設(shè)置一個具有兩個域的表頭結(jié)點：一個是頂點域(vertex)，用來存放頂點vi的信息；另一個是指針域(Link)，用于存入指向vi的鄰接表中

11、第一個表結(jié)點的頭指針。為了便于隨機訪問任一頂點的鄰接表，將所有鄰接表的表頭結(jié)點順序存儲在一個向量中，這樣，圖G就可以由這個表頭向量來表示。,建立有向圖的鄰接表與此類似，只是更加簡單，每讀入一個頂點對序號i，j時，僅需生成十個鄰接點序號為j的邊表結(jié)點，將其插入到vi的出邊表頭部即可。若建立網(wǎng)絡的鄰接表，則需在邊表的每個結(jié)點中增加一個存儲邊上權(quán)的數(shù)據(jù)域。 值得注意的是，一個圖的鄰接矩陣表示是唯一的，但其鄰接表表示不唯一，這是因為鄰接表表示中，各邊表結(jié)點的鏈接次序取決于建立鄰接表的算法以及邊的輸入次序。 鄰接矩陣和鄰接表是圖的兩種最常用的存儲結(jié)構(gòu)，它們各有所長。下面從空間及執(zhí)行某些常用操作的時間這兩

12、方面來作一比較。,在鄰接表(或逆鄰接表)表示中，每個邊表對應于鄰接矩陣的一行(或一列)，邊表中結(jié)點個數(shù)等于一行(或一列)中非零元素的個數(shù)。對于一個具有n個頂點e條邊的圖G，若G是無向圖，則它的鄰接表表示中有n個頂點表結(jié)點和2e個邊表結(jié)點；若G是有向圖，則它的鄰接表表示或逆鄰接表表示中均有n個頂點表結(jié)點和e個邊表結(jié)點。因此鄰接表或逆鄰接表表示的空間復雜度為S(n，e)O(n+e)。若圖中邊的數(shù)目遠遠小于n2(即en2)，此類圖稱作稀疏圖(Sparse Graph)，這時用鄰接表表示比用鄰接矩陣表示節(jié)省存儲空間；若e接近于n2 (準確地說，無向圖e接近于n(n-1)2，有向圖e接近于n(n-1)，

13、此類圖稱作稠密圖(Dense Graph)，考慮到鄰接表中要附加鏈域，則應取鄰接矩陣表示法為宜。,在無向圖中求頂點的度，鄰接矩陣及鄰接表兩種存儲結(jié)構(gòu)都很容易做到：鄰接矩陣中第i行(或第i列)上非零元素的個數(shù)即為頂點vi的度；在鄰接表表示中，頂點vi的度則是第i個邊表中的結(jié)點個數(shù)。在有向圖中求頂點的度。采用鄰接矩陣表示比鄰接表表示更方便：鄰接矩陣中的第i行上非零元素的個數(shù)是頂點vi的出度OD(vi)，第i列上非零元素的個數(shù)是頂點vi的入度ID(vi)，頂點vi的度即是二者之和；在鄰接表表示中，第i個邊表(即出邊表)上的結(jié)點個數(shù)是頂點vi的出度，求vi的入度較困難，需遍歷各頂點的邊表。若有向圖采用

14、逆鄰接表表示，則與鄰接表表示相反，求頂點的入度容易，而求頂點出度較難。 在鄰接矩陣表示中，很容易判定(vi，vj)或vi，vj是否是圖的一條邊，只要判定矩陣中的第i行第j列上的那個元素是否為零即可；但是在鄰接表表示中，需掃描第i個邊表，最壞情況下要耗費O(n)時間。 在鄰接矩陣中求邊的數(shù)目e，必須檢測整個矩陣，所耗費的時間是0(n2)，與e的大小無關(guān)；而在鄰接表表示中，只要對每個邊表的結(jié)點個數(shù)計數(shù)即可求得e，所耗費的時間是0(e+n)。因此，當en2時，采用鄰接表表示更節(jié)省時間。,圖的遍歷,和樹的遍歷類似，圖的遍歷也是從某個頂點出發(fā)，沿著某條搜索路徑對圖中所有頂點各作一次訪問。若給定的圖是連通

15、圖，則從圖中任一頂點出發(fā)順著邊可以訪問到該圖的所有頂點。然而，圖的遍歷比樹的遍歷復雜得多，這是因為圖中的任一頂點都可能和其余頂點相鄰接，故在訪問了某個頂點之后，可能順著某條回路又回到了該頂點。為了避免重復訪問同一個頂點，必須記住每個頂點是否被訪問過。為此，可設(shè)置一個布爾向量visitedn，它的初值為false，一旦訪問了頂點vi，便將visitedi-1置為TRUE。,深度優(yōu)先搜索(Depth-First-Search)遍歷類似于樹的前序遍歷。假設(shè)給定圖G的初態(tài)是所有頂點均未訪問過，在G中任選一頂點vi為初始出發(fā)點，則深度優(yōu)先搜索可定義如下：首先，訪問出發(fā)點vi，并將其標記為已訪問過，然后，

16、依次從vi出發(fā)搜索vi的每一個鄰接點vj,若vj未曾訪問過，則以vj為新的出發(fā)點繼續(xù)進行深度優(yōu)先搜索。顯然上述搜索法是遞歸定義的，它的特點是盡可能先對縱深方向進行搜索，故稱之為深度優(yōu)先搜索。例如，設(shè)x是剛訪問過的頂點，按深度優(yōu)先搜索方法，下一步將選擇一條從x出發(fā)的未檢測過的邊(x，y)。若發(fā)現(xiàn)頂點y已被訪問過，則重新選擇另一條從x出發(fā)的未檢測過的邊。若發(fā)現(xiàn)頂點y未曾訪問過，則沿此邊從x到達y，訪問y并將其標記為已訪問過，然后從y開始搜索，直到搜索完從y出發(fā)的所有路徑，才回溯到頂點x，然后再選擇一條從x出發(fā)的未檢測過的邊。上述過程直至從x出發(fā)的所有邊都已檢測過為止。此時，若x不是初始出發(fā)點，則回

17、溯到在x之前被訪問過的頂點；若x是初始出發(fā)點，則整個搜索過程結(jié)束。顯然這時圖G中所有和初始出發(fā)點有路徑相通的頂點都已被訪問過。因此，若G是連通圖，則從初始出發(fā)點開始的搜索過程結(jié)束，也就意味著完成了對圖G的遍歷。,在該存儲結(jié)構(gòu)上執(zhí)行DFS算法的過程如下：設(shè)初始出發(fā)點是v1，則DFS（0）的執(zhí)行結(jié)果是訪問v1，將其置上已訪問標記，從v1搜索到的第1個鄰接點是v2，因v2未曾訪問過，故調(diào)用DFS(1)。執(zhí)行DFS(1)，首先訪問v2，將其標記為已訪問過，然后從v2搜索到的第1個鄰接點是vl，但vl已訪問過，故繼續(xù)搜索到第2個鄰接點v4，v4未曾訪過，因此調(diào)用DFS(3)。類似地分析，訪問v4后調(diào)用D

18、FS(7)，訪問v：后調(diào)用DPS(4)。執(zhí)行DFS(4)時，在訪問v5并作標記后，從v5搜索到的兩個鄰接點依次是v2和v8，因為它們均已被訪問過，所以DFS(4)執(zhí)行結(jié)束返回，回溯到v8。又因為v8的兩個鄰接點已搜索過，故DFS(7)亦結(jié)束返回，回溯到v4。類似地由v4回溯到v2。V2的鄰接點vl和v4已搜索過，但v2的第3個鄰接點v5還尚未搜索，故接下來由v2搜索到v5，但因為v5已訪問過，所以DFS(1)也結(jié)束返回，回溯到vl。vl的第1個鄰接點已搜索過，故繼續(xù)從v1搜索到第2個鄰接點v3，因為v3未曾訪問過，故調(diào)用DFS(2)。類似地依次訪問v3，v6，v7后，又由v7依次回溯到v6，v

19、3，vl。此時，vl的所有鄰接點都已搜索過，故DFS(0)執(zhí)行完畢。,寬度優(yōu)先搜索法,寬度優(yōu)先搜索(Breadth-First-Search)遍歷類似于樹的按層次遍歷。設(shè)圖G的初態(tài)是所有頂點均未訪問過，在G中任選一頂點2為初始出發(fā)點，則寬度優(yōu)先搜索的基本思想是：首先訪問出發(fā)點Vi，接著依次訪問vi的所有鄰接點wl，w2，wt，然后，再依次訪問與wl，w2，wt鄰接的所有未曾訪問過的頂點，依此類推，直至圖中所有和初始出發(fā)點v有路徑相通的頂點都已訪問到為止。此時，從vi開始的搜索過程結(jié)束，若G是連通圖則遍歷完成。 顯然，上述搜索法的特點是盡可能先對橫向進行搜索，故稱之為寬度優(yōu)先搜索。設(shè)x和y是兩個

20、相繼被訪問過的頂點，若當前是以x為出發(fā)點進行搜索，則在訪問x的所有未曾訪問過的鄰接點之后，緊接著是以y為出發(fā)點進行橫向搜索，并對搜索到的y的鄰接點中尚未被訪問的頂點進行訪問。也就是說，先訪問的頂點其鄰接點亦先被訪問。為此，需引進隊列保存已訪問過的頂點。,最小生成樹,圖的生成樹不是唯一的，從不同的頂點出發(fā)進行遍歷，可以得到不同的生成樹。對于連通網(wǎng)絡G(V，E)，邊是帶權(quán)的，因而G的生成樹的各邊也是帶權(quán)的。我們把生成樹各邊的權(quán)值總和稱為生成樹的權(quán)，并把權(quán)最小的生成樹稱為G的最小生成樹(Minimun Spanning Tree)。 生成樹和最小生成樹有許多重要的應用。令圖G的頂點表示城市，邊表示連

21、接兩個城市之間的通訊線路。n個城市之間最多可設(shè)立的線路有n(n-1)2條，把n個城市連接起來至少要有n-1條線路，則圖G的生成樹表示了建立通訊網(wǎng)絡的可行方案。如果給圖中的邊都賦予權(quán)，而這些權(quán)可表示兩個城市之間通訊線路的長度或建造代價，那么，如何選擇n-1條線路，使得建立的通訊網(wǎng)絡其線路的總長度最短或總代價最小呢?這就是要構(gòu)造該圖的一棵最小生成樹。,以下我們只討論無向圖的最小生成樹問題。構(gòu)造最小生成樹可以有多種算法，其中大多數(shù)構(gòu)造算法都是利用了最小生成樹的下述性質(zhì)：設(shè)G(V，E)是一個連通網(wǎng)絡，U是頂點集V的一個真子集。若(u，v)是G中所有的一個端點在U(即uU)里、另一個端點不在U(即vV-

22、U)里的邊中，具有最小權(quán)值的一條邊，則一定存在G的一棵最小生成樹包含此邊(u，v)。這個性質(zhì)稱為MST性質(zhì)。MST性質(zhì)可用反證法證明：假設(shè)G的任何一棵最小生成樹中都不含邊(u，v)。設(shè)T是G的一棵最小生成樹，但不包含邊(u，v)。由于T是樹，且是連通的，因此有一條從u到v的路徑；且該路徑上必有一條連接兩個頂點集U和V-U的邊(u，v)，其中uU，vV-U，否則u和v不連通。當把邊(u，v)加入樹T時，得到一個含有邊(u，v)的回路，見圖7-15。刪去邊(u，v)，上述回路即被消除，由此得到另一棵生成樹T，T和T的區(qū)別僅在于用邊(u，v)取代了T中的邊(u，v)。因為(u，v)的權(quán)(u，v)的權(quán)

23、，故T的權(quán)T的權(quán)，因此T也是G的最小生成樹，它包含邊(u，v)，與假設(shè)矛盾!,假設(shè)G(V，E)是連通網(wǎng)絡，為簡單起見，我們用序號1至n來表示頂點集合，即v1，2，n。設(shè)所求的最小生成樹為T(U，TE)，其中U是T的頂點集，TE是T的邊集。并且將G中邊上的權(quán)看做是長度。 Prim算法的基本思想是：首先從v中任取一個頂點u0，將生成樹T置為僅有一個結(jié)點u0的樹，即置Uu0；然后只要U是V的真子集，就在所有那些其一個端點u己在T(即uU)、另一個端點v還未在T(即vVU)的邊中，找一條最短(即權(quán)最小)的邊(u，v)，并把該條邊(u，v)和其不在T中的頂點v，分別并入T的邊集TE和頂點集U。如此進行下

24、去，每次往生成樹里并入一個頂點和一條邊，直到把所有頂點都包括進生成樹T為止。此時，必有UV，TE中有n-1條邊。MST性質(zhì)保證上述過程求得的T(U，TE)是G的一棵最小生成樹。 顯然，Prim算法的關(guān)鍵是如何找到連接U和V-U的最短邊來擴充生成樹T。為直觀解釋方便，設(shè)想在構(gòu)造過程中，T的頂點集U中頂點和邊集TE中的邊均被涂成紅色，U之外的頂點集V-U中的頂點均被涂成藍色，連接紅點和藍點的邊均被涂成紫色，那么最短紫邊就是連接U和V-U的最短邊。,最短路徑,交通網(wǎng)絡中常常提出這樣的問題：從甲地到乙地之間是否有公路連通?在有多條通路的情況下，哪一條路最短? 交通網(wǎng)絡可用帶權(quán)圖來表示。頂點表示城市名稱

25、，邊表示兩個城市有路連通，邊上權(quán)值可表示兩城市之間的距離、交通費或途中所花費的時間等。求兩個頂點之間的最短路徑，不是指路徑上邊數(shù)之和最少，而是指路徑上各邊的權(quán)值之和最小。 另外，若兩個頂點之間沒有邊，則認為兩個頂點無通路，但有可能有間接通路（從其他頂點達到)）。路徑上的開始頂點(出發(fā)點)稱為源點，路徑上的最后一個頂點稱為終點，并假定討論的權(quán)值不能為負數(shù)。,所有頂點對之間的最短路徑,所有頂點對之間的最短路徑是指：對于給定的有向網(wǎng)G=(V,E)，要對G中任意一對頂點有序?qū)、W(VW)，找出V到W的最短距離和W到V的最短距離。解決此問題的一個有效方法是:輪流以每一個頂點為源點，重復執(zhí)行迪杰斯特拉算

26、法n次，即可求得每一對頂點之間的最短路徑,總的時間復雜度為O(n3)。,弗洛伊德算法仍然使用前面定義的圖的鄰接矩陣costn+1n+1來存儲帶權(quán)有向圖。算法的基本思想是:設(shè)置一個nxn的矩陣A(k)，其中除對角線的元素都等于0外，其他元素a(k)ij表示頂點i到頂點j的路徑長度，K表示運算步驟。開始時，以任意兩個頂點之間的有向邊的權(quán)值作為路徑長度，沒有有向邊時，路徑長度為，當K=0時，A (0)ij=arcsij, 以后逐步嘗試在原路徑中加入其他頂點作為中間頂點，如果增加中間頂點后，得到的路徑比原來的路徑長度減少了，則以此新路徑代替原路徑，修改矩陣元素。具體做法為：第一步，讓所有邊上加入中間頂

27、點1，取Aij與Ai1+A1j中較小的值作Aij的值，完成后得到A(1)，第二步，讓所有邊上加入中間頂點2，取Aij與Ai2+A2j中較小的值，完成后得到A(2)，如此進行下去，當?shù)趎步完成后，得到A(n)，A(n)即為我們所求結(jié)果，A(n)ij表示頂點i到頂點j的最短距離。,拓撲排序,通常我們把計劃、施工過程、生產(chǎn)流程、程序流程等都當成一個工程，一個大的工程常常被劃分成許多較小的子工程，這些子工程稱為活動，這些活動完成時，整個工程也就完成了。例如，計算機專業(yè)學生的課程開設(shè)可看成是一個工程，每一門課程就是工程中的活動，圖7-24給出了若干門所開設(shè)的課程，其中有些課程的開設(shè)有先后關(guān)系，有些則沒有

28、先后關(guān)系，有先后關(guān)系的課程必須按先后關(guān)系開設(shè)，如開設(shè)數(shù)據(jù)結(jié)構(gòu)課程之前必須先學完程序設(shè)計基礎(chǔ)及離散數(shù)學，而開設(shè)離散數(shù)學則必須學完高等數(shù)學。在圖7-24（b）中，我們用一種有向圖來表示課程開設(shè)，在這種有向圖中，頂點表示活動，有向邊表示活動的優(yōu)先關(guān)系，這有向圖叫做頂點表示活動的網(wǎng)絡(Active On Vertices)簡稱為AOV網(wǎng)。,在AOV網(wǎng)中，有向邊表示i活動應先于j活動開始，即i活動必須完成后，j活動才可以開始，并稱i為j的直接前驅(qū)，j為i的直接后繼。這種前驅(qū)與后繼的關(guān)系有傳遞性，此外，任何活動i不能以它自己作為自己的前驅(qū)或后繼，這叫做反自反性。從前驅(qū)和后繼的傳遞性和反自反性來看，AOV網(wǎng)

29、中不能出現(xiàn)有向回路（或稱有向環(huán)）。在AOV網(wǎng)中如果出現(xiàn)了有向環(huán)，則意味著某項活動應以自己作為先決條件，這是不對的，工程將無法進行。對程序流程而言，將出現(xiàn)死循環(huán)。因此，對給定的AOV網(wǎng)，應先判斷它是否存在有向環(huán)。判斷AOV網(wǎng)是否有有向環(huán)的方法是對該AOV網(wǎng)進行拓撲排序，將AOV網(wǎng)中頂點排列成一個線性有序序列，若該線性序列中包含AOV網(wǎng)全部頂點，則AOV網(wǎng)無環(huán)，否則，AOV網(wǎng)中存在有向環(huán)，該AOV網(wǎng)所代表的工程是不可行的。,本章小結(jié),圖是一種復雜的非線性結(jié)構(gòu)，具有廣泛的應用背景。本章涉及到的基本概念有： 圖：由兩個集合V和E組成，記為G(V，E)，其中v是頂點的有窮非空集合，E是V中頂點偶對（稱為

30、邊）的有窮集。通常，也將圖G的頂點集和邊集分別記為V(G)和E(G)。E(G)可以是空集，若E(G)為空，則圖G只有頂點而沒有邊，稱為空圖。 有向圖（Digraph）：若圖G中的每條邊都是有方向的，則稱G為有向圖。 無向圖（Undigraph）：若圖G中的每條邊都是沒有方向的，則稱G為無向圖。 無向完全圖(Undirected Complete Graph)：恰好有n(n-1)2條邊的無向圖稱為無向完全圖。 有向完全圖(Directed Complete Graph)：恰有n(n-1)條邊的有向圖稱為有向完全圖。 鄰接點(Adjacent)：若(vi，vj)是一條無向邊，則稱頂點vi和vj互為鄰接點。 度(Degree)：無向圖中頂點v的度是關(guān)聯(lián)于該頂點的邊的數(shù)目。 人度(1ndegree)若G為有向圖，則把以頂點v為