圖最小生成樹課件

第九講1、圖的基本概念復習2、最小生成樹1第九講1、圖的基本概念復習122最小生成樹

1.生成樹在一個無向連通圖G中，其所有頂點和遍歷該圖經(jīng)過的所有邊所構成的子圖G′稱做圖G的生成樹。一個圖可以有多個生成樹，從不同的頂點出發(fā)，采用不同的遍歷順序，遍歷時所經(jīng)過的邊也就不同，例如圖7-12的(b)和(c)為圖7-12(a)的兩棵生成樹。其中(b)是通過DFS得到的，稱為深度優(yōu)先生成樹；(c)是通過BFS得到的，稱為廣度優(yōu)先生成樹。

圖7-12生成樹

3最小生成樹1.生成樹圖7-12生成樹3

按照生成樹的定義，n個頂點的連通網(wǎng)絡的生成樹有n個頂點、n-1條邊。而所有包含n-1條邊及n個頂點的連通圖都是無回路的樹，所以生成樹是連通圖中的極小連通子圖.由于使用不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點出發(fā)，也可能得到不同的生成樹。如深度優(yōu)先生成樹、廣度優(yōu)先生成樹在圖論中，常常將樹定義為一個無回路連通圖。

對于一個帶權的無向連通圖，其每個生成樹所有邊上的權值之和可能不同，我們把所有邊上權值之和最小的生成樹稱為圖的最小生成樹。求圖的最小生成樹有很多實際應用。例如，通訊線路鋪設造價最優(yōu)問題就是一個最小生成樹問題。4按照生成樹的定義，n個頂點的連通網(wǎng)絡的生成樹有假設把n個城市看作圖的n個頂點，邊表示兩個城市之間的線路，每條邊上的權值表示鋪設該線路所需造價。鋪設線路連接n個城市，但不形成回路，這實際上就是圖的生成樹，而以最少的線路鋪設造價連接各個城市，即求線路鋪設造價最優(yōu)問題，實際上就是在圖的生成樹中選擇權值之和最小的生成樹。構造最小生成樹的算法有很多，下面分別介紹克魯斯卡爾(Kruskal)算法和普里姆(Prim)算法。

克魯斯卡爾(Kruskal)算法克魯斯卡爾算法是一種按權值遞增的次序選擇合適的邊來構造最小生成樹的方法。5假設把n個城市看作圖的n個頂點，邊表示兩個城市之間的線假設G=（V，E）是一個具有n個頂點的帶權無向連通圖，T=(U，TE)是G的最小生成樹，其中U是T的頂點集，TE是T的邊集，則構造最小生成樹的過程如下：(1)置U的初值等于V，TE的初值為空集；6假設G=（V，E）是一個具有n個頂點的帶權無向連通圖，T=(2)按權值從小到大的順序依次選取圖G中的邊，若選取的邊未使生成樹T形成回路，則加入TE；若選取的邊使生成樹T形成回路，則將其舍棄。循環(huán)執(zhí)行(2)，直到TE中包含(n-1)條邊為止。

7(2)按權值從小到大的順序依次選取圖G中的邊，若選取的邊未應用克魯斯卡爾算法構造最小生成樹的過程:8應用克魯斯卡爾算法構造最小生成樹的過程:899普里姆(Prim)算法

普里姆算法的基本思想：普里姆算法是另一種構造最小生成樹的算法，它是按逐個將頂點連通的方式來構造最小生成樹的。10普里姆(Prim)算法普里姆算法的基本思想：普里姆算法是另一從連通網(wǎng)絡N={V,E}中的某一頂點u0出發(fā)，選擇與它關聯(lián)的具有最小權值的邊(u0,v)，將其頂點加入到生成樹的頂點集合U中。以后每一步從一個頂點在U中，而另一個頂點不在U中的各條邊中選擇權值最小的邊(u,v),把該邊加入到生成樹的邊集TE中，把它的頂點加入到集合U中。如此重復執(zhí)行，直到網(wǎng)絡中的所有頂點都加入到生成樹頂點集合U中為止。11從連通網(wǎng)絡N={V,E}中的某一頂點u0出發(fā)

假設G=(V，E)是一個具有n個頂點的帶權無向連通圖，T(U，TE)是G的最小生成樹，其中U是T的頂點集，TE是T的邊集，則構造G的最小生成樹T的步驟如下：（1）初始狀態(tài)，TE為空，U={v0}，v0∈V；（2）在所有u∈U，v∈V-U的邊(u，v)∈E中找一條代價最小的邊(u′，v′)并入TE，同時將v′并入U；重復執(zhí)行步驟（2）n-1次，直到U=V為止。12假設G=(V，E)是一個具有n個頂點的帶權無向連通圖在普里姆算法中，為了便于在集合U和(V-U)之間選取權值最小的邊，需要設置兩個輔助數(shù)組closest和lowcost，分別用于存放頂點的序號和邊的權值。對于每一個頂點v∈V-U，closest[v]為U中距離v最近的一個鄰接點，即邊(v，closest[v])是在所有與頂點v相鄰、且其另一頂點j∈U的邊中具有最小權值的邊，其最小權值為lowcost[v]，即lowcost[v]=cost[v][closest[v]]，

13在普里姆算法中，為了便于在集合U和(V-U)之間選取權值最小為實現(xiàn)克魯斯卡爾算法需要設置一維輔助數(shù)組E，按權值從小到大的順序存放圖的邊，數(shù)組的下標取值從0到e-1（e為圖G邊的數(shù)目）。假設數(shù)組E存放圖G中的所有邊，且邊已按權值從小到大的順序排列。n為圖G的頂點個數(shù)，e為圖G的邊數(shù)。

注：克魯斯卡爾算法的時間復雜度與邊數(shù)e有關O(eloge)，該算法適合于求邊數(shù)較少的帶權無向連通圖的最小生成樹。14為實現(xiàn)克魯斯卡爾算法需要設置一維輔助數(shù)組E，按權值從小到大的應用普里姆算法構造最小生成樹的過程:15應用普里姆算法構造最小生成樹的過程:151616采用鄰接表作為存儲結構：設置一個輔助數(shù)組closedge[]：

lowcost域：存放在V-U中各個頂點到集合U中的當前最小權值；

adjvex域：記錄該邊所依附的在U中的頂點注：普里姆算法的時間復雜度為O(n2),與網(wǎng)中的邊數(shù)無關，因此適合于求邊稠密的網(wǎng)的最小生成樹。17采用鄰接表作為存儲結構：注：普里姆算法的時間復雜度為O(n21818191920201.拓撲排序

通常我們把計劃、施工過程、生產(chǎn)流程、程序流程等都當成一個工程，一個大的工程常常被劃分成許多較小的子工程，這些子工程稱為活動。這些活動完成時，整個工程也就完成了。例如，計算機專業(yè)學生的課程開設可看成是一個工程，每一門課程就是工程中的活動，圖7-21給出了若干門所開設的課程，其中有些課程的開設有先后關系，有些則沒有先后關系，有先后關系的課程必須按先后關系開設，如開設數(shù)據(jù)結構課程之前必須先學完程序設計基礎及離散數(shù)學，而開設離散數(shù)學則必須先并行學完高等數(shù)學、程序設計基礎課程。拓撲排序

211.拓撲排序拓撲排序21圖7-21課程名稱及相應的課程安排次序

圖7-22課程安排的AOV網(wǎng)在圖7-22中，我們用一種有向圖來表示課程開設，在這種有向圖中，頂點表示活動，有向邊表示活動的優(yōu)先關系，這有向圖叫做頂點表示活動的網(wǎng)絡(ActivityOnVertices)簡稱為AOV網(wǎng)。22圖7-21課程名稱及相應的課程安排次序圖7-22課程安AOV網(wǎng)——ActivityOnVertexNetwork用頂點表示活動，用弧表示活動間的優(yōu)先關系的有向圖，稱為頂點表示活動的網(wǎng)。AOV網(wǎng)中不能有回路拓撲排序：假設G=(V，E)是一個具有n個頂點的有向圖，V中頂點序列vl，v2，…，vn稱做一個拓撲序列(TopologicalOrder)，當且僅當該頂點序列滿足下列條件：若在有向圖G中存在從頂點vi到vj的一條路徑，則在頂點序列中頂點vi必須排在頂點vj之前。通常，在AOV網(wǎng)中，將所有活動排列成一個拓撲序列的過程叫做拓撲排序(TopologicalSort)。23AOV網(wǎng)——ActivityOnVertexNetwo由于AOV網(wǎng)中有些活動之間沒有次序要求，它們在拓撲序列的位置可以是任意的，因此拓撲排序的結果不唯一。對右圖進行拓撲排序，可得一個拓撲序列：C1，C3，C2，C4，C7，C6，C5也可得到另一個拓撲序列：

C2，C7，C1，C3，C4，C5，C6還可以得到其它的拓撲序列。學生按照任何一個拓撲序列都可以完成所要求的全部課程學習。在AOV網(wǎng)中不應該出現(xiàn)有向環(huán)。因為環(huán)的存在意味著某項活動將以自己為先決條件，顯然無法形成拓撲序列。判定網(wǎng)中是否存在環(huán)的方法：對有向圖構造其頂點的拓撲有序序列，若網(wǎng)中所有頂點都出現(xiàn)在它的拓撲有序序列中，則該AOV網(wǎng)中一定不存在環(huán)。24由于AOV網(wǎng)中有些活動之間沒有次序要求，它們在拓撲序列的進行拓撲排序的算法：(1)在AOV網(wǎng)絡中選一個沒有直接前驅的頂點,并輸出之;(2)從圖中刪去該頂點,同時刪去所有它發(fā)出的有向邊;重復以上(1)、(2)步,直到全部頂點均已輸出，拓撲有序序列形成，拓撲排序完成；或圖中還有未輸出的頂點，但已跳出處理循環(huán)。這說明圖中還剩下一些頂點，它們都有直接前驅，再也找不到?jīng)]有前驅的頂點了。這時AOV網(wǎng)絡中必定存在有向環(huán)。25進行拓撲排序的算法：(1)在AOV網(wǎng)絡中選一個沒有直接前驅的拓撲排序的過程26拓撲排序的過程262727

最后得到的拓撲有序序列為C4,C0,C3,C2,C1,C5

。它滿足圖中給出的所有前驅和后繼關系，對于本來沒有這種關系的頂點，如C4和C2，也排出了先后次序關系。28最后得到的拓撲有序序列為C4,C0,C3在實現(xiàn)拓撲排序的算法中，采用鄰接表作為有向圖的存儲結構，每個頂點設置一個單鏈表，每個單鏈表有一個表頭結點，在表頭結點中增加一個存放頂點入度的域count，這些表頭結點構成一個數(shù)組，表頭結點定義如下：typedefstruct//表頭結點{Vertexdata;//頂點信息

intcount;//存放頂點入度

ArcNode*firstarc;//指向第一條弧}Vnode;

在執(zhí)行拓撲排序的過程中，當某個頂點的入度為零(沒有前驅頂點)時，就將此頂點輸出，同時將該頂點的所有后繼頂點的入度減1，相當于刪除所有以該頂點為尾的弧。為了避免重復檢測頂點的入度是否為零，需要設立一個棧來存放入度為零的頂點。執(zhí)行拓撲排序的算法如下：

29在實現(xiàn)拓撲排序的算法中，采用鄰接表作為有向圖的存儲結構，每個StatusTopologicalSort(ALGraphG){//算法7.12//有向圖G采用鄰接表存儲結構。

//若G無回路，則輸出G的頂點的一個拓撲序列并返回OK，否則ERROR。FindInDegree(G,indegree);//對各頂點求入度indegree[0..vernum-1]InitStack(S);for(i=0;i<G.vexnum;++i)//建零入度頂點棧Sif(!indegree[i])Push(S,i);//入度為0者進棧

count=0;//對輸出頂點計數(shù)

while(!StackEmpty(S)){Pop(S,i);printf(i,G.vertices[i].data);++count;//輸出i號頂點并計數(shù)

for(p=G.vertices[i].firstarc;p;p=p->nextarc){k=p->adjvex;//對i號頂點的每個鄰接點的入度減1if(!(--indegree[k]))Push(S,k);//若入度減為0，則入棧

}}if(count<G.vexnum)returnERROR;//該有向圖有回路

elsereturnOK;}//TopologicalSort30StatusTopologicalSort(ALGraph

【例7-3】請給出圖7-24所示的有向圖G的拓撲排序過程。圖7-24有向圖G及其鄰接矩陣

31【例7-3】請給出圖7-24所示的有向圖G的拓撲排序過程。

【解】依據(jù)拓撲排序算法，將圖7-24中入度為0的兩個頂點l和5相繼入棧；頂點5出棧，輸出，且以頂點5為尾的弧的另一頂點入度減一，如另一頂點2的入度值由2變?yōu)?，另一頂點6的入度值由1變?yōu)?。將入度為0的頂點6入棧；頂點6出棧，輸出，且以頂點6為尾的弧的另一頂點入度減一，如另一頂點4的入度值由2變?yōu)?；依次類推得到拓撲序列：561234，拓撲排序過程棧的變化見圖7-25。入度為0的頂點可以按不同順序入棧，因此還可以得到其它拓撲序列：152364，152634，156234，512364，516234，512634。

圖7-25拓撲排序過程的棧

32【解】依據(jù)拓撲排序算法，將圖7-24中入度為0的兩個頂點l關鍵路徑

如果在有向無環(huán)的帶權有向圖中用有向邊表示一個工程中的各項活動(Activity)

用邊上的權值表示活動的持續(xù)時間(Duration)

用頂點表示事件(Event)則這樣的有向圖叫做用邊表示活動的網(wǎng)絡，簡稱AOE(ActivityOnEdges)網(wǎng)絡。

AOE網(wǎng)是一個帶權的有向無環(huán)圖。AOE網(wǎng)絡在某些工程估算方面非常有用。例如，可以使人們了解：

(1)完成整個工程至少需要多少時間(假設網(wǎng)絡中沒有環(huán))?(2)為縮短完成工程所需的時間,應當加快哪些活動?33關鍵路徑如果在有向無環(huán)的帶權有向圖中33在AOE網(wǎng)絡中,有些活動順序進行，有些活動并行進行。從源點到各個頂點，以至從源點到匯點的有向路徑可能不止一條。這些路徑的長度也可能不同。完成不同路徑的活動所需的時間雖然不同，但只有各條路徑上所有活動都完成了，整個工程才算完成。因此，完成整個工程所需的時間取決于從源點到匯點的最長路徑長度，即在這條路徑上所有活動的持續(xù)時間之和。這條路徑長度最長的路徑就叫做關鍵路徑(CriticalPath)。34在AOE網(wǎng)絡中,有些活動順序進行，有些活動并行進行。因此，圖7-26就是一個AOE網(wǎng)，該網(wǎng)中有11個活動和9個事件。每個事件表示在它之前的活動已經(jīng)完成，在它之后的活動可以開始。如事件v5表示a4和a5活動已經(jīng)完成，a7和a8活動可以開始。每個弧上的權值表示完成相應活動所需要的時間，如完成活動a1需要6天，a8需要7天。圖7-26AOE網(wǎng)

35圖7-26就是一個AOE網(wǎng)，該網(wǎng)中有11個活動和9個事

AOE網(wǎng)常用于表示工程的計劃或進度。由于實際工程只有一個開始點和一個結束點，因此AOE網(wǎng)存在唯一的入度為0的開始點（又稱源點）和唯一的出度為0的結束點（又稱匯點），例如下圖的AOE網(wǎng)從事件v1開始，以事件v9結束。同時AOE網(wǎng)應當是無環(huán)的。

36AOE網(wǎng)常用于表示工程的計劃或進度。由于實際工程定義幾個與計算關鍵活動有關的量：

事件Vi

的最早可能開始時間Ve(i)

是從源點V0到頂點Vi的最長路徑長度。

事件Vi的最遲允許開始時間Vl[i]

是在保證匯點Vn-1在Ve[n-1]時刻完成的前提下，事件Vi

的允許的最遲開始時間。

活動ak的最早可能開始時間e[k]

設活動ak在邊<Vi,Vj>上，則e[k]是從源點V0到頂點Vi

的最長路徑長度。因此,e[k]=Ve[i]。

活動ak的最遲允許開始時間l[k]

l[k]是在不會引起時間延誤的前提下，該活動允許的最遲開始時間。

37定義幾個與計算關鍵活動有關的量：事件Vi的最早可能開始時

l[k]=Vl[j]-dur(<i,j>)。其中，dur(<i,j>)是完成ak所需的時間。

時間余量l[k]-e[k]

表示活動ak的最早可能開始時間和最遲允許開始時間的時間余量。l[k]==e[k]表示活動ak是沒有時間余量的關鍵活動。為找出關鍵活動,需要求各個活動的e[k]與l[k]，以判別是否l[k]==e[k].為求得e[k]與l[k]，需要先求得從源點V0到各個頂點Vi的Ve[i]和Vl[i]。38l[k]=Vl[j]-dur(<從Ve[0]=0開始，向前遞推

<Vj,Vi>

S2,i=1,2,,n-1

其中,S2是所有指向頂點Vi的有向邊<Vj

,Vi

>的集合。 從Vl[n-1]=Ve[n-1]開始，反向遞推

<Vi,Vj>

S1,i=n-2,n-3,,0

其中,S1是所有從頂點Vi

發(fā)出的有向邊<Vi

,Vj

>的集合。 這兩個遞推公式的計算必須分別在拓撲有序及逆拓撲有序的前提下進行。39從Ve[0]=0開始，向前遞推39設活動ak(k=1,2,…,e)在帶權有向邊<Vi

,Vj

>上,它的持續(xù)時間用dur(<Vi

,Vj

>)表示，則有

e[k]=Ve[i]；

l[k]=Vl[j]-

dur(<Vi

,Vj

>)；k=1,2,…,e。這樣就得到計算關鍵路徑的算法。計算關鍵路徑時，可以一邊進行拓撲排序一邊計算各頂點的Ve[i]。為了簡化算法，假定在求關鍵路徑之前已經(jīng)對各頂點實現(xiàn)了拓撲排序，并按拓撲有序的順序對各頂點重新進行了編號。算法在求Ve[i],i=0,1,…,n-1時按拓撲有序的順序計算，在求Vl[i],i=n-1,n-2,…,0時按逆拓撲有序的順序計算。40設活動ak(k=1,2,…,e)在帶權有向邊<

【例7-4】圖7-29是一個具有8個活動和6個事件的AOE網(wǎng)，試求其關鍵路徑。

【解】由ve(i)和vl(i)的遞推公式，依次求出所有事件的最早發(fā)生時間ve(i)和最遲發(fā)生時間vl(i)，如下：圖7-29AOE網(wǎng)

源點V1的最早發(fā)生時間為0，同理最遲發(fā)生時間也為0，由于Ve(i)表示從源點V1到Vi的最長路徑長度，因此Ve(2)=3,同理：Ve(3)=2,從V1到V4有兩條路經(jīng)：V1-V2-V4，和V1-V3-V4，其路徑長度分別為2+3=5，2+4=6，因此Ve(4)=6。41【例7-4】圖7-29是一個具有8個活動和6個事顯然Ve(5)=6,而V1到V6有4條路徑，最長路徑為V1-V3-V4-V6路徑長度為：8，因此Ve(6)=8.42顯然Ve(5)=6,而V1到V6有4條路徑，最長路徑為V1-求Vl(i),應該逆序求得，即有Vl(6)=8開始，應用下面的公式：注意：匯點V6的最早發(fā)生時間和最遲發(fā)生時間相同。由于V5與V6只有一條弧相連，因此Vl(5)=Vl(6)-dur<5,6>=8-1=7。同理Vl(4)=6,Vl(3)=2,Vl(2)=4,Vl(1)=0。43求Vl(i),應該逆序求得，即有Vl(6)=8開始，應用下面4444

求出所有活動的最早開始時間e(i)、最遲開始時間l(i)以及d(i)=l(i)-e(i)，如下：e[k]=Ve[i]；即活動所在弧的起點的最早發(fā)生時間就是活動ak的最早發(fā)生時間，因此45求出所有活動的最早開始時間e(i)、最遲開始時間l(i由于l[k]=Vl[j]-dur(<Vi,Vj>)；k=1,2,…,e。46由于l[k]=Vl[j]-dur(<Vi,Vj顯然關鍵活動為：a2,a5,a747顯然關鍵活動為：a2,a5,a747從以上計算得出，圖7-29中AOE網(wǎng)的關鍵活動為a2，a5，a7，這些活動構成了關鍵路徑，如圖7-30所示：圖7-30AOE網(wǎng)的關鍵路徑48從以上計算得出，圖7-29中AOE網(wǎng)的關鍵活動為a2注意：1.影響關鍵活動的因素是多方面的，任何一項活動持續(xù)時間的改變都會影響關鍵路徑的改變，2.關鍵活動的速度提高是有限度的，只有在不改變網(wǎng)的關鍵路徑的情況下，提高關鍵活動的速度才有效，3.關鍵路徑不是唯一的，4.若網(wǎng)中存在幾條關鍵路徑，那么單單提高一條關鍵路徑上的關鍵活動的速度，還不能導致整個工期的縮短，只有提高同時在幾條關鍵路徑上的活動的速度。49注意：2.關鍵活動的速度提高是有限度的，只有在不改變網(wǎng)的關鍵StatusTopologicalOrder(ALGraphG,Stack&T){//算法7.13//有向網(wǎng)G采用鄰接表存儲結構，求各頂點事件的最早發(fā)生時間ve(全局變量)。

//T為拓撲序列定點棧，S為零入度頂點棧。

//若G無回路，則用棧T返回G的一個拓撲序列，且函數(shù)值為OK，否則為ERROR。FindInDegree(G,indegree);//對各頂點求入度indegree[0..vernum-1]for(intj=0;j<G.vexnum;++j)//建零入度頂點棧Sif(indegree[j]==0)Push(S,j);//入度為0者進棧

InitStack(T);//建拓撲序列頂點棧Tcount=0;for(inti=0;i<G.vexnum;i++)ve[i]=0;//初始化

while(!StackEmpty(S)){Pop(S,j);Push(T,j);++count;//j號頂點入T棧并計數(shù)

for(p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;//對j號頂點的每個鄰接點的入度減1if(--indegree[k]==0)Push(S,k);//若入度減為0，則入棧

if(ve[j]+p->info>ve[k])ve[k]=ve[j]+p->info;}//for*(p->info)=dut(<j,k>)}//while50StatusTopologicalOrder(ALGrapif(count<G.vexnum)returnERROR;//該有向網(wǎng)有回路

elsereturnOK;}//TopologicalOrder51if(count<G.vexnum)returnERRStatusCriticalPath(ALGraphG){//算法7.14//G為有向網(wǎng)，輸出G的各項關鍵活動。if(!TopologicalOrder(G,T))returnERROR;for(a=0;a<G.vexnum;a++)vl[a]=ve[G.vexnum-1];//初始化頂點事件的最遲發(fā)生時間

while(!StackEmpty(T))//按拓撲逆序求各頂點的vl值

for(Pop(T,j),p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;dut=p->info;//dut<j,k>if(vl[k]-dut<vl[j])vl[j]=vl[k]-dut;}for(j=0;j<G.vexnum;++j)//求ee,el和關鍵活動

for(p=G.vertices[j].firstarc;p;p=p->nextarc){k=p->adjvex;dut=p->info;ee=ve[j];el=vl[k]-dut;tag=(ee==el)?'*':'';printf(j,k,dut,ee,el,tag);//輸出關鍵活動

}returnOK;}//CriticalPath52StatusCriticalPath(ALGraphG)19．下面哪一方法可以判斷出一個有向圖是否有環(huán)（回路）A．深度優(yōu)先遍歷B.拓撲排序C.求最短路徑D.求關鍵路徑25．已知有向圖G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓撲序列是（）。A．V1,V3,V4,V6,V2,V5,V7B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7D．V1,V2,V5,V3,V4,V6,V7

26．若一個有向圖的鄰接距陣中,主對角線以下的元素均為零,則該圖的拓撲有序序列（）。A．存在B．不存在

A

ABA5319．下面哪一方法可以判斷出一個有向圖是否有環(huán)（回路）AA27．一個有向無環(huán)圖的拓撲排序序列（）是唯一的。A．一定B．不一定28.在有向圖G的拓撲序列中，若頂點Vi在頂點Vj之前，則下列情形不可能出現(xiàn)的是（）。A．G中有弧<Vi，Vj>B．G中有一條從Vi到Vj的路徑