數(shù)據(jù)結(jié)構(gòu)第七章圖嚴蔚敏

數(shù)據(jù)結(jié)構(gòu)第七章圖嚴蔚敏第1頁，課件共134頁，創(chuàng)作于2023年2月第六章圖第六章圖知識點圖的邏輯結(jié)構(gòu)特征及圖的基本術(shù)語鄰接矩陣和鄰接表兩種圖的存儲結(jié)構(gòu)的特點及適用范圍深度優(yōu)先搜索和廣度優(yōu)先搜索兩種遍歷算法的特點和執(zhí)行過程生成樹和最小生成樹的概念及構(gòu)造最小生成樹的prim和kruskal算法最短路徑的含義及求最短路徑的算法拓撲排序的基本思想和步驟關(guān)鍵路徑法及其在管理科學(xué)中的作用第2頁，課件共134頁，創(chuàng)作于2023年2月第六章圖難點圖的遍歷、最小生成樹、最短路徑、拓樸排序算法的理解關(guān)鍵路徑法求關(guān)鍵活動和關(guān)鍵路徑的方法要求熟練掌握以下內(nèi)容：圖的存儲結(jié)構(gòu)圖的遍歷算法了解以下內(nèi)容：圖的最小生成樹和求最小生成樹算法的基本思想帶權(quán)有向圖的最短路徑問題利用AOV網(wǎng)絡(luò)的拓樸排序問題利用AOE網(wǎng)絡(luò)的關(guān)鍵路徑法第3頁，課件共134頁，創(chuàng)作于2023年2月第六章圖第六章目錄7.1圖的定義和基本術(shù)語7.2圖的存儲方式7.3圖的遍歷7.4最小生成樹7.5最短路徑7.6拓撲排序7.7關(guān)鍵路徑法7.8應(yīng)用實例與分析小結(jié)習(xí)題與練習(xí)第4頁，課件共134頁，創(chuàng)作于2023年2月第六章圖7.1圖的定義和基本術(shù)語圖：圖G由V（G）和E（G）這兩個集合所組成，記為G=（V，E），其中V（G）是頂點（Vertex）的非空集，每個頂點可以標以不同的字符或數(shù)字；E（G）是邊（Edge）的集合，特殊情況下E（G）可以是空集。每個邊由其所連接的兩個頂點表示。無向圖：對于一個圖G，若邊集合E（G）為無向邊的集合，則稱該圖為無向圖。有向圖：對于一個圖G，若邊集合E（G）為有向邊的集合，則稱該圖為有向圖。第5頁，課件共134頁，創(chuàng)作于2023年2月第六章圖圖7.1有向圖與無向圖無向圖G1有向圖G2第6頁，課件共134頁，創(chuàng)作于2023年2月第六章圖完全圖：在一個有n個頂點的無向圖中，若每個頂點到其它（n-1）個頂點都連有一條邊，則圖中共有n(n-1)/2條邊，這種圖稱為完全圖（Completegraph，也稱完備圖）。左圖所示就是n=4的完全圖，它一共有六條邊。第7頁，課件共134頁，創(chuàng)作于2023年2月第六章圖權(quán)和網(wǎng)絡(luò)：有些圖，對應(yīng)每條邊有一相應(yīng)的數(shù)值，這個數(shù)值叫做該邊的權(quán)(Weight)。邊上帶權(quán)的圖稱為帶權(quán)圖，也稱為網(wǎng)絡(luò)(Network)。子圖：設(shè)有兩個圖G=(V,E)和G’=(V’,E’)，若V(G’)是V(G)的子集，且E(G’)是E(G)的子集，則稱G’是G的子圖(Subgraph)。例如圖7.3所示的圖是圖7.1中G1的一些子圖。第8頁，課件共134頁，創(chuàng)作于2023年2月第六章圖圖7.3子圖第9頁，課件共134頁，創(chuàng)作于2023年2月第六章圖頂點的度：圖中與每個頂點相連的邊數(shù)，叫該頂點的度(Degree)。例如圖7.1的圖G1中，頂點①的度數(shù)為2，頂點②的度數(shù)為3，……。入度、出度：對于有向圖，頂點的度分為入度和出度，入度是以該頂點為終點的入邊數(shù)目；出度是以該頂點為起點的出邊數(shù)目，該頂點的度等于其入度和出度之和。例如在圖7.1的圖G2中，頂點①的入度為1，出度為2，而頂點②的入度為1，出度為0，因為有一條邊指向它，而沒有邊從它指出去。第10頁，課件共134頁，創(chuàng)作于2023年2月第六章圖路徑：在一個圖中，若從某頂點Vp出發(fā)，沿一些邊經(jīng)過頂點V1,V2,…,Vm到達，Vq，則稱頂點序列(Vp,V1,V2,…,Vm,Vq)為從Vp到Vq的路徑(Path)。路徑長度：對于無權(quán)的圖，路徑長度指的是沿此路徑上邊的數(shù)目；對于有權(quán)圖，一般是取沿路徑各邊的權(quán)之和作為此路徑的長度。若一條路徑上各頂點均不重復(fù)，即路徑經(jīng)過每一頂點不超過一次，則此路徑叫做簡單路徑。如果從一個頂點出發(fā)又回到該頂點，即Vp與Vq相同，則此路徑叫做環(huán)路（Cycle）。第11頁，課件共134頁，創(chuàng)作于2023年2月第六章圖連通、連通圖：在無向圖中，如果從頂點Vi到頂點Vj之間有路徑，則稱這兩個頂點是連通的。如果圖中任意一對頂點都是連通的，則稱此圖是連通圖(Connectedgraph)。連通分量：例如圖7.1中的圖G1是連通圖。圖7.4中的圖就是非連通圖，非連通圖的每一個極大連通子圖叫連通分量(ConnectedComponent)，此圖包括二個連通分量。第12頁，課件共134頁，創(chuàng)作于2023年2月第六章圖圖7.4非連通圖G第13頁，課件共134頁，創(chuàng)作于2023年2月第六章圖強連通圖和強連通分量：在有向圖G中，如果從頂點Vi到頂點Vj和從頂點Vj到頂點Vi之間都有路徑，則稱這兩個頂點是強連通的。如果圖中任何一對頂點都是強連通的，則此圖叫做強連通圖。非強連通圖的每一個極大強連通子圖叫做強連通分量。圖7.1中的G2不是強連通圖，它有兩個強連通分量，如圖7.5所示。第14頁，課件共134頁，創(chuàng)作于2023年2月第六章圖圖7.5圖G2的強連通分量返回第15頁，課件共134頁，創(chuàng)作于2023年2月第六章圖7.2.1鄰接矩陣鄰接矩陣是表示頂點之間相鄰關(guān)系的矩陣。所謂兩頂點的相鄰關(guān)系即它們之間有邊相連。鄰接矩陣是一個（n×n）階方陣，n為圖的頂點數(shù)，它的每一行分別對應(yīng)圖的各個頂點，它的每一列也分別對應(yīng)圖的各個頂點。我們規(guī)定矩陣的元素為：第16頁，課件共134頁，創(chuàng)作于2023年2月第六章圖圖7.7無向圖的鄰接矩陣第17頁，課件共134頁，創(chuàng)作于2023年2月第六章圖圖7.7有向圖的鄰接矩陣第18頁，課件共134頁，創(chuàng)作于2023年2月第六章圖無向圖的鄰接矩陣是對稱的，如果A[i，j]=1，必有A[j，i]=1。這說明，只輸入和存儲其上三角陣元素即可得到整個鄰接矩陣。一般有向圖的鄰接矩陣是不對稱的，A[i，j]不一定等于A[j，i]。鄰接矩陣用二維數(shù)組即可存儲，定義如下：intadjmatrix=ARRAY[n][n];如果圖的各邊是帶權(quán)的，只需將矩陣中的各個1元素換成相應(yīng)邊的權(quán)即可。第19頁，課件共134頁，創(chuàng)作于2023年2月第六章圖產(chǎn)生無向圖鄰接矩陣算法voidcreatgraph(intadjarray[][]){inti,j,v1,v2,num;scanf(“%d”,&num);/*輸入頂點數(shù)*/if(num>0){for(i=1;i<=num;i++)for(j=1;j<=num;j++)adjarry[i][j]=0;/*矩陣初始化*/do{第20頁，課件共134頁，創(chuàng)作于2023年2月第六章圖產(chǎn)生無向圖鄰接矩陣算法續(xù)scanf(“%d,%d”,&v1,&v2);/*輸入邊*/adjarray[v1][v2]=1;adjarray[v2][v1]=1;}while(v1!=0&&v2!=0);}elsenum=0;retrunnum;}第21頁，課件共134頁，創(chuàng)作于2023年2月第六章圖7.2.2鄰接表鄰接表是圖的一種鏈接存儲結(jié)構(gòu)。在鄰接表結(jié)構(gòu)中，對圖中每個頂點建立一個單鏈表，第i個單鏈表中的結(jié)點表示依附于該頂點Vi的邊，即對于無向圖每個結(jié)點表示與該頂點相鄰接的一個頂點；對于有向圖則表示以該頂點為起點的一條邊的終點。一個圖的鄰接矩陣表示是唯一的，但其鄰接表表示是不唯一的。因為在鄰接表的每個單鏈表中，各結(jié)點的順序是任意的。第22頁，課件共134頁，創(chuàng)作于2023年2月第六章圖圖7.8鄰接表圖7.7中無向圖對應(yīng)的鄰接表第23頁，課件共134頁，創(chuàng)作于2023年2月第六章圖圖7.7中有向圖對應(yīng)的鄰接表第24頁，課件共134頁，創(chuàng)作于2023年2月第六章圖鄰接表中每個表結(jié)點均由兩個域組成，其一是鄰接點域（adjvex），用以存放與頂點Vi相鄰接的頂點在圖中的位置；其二是鏈域（next），用以指向依附于頂點Vi的下一條邊所對應(yīng)的結(jié)點。如果用鄰接表存放網(wǎng)絡(luò)中的信息，則還需要在結(jié)點中增加一個存放權(quán)值的域。在每個鏈表設(shè)一表頭結(jié)點，一般這些表頭結(jié)點本身以向量的形式存儲。第25頁，課件共134頁，創(chuàng)作于2023年2月第六章圖對于無向圖的鄰接表來說，一條邊對應(yīng)兩個單鏈表結(jié)點，鄰接表結(jié)點總數(shù)是邊數(shù)的2倍。在無向圖的鄰接表中，各頂點對應(yīng)的單鏈表的結(jié)點數(shù)（不算表頭結(jié)點）就等于該頂點的度數(shù)。在有向圖鄰接表中，一條弧對應(yīng)一個表結(jié)點，表結(jié)點的數(shù)目和弧的數(shù)目相同。在有向圖鄰接表中，單鏈表的結(jié)點數(shù)就等于相應(yīng)頂點的出度數(shù)。要求有向圖中某頂點的入度數(shù)，需掃視鄰接表的所有單鏈表，統(tǒng)計與頂點標號相應(yīng)的結(jié)點個數(shù)。第26頁，課件共134頁，創(chuàng)作于2023年2月第六章圖鄰接表存儲結(jié)構(gòu)定義#defineMAXVEX30structedgenode{intadjvex;/*鄰接點域*/structedgenode*next;/*鏈域*/};structvexnode{chardata;/*頂點信息*/structedgenode*link;};typedefstructvexnodeadjlist[MAXVEX];第27頁，課件共134頁，創(chuàng)作于2023年2月第六章圖產(chǎn)生無向圖的鄰接表算法voidcreategraph(adjlistg){inte,i,s,d,n;structedgenode*p;printf(“請輸入結(jié)點數(shù)(n)和邊數(shù)(e):\n”);scanf(“%d,%d”,&n,&e);for(i=1;i<=n;i++){printf(“\n請輸入第%d個頂點信息：”,i);scanf(“%c”,&g[i].data);g[i].link=NULL;}for(i=1;i<=e;i++)

第28頁，課件共134頁，創(chuàng)作于2023年2月第六章圖產(chǎn)生無向圖的鄰接表算法續(xù){printf(“\n請輸入第%d條邊起點序號，終點序號：”,i);scanf(“%d,%d”,&s,&d);p=(structedgenode*)malloc(sizeof(edgenode));p→adjvex=d;/*鄰接點序號為d*/

p→next=g[s].link;

g[s].link=p;

/*將新結(jié)點插入頂點Vs邊表的頭部*/p=(structedgenode*)malloc(sizeof(edgenode));p→adjvex=s;/*鄰接點序號為s*/p→next=g[d].link;g[d].link=p;/*將新結(jié)點插入頂點Vd邊表的頭部*/}}返回第29頁，課件共134頁，創(chuàng)作于2023年2月第六章圖7.3.1深度優(yōu)先搜索(DFS)首先訪問圖中某指定起始點Vi，然后由Vi出發(fā)訪問它的任一相鄰接頂點Vj，再從Vj出發(fā)訪問Vj的任一未訪問過的相鄰接頂點Vk，再從Vk出發(fā)進行類似訪問，如此進行下去，直到某頂點已沒有未被訪問過的相鄰接頂點時，則退回一步，退到前一個頂點，找前一個頂點的其它尚未被訪問的相鄰接頂點。如有未訪問過的相鄰接頂點，則訪問此頂點后，再從該頂點出發(fā)向前進行與前述類似的訪問；如退回一步后，前一頂點也沒有未被訪問過的相鄰接頂點，則再向回退一步進行搜索，重復(fù)上述過程，一直到所有頂點均被訪問過為止。第30頁，課件共134頁，創(chuàng)作于2023年2月第六章圖圖7.9圖的遍歷例子第31頁，課件共134頁，創(chuàng)作于2023年2月第六章圖由于圖中的路徑可能有環(huán)路，為了避免重復(fù)訪問某些頂點，設(shè)計圖的搜索算法時，可設(shè)置一個表示頂點是否被訪問過的輔助數(shù)組visited，初始時將數(shù)組元素置零，一旦某頂點Vi被訪問過，則令visited[Vi]=1，以后此頂點即不再訪問。第32頁，課件共134頁，創(chuàng)作于2023年2月第六章圖深度優(yōu)先搜索算法深度優(yōu)先搜索是一種遞歸的過程，可以簡單地將其表示成遞歸的形式，其算法描述如下：DFS(V0){訪問V0頂點;visited[V0]=1;對所有與V0相鄰接的頂點wif(visited[w]==0)DFS(w);}第33頁，課件共134頁，創(chuàng)作于2023年2月第六章圖鄰接表表示的圖的DFS算法intvisited[MAXVEX];voiddfsgraph(adjlistadj,intn){inti;for(i=1;i<=n;i++)visited[i]=0;/*給visited數(shù)組賦初值*/for(i=1;i<=n;i++)if(!visited[i])dfs(adj,i);}第34頁，課件共134頁，創(chuàng)作于2023年2月第六章圖從Vi出發(fā)進行DFS的遞歸算法voiddfs(adjlistadj,intv){structedgenode*p;visited[v]=1;printf(“%d”,v);p=adj[v]→link;while(p!=NULL){if(visited[p→adjvex]==0)dfs(adjlist,p→adjvex);/*從v未訪問的鄰接點出發(fā)進行DFS*/p=p→next;}}第35頁，課件共134頁，創(chuàng)作于2023年2月第六章圖時間復(fù)雜性分析一個有n個頂點、e條邊的圖，在深度優(yōu)先搜索圖的過程中，找鄰接點所需時間為O(e)。對輔助數(shù)組初始化時間為O(n)。因此，當用鄰接表作為圖的存儲結(jié)構(gòu)時，深度優(yōu)先搜索圖的時間復(fù)雜性為O(e+n)。第36頁，課件共134頁，創(chuàng)作于2023年2月第六章圖非遞歸算法從頂點Vi出發(fā)進行深度優(yōu)先遍歷的遞歸過程也可以寫成非遞歸的形式，此時需借助一個堆棧保存被訪問過的結(jié)點，以便回溯時查找已被訪問結(jié)點的未被訪問過的鄰接點。設(shè)堆棧由一個一維數(shù)組構(gòu)成，數(shù)組名為stack，棧頂指針為top,假設(shè)此數(shù)組足夠大,不必考慮溢出的可能。第37頁，課件共134頁，創(chuàng)作于2023年2月第六章圖非遞歸算法#defineMAXVEX100voiddfs(adjlistg，intv,intn)/*從頂點v出發(fā)進行深度優(yōu)先遍歷*/{structvexnode*stack[MAXVEX],*p;intvisited[MAXVEX],top=0;for(i=1;i<=n;i++)visited[i]=0;printf(“%d”,v);p=g[v].link;visited[v]=1;while(top>0||p!=NULL)第38頁，課件共134頁，創(chuàng)作于2023年2月第六章圖非遞歸算法續(xù){while(p!=NULL)if(visited[p->adjvex]==1)p=p->next;else{printf(“%d”,p->adjvex);visited[p->adjvex]=1;top++;stack[top]=p;p=g[p->adjvex].link;}第39頁，課件共134頁，創(chuàng)作于2023年2月第六章圖非遞歸算法續(xù)if(top>0){top--;/*退棧，回溯查找已被訪問結(jié)點的未被訪問過的鄰接點*/p=stack[top];p=p->next;}}}第40頁，課件共134頁，創(chuàng)作于2023年2月第六章圖7.3.2廣度優(yōu)先搜索(BFS)圖的廣度優(yōu)先搜索（BFS）類似于樹的按層次遍歷。廣度優(yōu)先搜索的基本思想是：首先訪問圖中某指定的起始點Vi并將其標記為已訪問過，然后由Vi出發(fā)訪問與它相鄰接的所有頂點Vj、Vk……，并均標記為已訪問過，然后再按照Vj、Vk……的次序，訪問每一個頂點的所有未被訪問過的鄰接頂點，并均標記為已訪問過，下一步再從這些頂點出發(fā)訪問與它們相鄰接的尚未被訪問的頂點，如此做下去，直到所有的頂點均被訪問過為止。第41頁，課件共134頁，創(chuàng)作于2023年2月第六章圖在廣度優(yōu)先搜索中，若對頂點V1的訪問先于頂點V2的訪問，則對V1鄰接頂點的訪問也先于V2鄰接頂點的訪問。就是說廣度優(yōu)先搜索中對鄰接點的尋找具有“先進先出”的特性。因此，為了保證訪問頂點的這種先后關(guān)系，需借助一個隊列暫存那些剛訪問過的頂點。設(shè)此隊列由一個一維數(shù)組構(gòu)成，數(shù)組名為Queue，隊首指針和隊尾指針分別為front和rear。假設(shè)數(shù)組足夠大，不必考慮有溢出的可能性。廣度優(yōu)先搜索不是遞歸過程，不能用遞歸形式。第42頁，課件共134頁，創(chuàng)作于2023年2月第六章圖BFS算法描述BFS(v0){訪問v0頂點；visited[v0]=1;被訪問過的頂點入隊；當隊列非空時，進行下面的循環(huán){（1）被訪問過的頂點出隊；（2）對所有與該頂點相鄰接的頂點wif(visited[w]==0){(a)訪問w頂點；(b)visited[w]=1;(c)w入隊;}}}第43頁，課件共134頁，創(chuàng)作于2023年2月第六章圖鄰接表表示的圖的BFS算法intvisited[MAXVEX];intqueue[MAXVEX];voidbfs(adjlistadj,intv){intfront=0,rear=1,v;structedgenode*p;visited[v]=1;printf(“%d”,v);queue[rear]=v;/*初始頂點入隊*/while(front!=rear)/*隊列不為空*/第44頁，課件共134頁，創(chuàng)作于2023年2月第六章圖鄰接表表示的圖的BFS算法續(xù){front=front+1;v=queue[front];/*按訪問次序出隊列*/p=adj[v]->link;/*找v的鄰接頂點*/while(p!=NULL){if(visited[p->adjvex]==0){visited[p->adjvex]=1;printf(“%d”,p->adjvex);第45頁，課件共134頁，創(chuàng)作于2023年2月第六章圖鄰接表表示的圖的BFS算法續(xù)rear=rear+1;queue[rear]=p->adjvex;}p=p->next;}}}第46頁，課件共134頁，創(chuàng)作于2023年2月第六章圖時間復(fù)雜性分析一個有n個頂點、e條邊的圖，在廣度優(yōu)先搜索圖的過程中，每個頂點至多進一次隊列，圖的搜索過程實質(zhì)上是通過邊來找頂點的過程，找鄰接點所需時間為O(e)。對輔助數(shù)組初始化時間為O(n)。因此，當用鄰接表作為圖的存儲結(jié)構(gòu)時，廣度優(yōu)先搜索圖的時間復(fù)雜性為O(e+n)。返回第47頁，課件共134頁，創(chuàng)作于2023年2月第六章圖7.4最小生成樹在一個無向連通圖G中，如果取它的全部頂點和一部分邊構(gòu)成一個子圖G’，若邊集E(G’)中的邊剛好將圖的所有頂點連通但又不形成環(huán)路，我們就稱子圖G’是原圖G的生成樹（Spanningtree）。生成樹有如下特點：任意兩個頂點之間有且僅有一條路徑；如果再增加一條邊就會出現(xiàn)環(huán)路；如果去掉一條邊此子圖就會變成非連通圖。一個有n個頂點的完全圖，一共存在n(n-2)種不同的生成樹。第48頁，課件共134頁，創(chuàng)作于2023年2月第六章圖對于帶權(quán)的連通圖（連通網(wǎng)）G，其生成樹也是帶權(quán)的。我們把生成樹各邊的權(quán)值總和稱為該生成樹的權(quán)。并且將權(quán)最小的生成樹稱為最小生成樹（MinimumSpanningTree）。具有n個頂點的連通圖的生成樹具有n-1條邊（少于此邊數(shù)不可能將各頂點連通，多于此邊數(shù)則必然要出現(xiàn)環(huán)路）。第49頁，課件共134頁，創(chuàng)作于2023年2月第六章圖圖7.10圖G及其生成樹無向連通圖G生成樹第50頁，課件共134頁，創(chuàng)作于2023年2月第六章圖圖7.10圖G及其生成樹生成樹最小生成樹第51頁，課件共134頁，創(chuàng)作于2023年2月第六章圖7.4.1普里姆(prim)算法假設(shè)G=(V,E)是一個具有n個頂點的連通網(wǎng)絡(luò)，T=(U,TE)是G的最小生成樹，其中U是T的頂點集，TE是T的邊集，U和TE的初值均為空。算法開始時，首先從V中任取一個頂點（假定為V1），將此頂點并入U中，此時最小生成樹頂點集U={V1}；然后從那些其一個端點已在U中，另一個端點仍在U外的所有邊中，找一條最短（即權(quán)值最?。┑倪?，假定該邊為(Vi,Vj),其中Vi∈U，Vj∈V-U,并把該邊(Vi,Vj)和頂點Vj分別并入T的邊集TE和頂點集U；第52頁，課件共134頁，創(chuàng)作于2023年2月第六章圖如此進行下去，每次往生成樹里并入一個頂點和一條邊，直到n-1次后，把所有n個頂點都并入生成樹T的頂點集U中，此時U=V，TE中包含有（n-1）條邊；這樣，T就是最后得到的最小生成樹。普里姆算法中每次選取的邊兩端，總是一個已連通頂點（在U集合內(nèi)）和一個未連通頂點（在U集合外），故這個邊選取后一定能將未連通頂點連通而又保證不會形成環(huán)路。第53頁，課件共134頁，創(chuàng)作于2023年2月第六章圖圖7.11普里姆算法例子第54頁，課件共134頁，創(chuàng)作于2023年2月第六章圖為了便于在頂點集合U和V-U之間選擇權(quán)最小的邊，建立兩個數(shù)組closest和lowcost,closest[i]表示U中的一個頂點，該頂點與V-U中的一個頂點構(gòu)成的邊具有最小的權(quán)；lowcost表示該邊對應(yīng)的權(quán)值。開始，由于U的初值為{1}，所以，closest[i]的值為1，i=2,…n,而lowcost[i]為V1到各頂點的邊中最小的權(quán)值。第55頁，課件共134頁，創(chuàng)作于2023年2月第六章圖普里姆算法voidprim(intc[MAXVEX],intn)/*c表示圖的鄰接矩陣，圖的頂點為{1,2…n}*/{intlowcost[n],closest[n];inti,jk,min;for(i=2,i<=n;i++)/*從頂點V1開始*/{lowcost[i]=c[1][i];closest[i]=1;}for(i=2;i<=n;i++)/*從U之外求離U中某頂點最近的頂點*/第56頁，課件共134頁，創(chuàng)作于2023年2月第六章圖普里姆算法續(xù){min=lowcost[i];k=i;for(j=2;j<=n;j++)if(lowcost[j]<min){min=lowcost[j];k=j;}printf(“(%d,%d)”,k,closest[j]);/*打印生成樹的一條邊*/第57頁，課件共134頁，創(chuàng)作于2023年2月第六章圖普里姆算法續(xù)lowcost[k]=32777;/*k加入到U中*/for(j=2;j<=n;j++)if(c[k][j]<lowcost[j]&&lowcost[j]<32777){lowcost[j]=c[k][j];closest[j]=k;}}}第58頁，課件共134頁，創(chuàng)作于2023年2月第六章圖算法分析該算法中每一步執(zhí)行都要掃描數(shù)組lowcost，在V-U頂點集中找出與U最近的頂點，令其為k，并打印邊（k,closest[k]）。然后將k加入U頂點集合中，并修改數(shù)組lowcost和closest。這里用c表示圖的鄰接矩陣，c[i][j]和c[j][i]是邊(i,j)的權(quán)。第59頁，課件共134頁，創(chuàng)作于2023年2月第六章圖7.4.2克魯斯卡爾（Kruskal）算法假設(shè)G=（V，E）是一個具有n個頂點的連通網(wǎng)絡(luò)，T=(U,TE)是G的最小生成樹，U的初值等于V，即包含有G中的全部頂點，TE的初值為空集。基本思想：將圖G中的邊按權(quán)值從小到大的順序依次選取，若選取的邊使生成樹T不形成環(huán)路，則把它并入TE中，保留作為生成樹T的一條邊，若選取的邊使生成樹T形成環(huán)路，則將其舍棄，如此進行下去，直到TE中包含n-1條邊為止。此時的T即為最小生成樹。第60頁，課件共134頁，創(chuàng)作于2023年2月第六章圖現(xiàn)以圖7.12中(a)圖為例說明此算法。設(shè)此圖是用邊集數(shù)組表示的，邊集數(shù)組是一個結(jié)構(gòu)數(shù)組，數(shù)組中的每個元素表示一條邊，組成每條邊的是三元組序列（邊的起始頂點、邊的終止頂點、邊的權(quán)值）。將每條邊的數(shù)據(jù)輸入之后，按權(quán)值的大小進行了排序，如圖7.12(b)所示。這樣，按權(quán)值由小到大選取各邊就是在數(shù)組中按下標由1到e(圖中邊的數(shù)目)的次序選取。第61頁，課件共134頁，創(chuàng)作于2023年2月第六章圖圖7.12克魯斯卡爾算法例子(a)帶權(quán)圖第62頁，課件共134頁，創(chuàng)作于2023年2月第六章圖(b)邊集數(shù)組第63頁，課件共134頁，創(chuàng)作于2023年2月第六章圖(c)最小生成樹第64頁，課件共134頁，創(chuàng)作于2023年2月第六章圖在選取某邊時如何判斷是否與已保留的邊形成環(huán)路？克魯斯卡爾算法是通過將各頂點劃分為集合的辦法來解決的。開始時假定n個頂點分屬于n個集合，即每個集合中有一個頂點，當確定某條邊保留作為生成樹的一條邊時，就將該邊兩端點所屬的兩集合合并為一個，表示原來屬于兩個集合的各個頂點已被這條新的邊連通。如果取到某條邊，發(fā)現(xiàn)它的兩個端點已屬于同一集合時，此邊則應(yīng)當舍去。因為兩個頂點屬于同一集合說明它們已連通，若再添上這條邊就會出現(xiàn)環(huán)路。第65頁，課件共134頁，創(chuàng)作于2023年2月第六章圖如此進行下去，到所有的頂點均已屬于一個集合時，此最小生成樹就構(gòu)成了。用一個set[]數(shù)組來表示頂點，set的初值為s[i]=0(i=1,2,…,n),表示各頂點自成一個分量。當從邊集數(shù)組中按次序選取一條邊時，查找它的兩個頂點所屬的分量，當這兩個分量不相等，則表明所選的這條邊的兩個頂點分屬不同的集合，該邊加入到生成樹中不會形成環(huán)路，應(yīng)作為生成樹的一條邊，同時合并這兩個分量為一個連通分量。若這兩個分量相等，則表明這條邊的兩個頂點同屬一個集合，將此邊加入到生成樹必產(chǎn)生環(huán)路，應(yīng)予放棄。第66頁，課件共134頁，創(chuàng)作于2023年2月第六章圖利用克魯斯卡爾構(gòu)造最小生成樹的邊集數(shù)組結(jié)構(gòu)定義如下：#defineMAXE100structedges/*邊集類型，存儲一邊條的起始頂點為bv,終止頂點為tv和權(quán)w*/{intbv,tv,w;}typedefstructedgesedgeset[MAXE];第67頁，課件共134頁，創(chuàng)作于2023年2月第六章圖查找一個頂點所屬的分量函數(shù)如下：intseeks(intset[],intv){inti=v;while(set[i]>0)i=set[i];return(i);}第68頁，課件共134頁，創(chuàng)作于2023年2月第六章圖克魯斯卡爾算法voidkruskal(edgesetge,intn,inte)/*ge為權(quán)按從小到大排序的邊集數(shù)組*/{intset[MAXE],v1,v2,i,j;for(i=1;i<=n;i++)set[i]=0;/*給set中每個元素賦初值*/i=1;/*i表示獲取的生成樹中的邊數(shù)，初值為1*/j=1;/*j表示ge中的下標，初始值為1*/while(j<n&&i<=e)/*檢查該邊是否加入到生成樹中*/{v1=seeks(set,ge[i].bv);第69頁，課件共134頁，創(chuàng)作于2023年2月第六章圖克魯斯卡爾算法續(xù)v2=seeks(set,ge[i].tv);if(v1!=v2)/*當v1,v2不在同一集合，該邊加入生成樹*/{printf(“(%d,%d)”,ge[i].bv,ge[i].tv);set[v1]=v2;j++;}i++;}}返回第70頁，課件共134頁，創(chuàng)作于2023年2月第六章圖7.5最短路徑所謂最短路徑（shortestpath）問題指的是：如果從圖中某頂點出發(fā)（此點稱為源點），經(jīng)圖的邊到達另一頂點（稱為終點）的路徑不止一條，如何找到一條路徑使沿此路徑上各邊的權(quán)值之和為最小。設(shè)一有向網(wǎng)絡(luò)G=（V,E），已知各邊的權(quán)值，并設(shè)每邊的權(quán)均大于零，以某指定V0為源點，求從V0到圖的其余各點的最短路徑。以圖7.13為例，若指定以頂點V7為源點V0，該圖比較簡單，通過觀察可得到從V7到其余各點的最短路徑。第71頁，課件共134頁，創(chuàng)作于2023年2月第六章圖圖7.13最短路徑例子第72頁，課件共134頁，創(chuàng)作于2023年2月第六章圖狄克斯特拉算法狄克斯特拉于1959年提出了一個按路徑“長度”遞增的次序，逐步得到由給定源點到圖的其余各點間的最短路徑的算法。假設(shè)我們以鄰接矩陣cost表示所研究的有向圖，cost[i][j]表示有向邊<i,j>對應(yīng)權(quán)值，如果兩點之間無相應(yīng)方向的邊，則該元素取為無窮大。在計算機中此矩陣用一個（n×n）二維數(shù)組表示（n為圖的頂點數(shù)），無窮大元素則可用某很大的有限值（如32777）代替。第73頁，課件共134頁，創(chuàng)作于2023年2月第六章圖圖7.13對應(yīng)的鄰接矩陣

第74頁，課件共134頁，創(chuàng)作于2023年2月第六章圖狄克斯特拉算法需要一個頂點集合，初始時集合內(nèi)只有一個源點V0，以后陸續(xù)將已求得最短路徑的頂點加入到集合中，到全部頂點都進入集合了，過程就結(jié)束了。集合可用一維數(shù)組來表示，設(shè)此數(shù)組為S，凡在集合S以外的頂點，其相應(yīng)的數(shù)組元素S[i]為0，否則為1。還需要另一個一維數(shù)組dist，每個頂點對應(yīng)數(shù)組的一個單元，記錄從源點到其他各頂點當前的最短路徑長度，其初值為dist[i]=cost[V0][i]，i=2…n。數(shù)組dist中的數(shù)據(jù)隨著算法的逐步進行要不斷地修改。第75頁，課件共134頁，創(chuàng)作于2023年2月第六章圖定義了S集合和dist數(shù)組并對其初始化后，狄克斯特拉算法在進行中，都是從S之外的頂點集合中選出一個頂點w，使dist[w]的值最小。于是從源點到達w只通過S中的頂點，把w加入集合S中，并調(diào)整dist中記錄的從源點到集合中每個頂點v的距離：從原來的dist[v]和dist[w]+cost[w][v]中，選擇較小的值作為新的dist[v]。重復(fù)上述過程，直到S中包含V中其余各頂點的最短路徑。第76頁，課件共134頁，創(chuàng)作于2023年2月第六章圖狄克斯特拉算法#defineMAXVEX100/*定義最多頂點數(shù)*/voidshortpath(intcost[MAXVEX][MAXVEX],dist[MAXVEX],n,v0){ints[MAXVEX],u,vnum,w,wm;for(w=1;w<=n;w++)/*最短路徑初始化*/{dist[w]=cost[v0][w];}for(w=1;w<=n;w++)s[w]=0;s[v0]=1;/*S中頂點個數(shù)的初值*/vnum=1;第77頁，課件共134頁，創(chuàng)作于2023年2月第六章圖狄克斯特拉算法續(xù)while(vnum<n-1)/*最后一個頂點已無選擇余地*/{wm=32777;u=v0;for(w=1;w<=n;w++)if(s[w]==0&&dist[w]<wm){u=w;wm=dist[w];/*找最小dist[w]*/}s[u]=1;/*u為找到最短路徑的終點*/vnum++;第78頁，課件共134頁，創(chuàng)作于2023年2月第六章圖狄克斯特拉算法續(xù)for(w=1;w<=n;w++)if(s[w]==0&&dist[u]+cost[u][w]<dist[w]){dist[w]=dist[u]+cost[u][w];}/*調(diào)整不在S集合中的頂點的最短路徑*/}for(w=1;w<=n;w++){printf(“%d”,w);printf(“%d”,dist[i]);}}/*輸出結(jié)果*/第79頁，課件共134頁，創(chuàng)作于2023年2月第六章圖狄克斯特拉算法例子以圖7.13所示的圖為例來說明當指定以V7為源點V0后，用狄克斯特拉算法求最短路徑的動態(tài)執(zhí)行情況，其表示集合的數(shù)組S和表示距離的數(shù)組dist元素值的變化如圖7.14所示。第80頁，課件共134頁，創(chuàng)作于2023年2月第六章圖圖7.14算法動態(tài)執(zhí)行情況第81頁，課件共134頁，創(chuàng)作于2023年2月第六章圖返回第82頁，課件共134頁，創(chuàng)作于2023年2月第六章圖7.7拓撲排序在工程實踐中，一個工程項目往往由若干個子項目組成，這些子項目間往往有多種關(guān)系：①先后關(guān)系，即必須在一子項目完成后，才能開始實施另一個子項目；②子項目之間無次序要求，即兩個子項目可以同時進行，互不影響。在工廠中，一件設(shè)備的生產(chǎn)包括許多工序，各工序之間也存在這兩種關(guān)系。學(xué)校里某個專業(yè)的課程學(xué)習(xí)，有些課程是基礎(chǔ)課，它們可以獨立于其它課程，即無前導(dǎo)課程；有些課程必須在一些課程學(xué)完后才能開始學(xué)。第83頁，課件共134頁，創(chuàng)作于2023年2月第六章圖這些類似的問題都可以用有向圖來表示，我們把這些子項目、工序、課程看成一個個頂點稱之為活動(Activity)。如果從頂點Vi到Vj之間存在有向邊<Vi，Vj>,則表示活動i必須先于活動j進行。這種圖稱做頂點表示活動的網(wǎng)絡(luò)(ActivityOnVertexnetwork,簡稱AOV網(wǎng)絡(luò))。例如圖7.15是某校計算機專業(yè)的課程及其相互之間的關(guān)系，它對應(yīng)的AOV網(wǎng)絡(luò)如圖7.17所示。第84頁，課件共134頁，創(chuàng)作于2023年2月第六章圖圖7.15某專業(yè)課程設(shè)置第85頁，課件共134頁，創(chuàng)作于2023年2月第六章圖圖7.17AOV網(wǎng)絡(luò)第86頁，課件共134頁，創(chuàng)作于2023年2月第六章圖在AOV網(wǎng)絡(luò)中，如果頂點Vi的活動必須在頂點Vj的活動以前進行，則稱Vi為Vj的前趨頂點，而稱Vj為Vi的后繼頂點。這種前趨后繼關(guān)系有傳遞性。AOV網(wǎng)絡(luò)中一定不能有有向環(huán)路。例如在圖7.17那樣的有向環(huán)路中，V2是V3的前趨頂點，V1是V2的前趨頂點，V3又是V1的前趨頂點，環(huán)路表示頂點之間的先后關(guān)系進入了死循環(huán)。因此，對給定的AOV網(wǎng)絡(luò)首先要判定網(wǎng)絡(luò)中是否存在環(huán)路，只有有向無環(huán)路網(wǎng)絡(luò)在應(yīng)用中才有實際意義。第87頁，課件共134頁，創(chuàng)作于2023年2月第六章圖圖7.17有向環(huán)路第88頁，課件共134頁，創(chuàng)作于2023年2月第六章圖拓撲排序所謂“拓撲排序”就是將AOV網(wǎng)絡(luò)中的各個頂點(各個活動)排列成一個線性有序序列，使得所有要求的前趨、后繼關(guān)系都能得到滿足。由于AOV網(wǎng)絡(luò)中有些頂點之間沒有次序要求，它們在拓撲有序序列中的位置可以任意顛倒，所以拓撲排序的結(jié)果一般并不是唯一的。通過拓撲排序還可以判斷出此AOV網(wǎng)絡(luò)是否包含有有向環(huán)路，若有向圖G所有頂點都在拓撲排序序列中，則AOV網(wǎng)絡(luò)必定不包含有有向環(huán)路。第89頁，課件共134頁，創(chuàng)作于2023年2月第六章圖拓撲排序方法(1)在網(wǎng)絡(luò)中選擇一個沒有前趨的頂點，并把它輸出；(2)從網(wǎng)絡(luò)中刪去該頂點和從該頂點發(fā)出的所有有向邊；(3)重復(fù)執(zhí)行上述兩步，直到網(wǎng)中所有的頂點都被輸出(此時，原AOV網(wǎng)絡(luò)中的所有頂點和邊就都被刪除掉了)。如果進行到某一步，無法找到無前趨的頂點，則說明此AOV網(wǎng)絡(luò)中存在有向環(huán)路，遇到這種情況，拓撲排序就無法進行了。第90頁，課件共134頁，創(chuàng)作于2023年2月第六章圖圖7.18拓撲排序過程AOV網(wǎng)絡(luò)輸出V3后第91頁，課件共134頁，創(chuàng)作于2023年2月第六章圖輸出V4后輸出V2后輸出V1后輸出V5后第92頁，課件共134頁，創(chuàng)作于2023年2月第六章圖為了實現(xiàn)拓撲排序的算法，對于給定的有向圖，假定采用鄰接表作為它的存儲結(jié)構(gòu)，每個頂點在鄰接表中對應(yīng)一個單鏈表，表示該頂點的各直接后繼頂點。規(guī)定將每個結(jié)點的Data域改為int型，并將每個鏈表的表頭結(jié)點構(gòu)成一個順序表，各表頭結(jié)點的Data域存放相應(yīng)頂點的入度值。每個頂點入度初值可隨鄰接表動態(tài)生成過程中累計得到。例如圖7.18有向圖生成的鄰接表如圖7.19所示。第93頁，課件共134頁，創(chuàng)作于2023年2月第六章圖圖7.19AOV網(wǎng)絡(luò)的鄰接表第94頁，課件共134頁，創(chuàng)作于2023年2月第六章圖在拓撲排序過程中，凡入度為零的頂點即是沒有前趨的頂點，可將其取出列入有序序列中，同時將該頂點從圖中刪除掉不再考慮。刪去一個頂點時，所有它的直接后繼頂點入度均減1，表示相應(yīng)的有向邊也被刪除掉。設(shè)置一個堆棧，將已檢驗到的入度為零的頂點標號進棧，當再出現(xiàn)新的無前趨頂點時，也陸續(xù)將其進棧。每次選入度為零的頂點時，只要取棧頂頂點即可。第95頁，課件共134頁，創(chuàng)作于2023年2月第六章圖設(shè)計算法時，可借用表頭結(jié)點的Data域構(gòu)成一個鏈接堆棧。用該數(shù)據(jù)域存放下一個入度為零的頂點標號，將堆棧中的各個單元鏈接起來，再設(shè)置一個棧頂指針top即可。右圖為表示圖7.19的鏈接堆棧。第96頁，課件共134頁，創(chuàng)作于2023年2月第六章圖用鄰接表存儲AOV網(wǎng)絡(luò)，實現(xiàn)拓撲排序的步驟可描述如下：(1)把鄰接表中所有入度為零的頂點進棧；(2)在棧不空時：①退棧并輸出棧頂?shù)捻旤cj；②在鄰接表的第i個單鏈表中，查找頂點為j的所有直接后繼頂點k，并將頂點k的入度減1。若頂點k的入度為零，則頂點k進棧；③若棧空時輸出的頂點個數(shù)不是n,則有向圖中有環(huán)路，否則拓撲排序完畢。第97頁，課件共134頁，創(chuàng)作于2023年2月第六章圖拓撲排序算法voidtopsort(adjlistadj,intn)/*adj為鄰接表*/{intnum,i,j,top;structvexnode*q;top=0;num=0;/*num指示輸出頂點個數(shù)*/for(i=1;i<=n;i++)/*建立入度為0頂點的堆棧*/{if(adj[i]->data==0){adj[i]->data=top;top=i;}}第98頁，課件共134頁，創(chuàng)作于2023年2月第六章圖拓撲排序算法續(xù)while(top>0){i=top;top=adj[i]->data;/*在鏈表中刪除入度為0的頂點，頂點序號為i*/q=adj[i]->link;printf(“%d”,i);/*輸出頂點Vi并計數(shù)*/num++;while(q!=NULL){j=q->adjvex;adj[j]->data--;/*將后繼結(jié)點j的入度減1*/第99頁，課件共134頁，創(chuàng)作于2023年2月第六章圖拓撲排序算法續(xù)if(adj[j]->data==0){adj[j]->data=top;top=j;}q=p->next;/*找下一個后繼結(jié)點*/}}if(num<n)printf(“網(wǎng)絡(luò)中有環(huán)路!”\n);/*因輸出的頂點數(shù)小于n*/}返回第100頁，課件共134頁，創(chuàng)作于2023年2月第六章圖7.7關(guān)鍵路徑法關(guān)鍵路徑法是采用邊表示活動(ActivityOnEdge)的網(wǎng)絡(luò)，簡稱為AOE網(wǎng)絡(luò)。AOE網(wǎng)絡(luò)是一個帶權(quán)的有向無環(huán)路圖，其中，每個頂點代表一個事件(Event)，事件說明某些活動或某一項活動的完成，即階段性的結(jié)果。離開某頂點的各條邊所代表的活動，只有在該頂點對應(yīng)的事件出現(xiàn)后才能開始。權(quán)值表示活動持續(xù)的時間。第101頁，課件共134頁，創(chuàng)作于2023年2月第六章圖圖7.20一個AOE網(wǎng)絡(luò)第102頁，課件共134頁，創(chuàng)作于2023年2月第六章圖AOE網(wǎng)絡(luò)通常利用AOE網(wǎng)絡(luò)可以研究以下兩個問題：(1)完成整個工程至少需要多少時間？(2)哪些活動是影響工程進度的關(guān)鍵？第103頁，課件共134頁，創(chuàng)作于2023年2月第六章圖關(guān)鍵路徑完成工程所需的時間就是從開始點起進行到結(jié)束點止所需的時間。路徑長度是指沿路徑各邊的權(quán)值之和，也就是這些邊所代表的活動所需時間之和。完成整個工程所需的時間取決于從開始點到結(jié)束點的最長路徑長度，此長度最大的路徑叫做關(guān)鍵路徑。分析關(guān)鍵路徑的目的是辨別哪些是關(guān)鍵活動，以便爭取提高關(guān)鍵活動的效率，縮短整個工期。第104頁，課件共134頁，創(chuàng)作于2023年2月第六章圖在描述關(guān)鍵路徑的算法時，設(shè)活動ai由弧<j,k>表示，要確定如下幾個相關(guān)的量：(1)事件Vj的最早出現(xiàn)時間和活動的最早開始時間：從源點V1到某頂點Vj的最長路徑長度叫作事件j的最早出現(xiàn)時間，表示成ev[j]。頂點Vj的最早出現(xiàn)時間ev[j]決定了從Vj指出的各條邊所代表活動的最早開始時間，因為事件j不出現(xiàn)，它后面的各項活動就不能開始。我們以e[i]表示活動ai的最早開始時間。顯然e[i]=ev[j]。第105頁，課件共134頁，創(chuàng)作于2023年2月第六章圖(2)活動ai的最遲開始時間：在不影響整個工程按時完成的前提下，此項活動最遲的必須開始時間，表示成L[i]。只要某活動ai有L[i]=e[i]的關(guān)系，我們就稱ai為關(guān)鍵活動。關(guān)鍵活動只允許在一個確定的時間開始，再早，它前面的事件還沒出現(xiàn)，尚不能開始；再晚，又會延誤整個工程的按時完成。由于完成整個工程所需的時間是由關(guān)鍵路徑上各邊權(quán)值之和所決定的，顯然關(guān)鍵路徑上各條邊所對應(yīng)的活動都是關(guān)鍵活動。第106頁，課件共134頁，創(chuàng)作于2023年2月第六章圖(3)事件j的最遲出現(xiàn)時間：即事件j在不延誤整個工程的前提下允許發(fā)生的最遲時間，表示為Lv[j]。對某條指向頂點Vj的邊所代表的活動ai可得到：L[i]=Lv[j]-(活動ai所需時間)也就是活動ai必須先于它后面事件的最遲出現(xiàn)時間開始，提前的時間為進行此活動所需的時間。圖7.21所示為活動開始時間與事件出現(xiàn)時間的關(guān)系。第107頁，課件共134頁，創(chuàng)作于2023年2月第六章圖圖7.21活動開始時間與事件出現(xiàn)時間的關(guān)系

第108頁，課件共134頁，創(chuàng)作于2023年2月第六章圖確定關(guān)鍵路徑的方法就是要確定e[i]=L[i]的關(guān)鍵活動。假設(shè)以w[j,k]表示有向邊<j,k>的權(quán)，即此邊對應(yīng)的活動所需的時間，為了求AOE網(wǎng)絡(luò)中活動ai的最早開始時間e[i]和活動ai的最遲開始時間L[i]，先要求得頂點Vk的事件Vk的最早出現(xiàn)時間ev[k]和最遲出現(xiàn)時間Lv[k]。第109頁，課件共134頁，創(chuàng)作于2023年2月第六章圖ev[k]和Lv[k]可以采用下面的遞推公式計算：(1)向匯點遞推由源點的ev[1]=0開始，利用公式：向匯點的方向遞推，可逐個求出各頂點的ev。式中p表示所有指向頂點的邊的集合，如圖7.22所示。第110頁，課件共134頁，創(chuàng)作于2023年2月第六章圖圖7.22集合p此式的意義為：從指向頂點Vk的各邊的活動中取最晚完成的一個活動的完成時間作為Vk的最早出現(xiàn)時間ev[k]。第111頁，課件共134頁，創(chuàng)作于2023年2月第六章圖(2)向源點遞推由上一步的遞推，最后總可求出匯點的最早出現(xiàn)時間ev[n]。因匯點就是結(jié)束點，最遲出現(xiàn)時間與最早出現(xiàn)時間相同，即Lv[n]=ev[n]。從匯點的最遲出現(xiàn)時間Lv[n]開始，利用下面公式：向源點的方向往回遞推，可逐個求出各頂點的最遲出現(xiàn)時間Lv。式中s表示所有由Vj點指出的邊的集合，如圖7.23所示。第112頁，課件共134頁，創(chuàng)作于2023年2月第六章圖圖7.23集合s此公式的意義為：由從Vj頂點指出的各邊所代表的活動中取需最早開始的一個開始時間作為Vj的最遲出現(xiàn)時間。第113頁，課件共134頁，創(chuàng)作于2023年2月第六章圖無論是向匯點遞推還是向源點遞推，都必須按一定的頂點順序進行。對所有的有向邊，向匯點遞推是先求出尾頂點的ev值，再求頭頂點的ev值；向源點遞推則相反，先求頭頂點的Lv值，再求尾頂點的Lv值。為此，可利用上節(jié)介紹的拓撲排序得到的頂點次序進行向匯點的遞推，向源點的遞推按相反的順序進行即可，不必再重新排序。第114頁，課件共134頁，創(chuàng)作于2023年2月第六章圖關(guān)鍵路徑算法(1)輸入e條有向邊<j,k>，建立AOE網(wǎng)絡(luò)的存儲結(jié)構(gòu)；(2)從源點出發(fā)，令ev[1]=0，按拓撲排序的序列求其余各頂點的最早出現(xiàn)時間ev[i](2≤i≤n)。若拓撲排序序列中的頂點個數(shù)小于網(wǎng)絡(luò)中的頂點數(shù)n，則說明網(wǎng)絡(luò)中存在環(huán)路，算法中止執(zhí)行；否則執(zhí)行(3)；第115頁，課件共134頁，創(chuàng)作于2023年2月第六章圖(3)從匯點Vn出發(fā)，令Lv[n]=ev[n]，按逆拓撲排序的序列求其余各頂點的最遲出現(xiàn)時間Lv[i](n-1≥i≥1)；(4)根據(jù)各