數據結構-第七章-圖第一頁，共一百零一頁，2022年，8月28日圖的基本概念圖定義圖是由頂點集合(vertex)及頂點間的關系集合組成的一種數據結構：

Graph＝(V,E)

其中V={x|x某個數據對象}是頂點的有窮非空集合；

E1={(x,y)|x,yV}或E2={<x,y>|x,yV&&Path(x,y)}其中，E1是頂點之間關系的有窮集合，也叫做邊(edge)集合，此時的圖稱為無向圖。E2表示從x到y的一條弧，且稱x為弧尾，y為弧頭，這樣的圖稱為有向圖。第二頁，共一百零一頁，2022年，8月28日有向圖與無向圖

在有向圖中，頂點對 <x,y>是有序的。在無向圖中，頂點對(x,y)是無序的。完全圖

若有n個頂點的無向圖有n(n-1)/2條邊,則此圖為無向完全圖。有n個頂點的有向圖有n(n-1)條邊,則此圖為有向完全圖。00001111222265433第三頁，共一百零一頁，2022年，8月28日

鄰接頂點

如果(u,v)是E(G)中的一條邊，則稱u與v互為鄰接頂點。子圖

設有兩個圖G＝(V,E)和G‘＝(V’,E‘)。若V’V且E‘E,則稱圖G’是圖G的子圖。權

某些圖的邊具有與它相關的數,稱之為權。這種帶權圖叫做網絡。0123子圖0130123023第四頁，共一百零一頁，2022年，8月28日頂點的度

一個頂點v的度是與它相關聯的邊的條數。記作TD(v)。在有向圖中,頂點的度等于該頂點的入度與出度之和。頂點v的入度是以v為終點的有向邊的條數,記作ID(v);頂點v的出度是以v為始點的有向邊的條數,記作OD(v)。路徑

在圖G＝(V,E)中,若從頂點vi出發,沿一些邊經過一些頂點vp1,vp2,…,vpm，到達頂點vj。則稱頂點序列(vivp1vp2...vpmvj)為從頂點vi到頂點vj的路徑。它經過的邊(vi,vp1)、(vp1,vp2)、...、(vpm,vj)應是屬于E的邊。第五頁，共一百零一頁，2022年，8月28日頂點的出度:以頂點v為弧尾的弧的數目;頂點的入度:以頂點v為弧頭的弧的數目。ABECF有向圖頂點的度(TD)=出度(OD)+入度(ID)TD(B)=OD(B)+ID(B)=3例如:第六頁，共一百零一頁，2022年，8月28日路徑長度

非帶權圖的路徑長度是指此路徑上邊的條數。帶權圖的路徑長度是指路徑上各邊的權之和。簡單路徑

若路徑上各頂點v1,v2,...,vm均不互相重復,則稱這樣的路徑為簡單路徑。簡單回路若路徑上第一個頂點v1與最后一個頂點vm重合,則稱這樣的路徑為回路或環。012301230123第七頁，共一百零一頁，2022年，8月28日ABECF如:從A到F長度為3的路徑{A,B,C,F}第八頁，共一百零一頁，2022年，8月28日連通圖與連通分量

在無向圖中,若從頂點v1到頂點v2有路徑,則稱頂點v1與v2是連通的。如果圖中任意一對頂點都是連通的,則稱此圖是連通圖。非連通圖的極大連通子圖叫做連通分量。強連通圖與強連通分量

在有向圖中,若對于每一對頂點vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱此圖是強連通圖。非強連通圖的極大強連通子圖叫做強連通分量。第九頁，共一百零一頁，2022年，8月28日無向圖,若圖中任意兩個頂點之間都有路徑相通，則稱此圖為連通圖;若無向圖為非連通圖，則圖中各個極大連通子圖稱作此圖的連通分量。BACDFEBACDFE第十頁，共一百零一頁，2022年，8月28日有向圖,若任意兩個頂點之間都存在一條有向路徑，則稱此有向圖為強連通圖。否則，其各個強連通子圖稱作它的強連通分量。ABECFABECF第十一頁，共一百零一頁，2022年，8月28日強連通圖與強連通分量

在有向圖中,若對于每一對頂點vi和vj,都存在一條從vi到vj和從vj到vi的路徑,則稱此圖是強連通圖。非強連通圖的極大強連通子圖叫做強連通分量。013425013425第十二頁，共一百零一頁，2022年，8月28日生成樹:假設一個連通圖有n個頂點和e條邊，其中n-1條邊和n個頂點構成一個極小連通子圖，稱該極小連通子圖為此連通圖的生成樹。在極小連通子圖中增加一條邊，則一定有環。在極小連通子圖中去掉一條邊，則成為非連通圖。BACDFEBACDFE第十三頁，共一百零一頁，2022年，8月28日有n個頂點，n-1條邊的圖必定是生成樹嗎？對非連通圖，則稱由各個連通分量的生成樹的集合為此非連通圖的生成森林。BACDFEBACDFE第十四頁，共一百零一頁，2022年，8月28日圖的存儲結構在圖的鄰接矩陣表示中，有一個記錄各個頂點信息的頂點表，還有一個表示各個頂點之間關系的鄰接矩陣。設圖A=(V,E)是一個有n個頂點的圖,圖的鄰接矩陣是一個二維數組A.edge[n][n]，定義：鄰接矩陣(AdjacencyMatrix)第十五頁，共一百零一頁，2022年，8月28日無向圖的鄰接矩陣是對稱的;有向圖的鄰接矩陣可能是不對稱的。0123012第十六頁，共一百零一頁，2022年，8月28日在有向圖中,統計第i行1的個數可得頂點i的出度，統計第j列1的個數可得頂點j的入度。在無向圖中,統計第i行(列)1的個數可得頂點i的度。第十七頁，共一百零一頁，2022年，8月28日186329542031網絡的鄰接矩陣第十八頁，共一百零一頁，2022年，8月28日#defineMaxValueInt_MaxconstintNumEdges=50; //邊條數constintNumVertices=10;//頂點個數typedefcharVertexData;//頂點數據類型

typedefintEdgeData;//邊上權值類型typedefstruct{ VertexDatavexList[NumVertices];//頂點表EdgeDataEdge[NumVertices][NumVertices];

//鄰接矩陣,可視為邊之間的關系intn,e;//圖中當前的頂點個數與邊數}MTGraph;

用鄰接矩陣表示的結構定義第十九頁，共一百零一頁，2022年，8月28日鄰接表(AdjacencyList)鄰接表:是圖的一種鏈式存儲結構。弧的結點結構 adjvex;//該弧所指向的頂點的位置 nextarc;//指向下一條弧指針 info;//該弧相關信息的指針adjvexnextarcinfo頂點的結點結構datafirstarc

data;//頂點信息firstarc;//指向第一條依附該頂點的弧第二十頁，共一百零一頁，2022年，8月28日無向圖的鄰接表

同一個頂點發出的邊鏈接在同一個邊鏈表中，每一個鏈結點代表一條邊(邊結點),結點中有另一頂點的下標dest和指針link。ABCDdataadjABCD0123destlinkdestlink130210第二十一頁，共一百零一頁，2022年，8月28日有向圖的鄰接表和逆鄰接表ABCdataadjABC012destlinkdestlink鄰接表(出邊表)dataadjABC012destlink逆鄰接表(入邊表)102011第二十二頁，共一百零一頁，2022年，8月28日網絡(帶權圖)的鄰接表BACD69528dataadjABCD0123destcostlink1

53

62

83

21

9(出邊表)(頂點表)第二十三頁，共一百零一頁，2022年，8月28日帶權圖的邊結點中保存該邊上的權值cost。頂點i的邊鏈表的表頭指針adj在頂點表的下標為i的頂點記錄中，該記錄還保存了該頂點的其它信息。在鄰接表的邊鏈表中，各個邊結點的鏈入順序任意，視邊結點輸入次序而定。設圖中有n個頂點，e條邊，則用鄰接表表示無向圖時，需要n個頂點結點，2e個邊結點；用鄰接表表示有向圖時，若不考慮逆鄰接表，只需n個頂點結點，e個邊結點。第二十四頁，共一百零一頁，2022年，8月28日圖的鄰接表存儲表示#defineMAX_VERTEX_NUM20typedefstructArcNode{intadjvex;//該弧所指向的頂點的位置structArcNode*nextarc;//指向下一條弧指針InfoType*info;//該弧相關信息的指針}ArcNode;typedefstructVNode{VertexTypedata;//頂點信息ArcNode*firstarc;//指向第一條依附該頂點的弧}VNode,AdjList[MAX_VERTEX_NUM];第二十五頁，共一百零一頁，2022年，8月28日typedefstruct{AdjListvertices;Intvexnum,arcnum;//圖的當前頂點數和弧數Intkind;//圖的種類標志}ALGraph;第二十六頁，共一百零一頁，2022年，8月28日typedefcharVertexData;//頂點數據類型typedefintEdgeData;//邊上權值類型typedefstructnode{//邊結點intdest;//目標頂點下標EdgeDatacost; //邊上的權值Structnode*link;//下一邊鏈接指針}EdgeNode;鄰接表表示的網的定義第二十七頁，共一百零一頁，2022年，8月28日typedefstruct{//頂點結點VertexDatadata;//頂點數據域EdgeNode*firstAdj;//邊鏈表頭指針}VertexNode;

typedefstruct{//圖的鄰接表VertexNodeVexList[NumVertices];//鄰接表intn,e;//圖中當前的頂點個數與邊數}AdjGraph;第二十八頁，共一百零一頁，2022年，8月28日鄰接表的構造算法(無向圖)voidCreateGraph(AdjGraphG){cin>>G.n>>G.e; //輸入頂點個數和邊數for(inti=0;i<G.n;i++){cin>>G.VexList[i].data;//輸入頂點信息G.VexList[i].firstAdj=NULL;}for(i=0;i<e;i++){//逐條邊輸入cin>>tail>>head>>weight;EdgeNode*p=newEdgeNode;p->dest=head;p->cost=weight; 第二十九頁，共一百零一頁，2022年，8月28日

//鏈入第tail號鏈表的前端p->link=G.VexList[tail].firstAdj;G.VexList[tail].firstAdj=p;

p=newEdgeNode;p->dest=tail;p->cost=weight;

//鏈入第head號鏈表的前端p->link=G.VexList[head].firstAdj;G.VexList[head].firstAdj=p;}}第三十頁，共一百零一頁，2022年，8月28日圖的遍歷從圖中某一頂點出發訪遍圖中所有的頂點，且使每個頂點僅被訪問一次，這一過程就叫做圖的遍歷(TraversingGraph)。圖中可能存在回路，且圖的任一頂點都可能與其它頂點相通，在訪問完某個頂點之后可能會沿著某些邊又回到了曾經訪問過的頂點。為了避免重復訪問，可設置一個標志頂點是否被訪問過的輔助數組visited[]。第三十一頁，共一百零一頁，2022年，8月28日輔助數組visited[]的初始狀態為0,在圖的遍歷過程中,一旦某一個頂點i

被訪問,就立即讓visited[i]為1,防止它被多次訪問。兩種圖的遍歷方法:深度優先搜索

DFS(DepthFirstSearch)廣度優先搜索BFS(BreadthFirstSearch)第三十二頁，共一百零一頁，2022年，8月28日深度優先搜索DFS(DepthFirstSearch)深度優先搜索過程67ACDEGBFIHACDEGBFIH1234589123456789前進回退深度優先生成樹第三十三頁，共一百零一頁，2022年，8月28日DFS在訪問圖中某一起始頂點v后,由v出發,訪問它的任一鄰接頂點w1;再從w1出發,訪問與w1鄰接但還沒有訪問過的頂點w2;然后再從w2出發,進行類似的訪問,…如此進行下去,直至到達所有的鄰接頂點都被訪問過的頂點u為止。接著,退回一步,退到前一次剛訪問過的頂點,看是否還有其它沒有被訪問的鄰接頂點。如果有,則訪問此頂點,之后再從此頂點出發,進行與前述類似的訪問;如果沒有,就再退回一步進行搜索。重復上述過程,直到連通圖中所有頂點都被訪問過為止。第三十四頁，共一百零一頁，2022年，8月28日

圖的深度優先搜索算法voidGraph_Traverse(AdjGraphG){ int*visited=newint[NumVertices];for(inti=0;i<G.n;i++)visited[i]=0;//訪問數組visited初始化for(inti=0;i<G.n;i++)if(!visited[i])DFS(G,i,visited);

//從頂點i出發開始搜索delete[]visited;//釋放visited}第三十五頁，共一百零一頁，2022年，8月28日voidDFS(AdjGraphG,intv,intvisited[]){cout<<GetValue(G,v)<<‘’;//訪問頂點vvisited[v]=1; //頂點v作訪問標記intw=GetFirstNeighbor(G,v);

//取v的第一個鄰接頂點wwhile(w!=-1){ //若鄰接頂點w存在if(!visited[w])DFS(G,w,visited);

//若頂點w未訪問過,遞歸訪問頂點ww=GetNextNeighbor(G,v,w);

//取頂點v排在w后的下一個鄰接頂點}} 第三十六頁，共一百零一頁，2022年，8月28日廣度優先搜索BFS(BreadthFirstSearch)廣度優先搜索過程ACDEGBFIHACDEGBFH123456789123456789廣度優先生成樹I第三十七頁，共一百零一頁，2022年，8月28日BFS在訪問了起始頂點v之后,由v出發,依次訪問v的各個未被訪問過的鄰接頂點w1,w2,…,wt,然后再順序訪問w1,w2,…,wt的所有還未被訪問過的鄰接頂點。再從這些訪問過的頂點出發，再訪問它們的所有還未被訪問過的鄰接頂點，…如此做下去，直到圖中所有頂點都被訪問到為止。廣度優先搜索是一種分層的搜索過程,每向前走一步可能訪問一批頂點,不像深度優先搜索那樣有往回退的情況。因此,廣度優先搜索不是一個遞歸的過程。第三十八頁，共一百零一頁，2022年，8月28日為了實現逐層訪問,算法中使用了一個隊列,以記憶正在訪問的這一層和下一層的頂點,以便于向下一層訪問。為避免重復訪問,需要一個輔助數組visited[]，給被訪問過的頂點加標記。

圖的廣度優先搜索算法voidGraph_Traverse(AdjGraphG){ ‥‥‥‥‥for(inti=0;i<G.n;i++)if(!visited[i])BFS(G,i,visited);‥‥‥‥‥}第三十九頁，共一百零一頁，2022年，8月28日voidBFS(AdjGraphG,intv,intvisited[]){cout<<GetValue(v)<<'';visited[v]=1;Queue<int>q;InitQueue(&q);EnQueue(&q,v);//進隊列while(!QueueEmpty(&q)){//隊空搜索結束DeQueue(&q,v);intw=GetFirstNeighbor(G,v);while(w!=-1){//若鄰接頂點w存在 if(!visited[w]){//未訪問過 cout<<GetValue(w)<<‘’;第四十頁，共一百零一頁，2022年，8月28日

visited[w]=1;EnQueue(&q,w);} w=GetNextNeighbor(G,v,w);}//重復檢測v的所有鄰接頂點}//外層循環，判隊列空否delete[]visited;}第四十一頁，共一百零一頁，2022年，8月28日

連通分量(Connectedcomponent)當無向圖為非連通圖時,從圖中某一頂點出發,利用深度優先搜索算法或廣度優先搜索算法不可能遍歷到圖中的所有頂點,只能訪問到該頂點所在的最大連通子圖(連通分量)的所有頂點。若從無向圖的每一個連通分量中的一個頂點出發進行遍歷,可求得無向圖的所有連通分量。圖的連通性問題第四十二頁，共一百零一頁，2022年，8月28日求連通分量的算法需要對圖的每一個頂點進行檢測：若已被訪問過，則該頂點一定是落在圖中已求得的連通分量上；若還未被訪問，則從該頂點出發遍歷圖，可求得圖的另一個連通分量。對于非連通的無向圖，所有連通分量的生成樹組成了非連通圖的生成森林。第四十三頁，共一百零一頁，2022年，8月28日ACDEIBFOGHJNMLK非連通無向圖的三個連通分量AHKCDEIBFOGJNML非連通圖的連通分量的極小連通子圖第四十四頁，共一百零一頁，2022年，8月28日重連通分量(BiconnectedComponent)在無向連通圖G中,當且僅當刪去G中的頂點v及所有依附于v的所有邊后,可將圖分割成兩個或兩個以上的連通分量，則稱頂點v為關節點。沒有關節點的連通圖叫做重連通圖。在重連通圖上,任何一對頂點之間至少存在有兩條路徑,在刪去某個頂點及與該頂點相關聯的邊時,也不破壞圖的連通性。一個連通圖G如果不是重連通圖，那么它可以包括幾個重連通分量。第四十五頁，共一百零一頁，2022年，8月28日在一個無向連通圖G中,重連通分量可以利用深度優先生成樹找到。在圖中各頂點旁標明的深度優先數,給出進行深度優先搜索時各頂點訪問的次序。深度優先生成樹的根是關節點的充要條件是它至少有兩個子女。其它頂點u是關節點的充要條件是它至少有一個子女w,從w出發,不能通過w、w的子孫及一條回邊所組成的路徑到達u的祖先。第四十六頁，共一百零一頁，2022年，8月28日ABCDEFGHIJABCDEFGHJABCDEFGHJII12345678910根有兩個子女關節點關節點關節點第四十七頁，共一百零一頁，2022年，8月28日ABCDEFGHIJABHIDFBCDEFGH連通圖和它的連通分量第四十八頁，共一百零一頁，2022年，8月28日最小生成樹(minimumcostspanningtree)使用不同的遍歷圖的方法，可以得到不同的生成樹；從不同的頂點出發，也可能得到不同的生成樹。按照生成樹的定義，n個頂點的連通網絡的生成樹有n個頂點、n-1條邊。構造最小生成樹的準則必須使用且僅使用該網絡中的n-1條邊來聯結網絡中的n個頂點；不能使用產生回路的邊；各邊上的權值的總和達到最小。第四十九頁，共一百零一頁，2022年，8月28日普里姆(Prim)算法普里姆算法的基本思想：從連通網絡N={V,E}中的某一頂點u0出發,選擇與它關聯的具有最小權值的邊 (u0,v),將其頂點加入到生成樹頂點集合U中。 以后每一步從一個頂點在U中,而另一個頂點不在U中的各條邊中選擇權值最小的邊(u,v),把它的頂點加入到集合U中。如此繼續下去,直到網絡中的所有頂點都加入到生成樹頂點集合U中為止。采用鄰接矩陣作為圖的存儲表示。第五十頁，共一百零一頁，2022年，8月28日252510504613228102514242216185046132504613210原圖(a)(b)504613210(c)(d)(e)(f)50461321022125046121025142216123252212第五十一頁，共一百零一頁，2022年，8月28日在構造過程中，還設置了兩個輔助數組：lowcost[]存放生成樹頂點集合內頂點到生成樹外各頂點的各邊上的當前最小權值；nearvex[]記錄生成樹頂點集合外各頂點距離集合內哪個頂點最近(即權值最小)。例子5046132281025142422161812第五十二頁，共一百零一頁，2022年，8月28日若選擇從頂點0出發，即u0=0，則兩個輔助數組的初始狀態為：然后反復做以下工作：在lowcost[]中選擇nearvex[i]

-1&&lowcost[i]最小的邊,用v標記它。則選中的權值最小的邊為(nearvex[v],v),相應的權值為lowcost[v]。02810-1000000lowcostnearvex0123456第五十三頁，共一百零一頁，2022年，8月28日將nearvex[v]改為-1,表示它已加入生成樹頂點集合。將邊(nearvex[v],v,lowcost[v])加入生成樹的邊集合。取lowcost[i]=min{lowcost[i],Edge[v][i]}，即用生成樹頂點集合外各頂點i到剛加入該集合的新頂點v的距離Edge[v][i]與原來它們到生成樹頂點集合中頂點的最短距離lowcost[i]做比較,取距離近的作為這些集合外頂點到生成樹頂點集合內頂點的最短距離。第五十四頁，共一百零一頁，2022年，8月28日

如果生成樹頂點集合外頂點i到剛加入該集合的新頂點v的距離比原來它到生成樹頂點集合中頂點的最短距離還要近，則修改nearvex[i]:nearvex[i]=v。表示生成樹外頂點i到生成樹內頂點v當前距離最近。 02810

-1000000

lowcostnearvex0123456選v=5選邊(0,5)第五十五頁，共一百零一頁，2022年，8月28日頂點v=5加入生成樹頂點集合：02825

10

-10005

-10

lowcostnearvex0123456選v=4選邊(5,4)50461322810251424221618原圖邊(0,5,10)

加入生成樹1204613210255第五十六頁，共一百零一頁，2022年，8月28日0123456頂點v=4加入生成樹頂點集合：02822

25

10

24

-100

4

-1

-1

4

lowcostnearvex選v=3選邊(4,3)50461322810251424221618原圖邊(5,4,25)

加入生成樹125046132102522第五十七頁，共一百零一頁，2022年，8月28日頂點v=3加入生成樹頂點集合：02812

22

25

10

18

-103

-1

-1

-1

3

lowcostnearvex0123456選v=2選邊(3,2)50461322810251424221618原圖邊(4,3,22)

加入生成樹12504613210252212第五十八頁，共一百零一頁，2022年，8月28日lowcostnearvex0123456頂點v=2加入生成樹頂點集合：0

16

12

22

25

1018

-1

2

-1

-1

-1

-13

選v=1選邊(2,1)50461322810251424221618原圖邊(3,2,12)

加入生成樹125041321025221612第五十九頁，共一百零一頁，2022年，8月28日頂點v=1加入生成樹頂點集合：0

16

12

22

25

10

14

-1

-1

-1

-1

-1

-1

1

lowcostnearvex0123456選v=6選邊(1,6)50461322810251424221618原圖邊(2,1,16)

加入生成樹125046132102514221612第六十頁，共一百零一頁，2022年，8月28日lowcostnearvex0123456頂點v=6加入生成樹頂點集合：0

16

12

22

25

10

14

-1

-1

-1

-1

-1

-1

-1

50461322810251424221618原圖邊(1,6,14)

加入生成樹125046132102514221612第六十一頁，共一百零一頁，2022年，8月28日最后生成樹中邊集合里存入得各條邊為： (0,5,10),(5,4,25),(4,3,22), (3,2,12),(2,1,16),(1,6,14)利用普里姆算法建立最小生成樹voidPrim(GraphG,MST&T,intu){float*lowcost=newfloat[NumVertices];int*nearvex=newint[NumVertices];for(inti=0;i<NumVertices;i++){lowcost[i]=G.Edge[u][i];//Vu到各點代價nearvex[i]=u;//及最短帶權路徑}第六十二頁，共一百零一頁，2022年，8月28日

nearvex[u]=-1;//加到生成樹頂點集合

intk=0;//存放最小生成樹結點的變量for(i=0;i<G.n;i++)if(i!=u){//循環n-1次,加入n-1條邊 EdgeDatamin=MaxValue;intv=0; for(intj=0;j<NumVertices;j++) if(nearvex[j]!=-1&&//=-1不參選lowcost[j]<min) {v=j;min=lowcost[j];}

//求生成樹外頂點到生成樹內頂點具有最

//小權值的邊,v是當前具最小權值的邊

第六十三頁，共一百零一頁，2022年，8月28日

if(v){//v=0表示再也找不到要求頂點T[k].tail=nearvex[v];//選邊加入生成樹T[k].head=v;T[k++].cost=lowcost[v];nearvex[v]=-1;//該邊加入生成樹標記for(j=0;j<G.n;j++)if(nearvex[j]!=-1&& G.Edge[v][j]<lowcost[j]){lowcost[j]=G.Edge[v][j];//修改nearvex[j]=v;}}第六十四頁，共一百零一頁，2022年，8月28日

}//循環n-1次,加入n-1條邊}分析以上算法,設連通網絡有n個頂點,則該算法的時間復雜度為O(n2),它適用于邊稠密的網絡。注意：當各邊有相同權值時，由于選擇的隨意性，產生的生成樹可能不唯一。當各邊的權值不相同時，產生的生成樹是唯一的。

第六十五頁，共一百零一頁，2022年，8月28日活動網絡(ActivityNetwork)計劃、施工過程、生產流程、程序流程等都是“工程”。除了很小的工程外，一般都把工程分為若干個叫做“活動”的子工程。完成了這些活動，這個工程就可以完成了。例如，計算機專業學生的學習就是一個工程，每一門課程的學習就是整個工程的一些活動。其中有些課程要求先修課程，有些則不要求。這樣在有的課程之間有領先關系，有的課程可以并行地學習。用頂點表示活動的網絡(AOV網絡)第六十六頁，共一百零一頁，2022年，8月28日

C1高等數學C2程序設計基礎C3離散數學C1,C2

C4數據結構C3,C2C5高級語言程序設計C2C6編譯方法C5,C4C7操作系統C4,C9C8普通物理C1C9計算機原理C8

課程代號課程名稱先修課程第六十七頁，共一百零一頁，2022年，8月28日學生課程學習工程圖C8C3C5C4C9C6C7C1C2第六十八頁，共一百零一頁，2022年，8月28日可以用有向圖表示一個工程。在這種有向圖中，用頂點表示活動，用有向邊<Vi,Vj>表示活動Vi必須先于活動Vj進行。這種有向圖叫做頂點表示活動的AOV網絡(ActivityOnVertices)。在AOV網絡中不能出現有向回路,即有向環。如果出現了有向環，則意味著某項活動應以自己作為先決條件。因此，對給定的AOV網絡，必須先判斷它是否存在有向環。第六十九頁，共一百零一頁，2022年，8月28日檢測有向環的一種方法是對AOV網絡構造它的拓撲有序序列。即將各個頂點(代表各個活動)排列成一個線性有序的序列，使得AOV網絡中所有應存在的前驅和后繼關系都能得到滿足。這種構造AOV網絡全部頂點的拓撲有序序列的運算就叫做拓撲排序。如果通過拓撲排序能將AOV網絡的所有頂點都排入一個拓撲有序的序列中,則該網絡中必定不會出現有向環。第七十頁，共一百零一頁，2022年，8月28日如果AOV網絡中存在有向環，此AOV網絡所代表的工程是不可行的。例如,對學生選課工程圖進行拓撲排序,得到的拓撲有序序列為C1,C2,C3,C4,C5,C6,C8,C9,C7

或C1,C8,C9,C2,C5,C3,C4,C7,C6C8C3C5C4C9C6C7C1C2第七十一頁，共一百零一頁，2022年，8月28日拓撲排序的方法①

輸入AOV網絡。令n為頂點個數。 ②在AOV網絡中選一個沒有直接前驅的頂點,并輸出之;③從圖中刪去該頂點,同時刪去所有它發出的有向邊;④重復以上②、③步,直到全部頂點均已輸出，拓撲有序序列形成，拓撲排序完成；或圖中還有未輸出的頂點,但已跳出處理循環。說明圖中還剩下一些頂點,它們都有直接前驅。這時網絡中必存在有向環。第七十二頁，共一百零一頁，2022年，8月28日C0C1C2C3C4C5拓撲排序的過程(a)有向無環圖C2C5C1C0C3(b)輸出頂點C4C1C2C5C3(c)輸出頂點C0C4C0C2C5C1C3(d)輸出頂點C3第七十三頁，共一百零一頁，2022年，8月28日C1C2C5(e)輸出頂點C2C5C1(f)輸出頂點C1C5(g)輸出頂點C5

最后得到的拓撲有序序列為C4,C0,C3,C2,C1,C5。它滿足圖中給出的所有前驅和后繼關系，對于本來沒有這種關系的頂點，如C4和C2，也排出了先后次序關系。(h)拓撲排序完成第七十四頁，共一百零一頁，2022年，8月28日AOV網絡及其鄰接表表示C0C1C2C3C4C5C0C1C2C30C4C50012345countdataadj

1301031

destlink3051500150第七十五頁，共一百零一頁，2022年，8月28日在鄰接表中增設一個數組count[]，記錄各頂點入度。入度為零的頂點即無前驅頂點。在輸入數據前,頂點表VexList[]和入度數組count[]全部初始化。在輸入數據時,每輸入一條邊<j,k>,就需要建立一個邊結點,并將它鏈入相應邊鏈表中,統計入度信息：EdgeNode*p=newEdgeNode;

p->dest=k;

//建立邊結點p->link=G.VexList[j].firstAdj;VexList[j].firstAdj=p;

//鏈入頂點j的邊鏈表的前端count[k]++; //頂點k入度加一第七十六頁，共一百零一頁，2022年，8月28日在算法中,使用一個存放入度為零的頂點的鏈式棧,供選擇和輸出無前驅的頂點。拓撲排序算法可描述如下：建立入度為零的頂點棧;當入度為零的頂點棧不空時,重復執行

從頂點棧中退出一個頂點,并輸出之;從AOV網絡中刪去這個頂點和它發出的邊,邊的終頂點入度減一;如果邊的終頂點入度減至0,則該頂點進入度為零的頂點棧;

如果輸出頂點個數少于AOV網絡的頂點個數,則報告網絡中存在有向環。第七十七頁，共一百零一頁，2022年，8月28日拓撲排序的算法voidTopologicalSort(AdjGraphG){StackS;StackEmpty(S);intj;

//入度為零的頂點棧初始化for(inti=0;i<n;i++)//入度為零頂點if(count[i]==0)Push(S,i);//進棧for(i=0;i<n;i++)//期望輸出n個頂點if(StackEmpty(S)){//中途棧空,轉出cout<<“網絡中有回路！"<<endl; return;}

第七十八頁，共一百零一頁，2022年，8月28日

else{//繼續拓撲排序 Pop(S,j);//退棧 cout<<j<<endl;//輸出EdgeNode*p=VexList[j].firstAdj;while(p!=NULL){//掃描出邊表 intk=p->dest; //另一頂點 if(--count[k]==0)//頂點入度減一 Push(S,k);

//頂點的入度減至零,進棧p=p->link; }}}第七十九頁，共一百零一頁，2022年，8月28日用邊表示活動的網絡(AOE網絡)如果在無有向環的帶權有向圖中,用有向邊表示一個工程中的活動(Activity),用邊上權值表示活動持續時間(Duration),用頂點表示事件(Event),則這樣的有向圖叫做用邊表示活動的網絡,簡稱AOE(ActivityOnEdges)網絡。AOE網絡在某些工程估算方面非常有用。例如，可以使人們了解：完成整個工程至少需要多少時間(假設網絡中沒有環)?第八十頁，共一百零一頁，2022年，8月28日為縮短完成工程所需的時間,應當加快哪些活動? 從源點到各個頂點,以至從源點到匯點的有向路徑可能不止一條。這些路徑的長度也可能不同。完成不同路徑的活動所需的時間雖然不同,但只有各條路徑上所有活動都完成了,整個工程才算完成。因此,完成整個工程所需的時間取決于從源點到匯點的最長路徑長度,即在這條路徑上所有活動的持續時間之和。這條路徑長度最長的路徑就叫做關鍵路徑(CriticalPath)。第八十一頁，共一百零一頁，2022年，8月28日a9=61324a1=8a2=125678a10=12a8=18a5=28a6=8a7=6a3=14a4=10要找出關鍵路徑，必須找出關鍵活動,即不按期完成就會影響整個工程完成的活動。關鍵路徑上的所有活動都是關鍵活動。因此,只要找到了關鍵活動,就可以找到關鍵路徑。例如,下圖就是一個AOE網。第八十二頁，共一百零一頁，2022年，8月28日定義幾個與計算關鍵活動有關的量：①

事件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]第八十三頁，共一百零一頁，2022年，8月28日

l[k]是在不會引起時間延誤的前提下,該活動允許的最遲開始時間。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]。第八十四頁，共一百零一頁，2022年，8月28日為求得e[k]與l[k],需要先求得從源點V0到各個頂點Vi的Ve[i]和Vl[i]。求Ve[i]的遞推公式

從

Ve[0]=0開始，向前遞推

<Vj,Vi>S2,i=1,2,,n-1S2是所有指向Vi的有向邊<Vj,Vi>的集合。

從Vl[n-1]=Ve[n-1]開始，反向遞推

<Vi,Vj>S1,i=n-2,n-3,,0S1是所有源自Vi的有向邊<Vi,Vj>的集合。第八十五頁，共一百零一頁，2022年，8月28日這兩個遞推公式的計算必須分別在拓撲有序及逆拓撲有序的前提下進行。設活動ak(k=1,2,…,e)在帶權有向邊<Vi,Vj>上,其持續時間用dur(<Vi,Vj>)表示,則有e[k]=Ve[i]；l[k]=Vl[j]-dur(<Vi,Vj>)；k=1,2,…,e。這樣就得到計算關鍵路徑的算法。為了簡化算法,假定在求關鍵路徑之前已經對各頂點實現了拓撲排序,并按拓撲有序的順序對各頂點重新進行了編號。第八十六頁，共一百零一頁，2022年，8月28日1324a1=8a2=125678a10=12a9=6a8=18a5=28a6=8a7=6a3=14a4=10VeVl12345678

0812222840465808122228404658el008121222222840460081212322228404612345678910第八十七頁，共一百零一頁，2022年，8月28日事件Ve[i]Vl[i]V000V166V246V358V477V5710V61616V71414V81818

邊<0,1><0,2><0,3><1,4><2,4><3,5><4,6><4,7><5,7><6,8><7,8>活動a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

a11

e0006457771614

l02366877101614l-e0

2302300300關鍵是是是是是是第八十八頁，共一百零一頁，2022年，8月28日利用關鍵路徑法求AOE網的各關鍵活動void

graph::CriticalPath(){//在此算法中需要對鄰接表中單鏈表的結點加以//修改,在各結點中增加一個int域cost,記錄該結//點所表示的邊上的權值。

int

i,

j;

int

p,k;

int

e,l;

Ve=newint[n];

Vl=newint[n];

for(i=0;

i<n;i++)Ve[i]=0;//初始化

for(i=0;i<n;

i++){//順向計算事件最早允許開始時間

Edge<int>*p=NodeTable[i].adj;//該頂點邊鏈表鏈頭指針p

while(p!=NULL){//找所有后繼鄰接頂點

k=p→dest;//i的后繼鄰接頂點k

if(Ve[i]+p→cost>Ve[k]) Ve[k]=Ve[i]+p→cost; p=p→link;//找下一個后繼}第八十九頁，共一百零一頁，2022年，8月28日}

for(i=0;

i<n;

i++)Vl[i]=Ve[n-1];//逆向計算事件 的最遲開始時間

for(i=n-2;

i;

i--){//按逆拓撲有序順序處理

p=NodeTable[i].adj;//該頂點邊鏈表鏈頭指針p

while(p!=NULL){

k=p→dest;//i的后繼鄰接頂點k

if(Vl[k]-

p→cost<Vl[i])

Vl[i]=Vl[k]-

p→cost;

p=p→link;//找下一個后繼

}

}第九十頁，共一百零一頁，2022年，8月28日

for(i=0;

i<n;

i++){//逐個頂點求各活動的e[k]和l[k]

p=NodeTable[i].adj; //該頂點邊鏈表鏈頭指針p

while(p!=NULL){

k=p→dest; //k是i的后繼鄰接頂點

e=Ve[i];l=Vl[k]-p→cost;

if(l==e)//關鍵活動

cout<<"<"<<i<<","<<k

<<“>”<<“是關鍵活動”<<endl;

p=p→link;//找下一個后繼

}

}}

第九十一頁，共一百零一頁，2022年，8月28日注意在拓撲排序求Ve[i]和逆拓撲有序求Vl[i]時,所需為O(n+e),求各個活動的e[k]和l[k]時所需時間為O(e),總共花費時間仍然是O(n+e)。所有頂點按拓撲有序的次序編號僅計算Ve[i]和Vl[i]是不夠的，還須計算e[k]和l[k]。不是任一關鍵活動加速一定能使整個工程提前。想使整個工程提前，要考慮各個關鍵路徑上所有關鍵活動。第九十二頁，共一百零一頁，2022年，8月28日最短路徑(ShortestPath)最短路徑問題：如果從圖中某一頂點(稱為源點)到達另一頂點(稱為終點)的路徑可能不止一條，如何找到一條路徑使得沿此路徑上各邊上的權值總和達到最小。問題解法

邊上權值非負情形的單源最短路徑問題—Dijkstra算法邊上權值為任意值的單源最短路徑問題—Bellman和Ford算法所有頂點之間的最短路徑—Floyd算法第九十三頁，共一百零一頁，2022年，8月28日邊上權值非負情形的單源最短路徑問題問題的提法：給定一個帶權有向圖D與源點v，求從v到D中其它頂點的最短路徑。限定各邊上的權值大于或等于0。為求得這些最短路徑,Dijkstra提出按路徑長度的遞增次序,逐步產生最短路徑的算法。首先求出長度最短的一條最短路徑，再參照它求出長度次短的一條最短路徑，依次類推，直到從頂點v到其它各頂點的最短路徑全部求出為止。舉例說明第九十四頁，共一百零一頁，2022年，8月28日Dijkstra逐步求解的過程10432101003050206010源點終點最短路徑路徑長度v0

v1

(v0,v1)