圖在日常生活及科學(xué)技術(shù)領(lǐng)域都有著廣泛的應(yīng)用

第七章圖圖在日常生活及科學(xué)技術(shù)領(lǐng)域都有著廣泛的應(yīng)用，是常用而又復(fù)雜的一種數(shù)據(jù)結(jié)構(gòu)。圖的概念圖的存儲結(jié)構(gòu)圖的遍歷圖的生成樹和最小生成樹最短路徑拓?fù)渑判蛐〗Y(jié)

over圖的概念圖(graph)的定義：一種復(fù)雜非線性數(shù)據(jù)結(jié)構(gòu)?！鴪D的二元組定義G=(V,E)，V是頂點(diǎn)集，V={vi|0≤i≤n-1，n≥0，vi∈VertexType}，VertexType是頂點(diǎn)值類型，n為頂點(diǎn)數(shù)，n=0時V是空集；E是V上二元關(guān)系，即V上頂點(diǎn)序偶<x,y>(有向邊)或無序?qū)?x,y)(無向邊)的集合，即是邊集合?！鴮τ赩上的每個頂點(diǎn)，在E中都允許有任意多個前驅(qū)和后繼。next▲圖的二元組的另一個定義：圖由頂點(diǎn)集(vertexset)V(G)和邊集(edgeset)E(G)所組成。假設(shè)V(G)為空，那么E(G)也必然為空；假設(shè)V(G)非空，那么E(G)不一定非空。▲有向圖(directedgraph)----指圖G的邊集E(G)中為有向邊?！鵁o向圖(undirectedgraph)----指圖G的邊集E(G)中為無向邊。nextV(G1)={0,1,2,3}E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)}V(G2)={0,1,2,3,4,5,6}E(G2)={(0,1),(0,2),(1,3),(1,4),(2,5),(2,6)}V(G3)={0,1,2}E(G3)={<0,1>,<1,0>,<1,2>}E(G4)={0,1,2,3}V(G4)={<0,1>,<1,0>,<0,2>,<2,0>,<0,3>,<3,0>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>}next圖的根本術(shù)語▲端點(diǎn)和鄰接點(diǎn)▲頂點(diǎn)的度、入度、出度▲完全圖、稠密圖、稀疏圖▲子圖▲路徑和回路▲連通和連通分量▲強(qiáng)連通圖和強(qiáng)連通分量▲權(quán)和網(wǎng)back端點(diǎn)(endpoint)和鄰接點(diǎn)(adjacent)在一無向圖中，假設(shè)有邊(vi,vj)，那么稱vi，vj為此邊的兩個端點(diǎn)，并稱它們互為鄰接點(diǎn)。在一有向圖中，假設(shè)有邊<vi,vj>，那么稱此邊是頂點(diǎn)vi的一條出邊(outedge)，頂點(diǎn)vj的一條入邊(inedge)；vi是此邊的起點(diǎn)/始點(diǎn)，vj是此邊的終點(diǎn)；稱vi和vj互為鄰接點(diǎn)，并稱vj是vi的出邊鄰接點(diǎn)，vi是vj的入邊鄰接點(diǎn)。back頂點(diǎn)的度、入度、出度無向圖中頂點(diǎn)v的度(deree)----D(v)定義為以該頂點(diǎn)為一個端點(diǎn)的邊的數(shù)目。有向圖中頂點(diǎn)v的度等于它的入度(ID(v))和出度(OD(v))之和，即D(v)=ID(v)+OD(v)?！攵?indegree)----ID(v)是該頂點(diǎn)的入邊數(shù)目?！龆?outdegree)----OD(v)是該頂點(diǎn)的出邊數(shù)目。next假設(shè)一個圖有n個頂點(diǎn)和e條邊，那么該圖所有頂點(diǎn)的度同邊數(shù)e滿足一下關(guān)系：證明：∵每條邊連接著兩個頂點(diǎn)，∴每個頂點(diǎn)的度數(shù)分別加1，總和加2，∴全部頂點(diǎn)的度數(shù)為所有邊數(shù)的2倍。back完全圖、稠密圖、稀疏圖完全圖----假設(shè)無向圖中的每兩個頂點(diǎn)間都存在一條邊，有向圖中每兩個頂點(diǎn)間都存在反方向的兩條邊，那么稱這樣的圖為完全圖。無向完全圖包含有n(n-1)/2條邊；有向完全圖包含有n(n-1)條邊。稠密圖----一個圖接近完全圖時。稀疏圖----一個圖含有較少的邊數(shù)時。back子圖設(shè)有兩個圖G=(V,E)和G’=(V’,E’)，假設(shè)V’?V，且E’?E，并且E’中的邊所涉及的頂點(diǎn)均屬于V’，那么稱G’是G的子圖。back路徑和回路在一圖G中，從頂點(diǎn)v到頂點(diǎn)v’的一條路徑(path)是一個頂點(diǎn)序列u1,u2,…,um，其中v=u1，v’=um，假設(shè)此圖是無向圖，那么(uj-1,uj)∈E(G)，2≤j≤m；假設(shè)此圖是有向圖，那么<uj-1,uj>∈E(G)，2≤j≤m。next路徑長度----是指該路徑上經(jīng)過的邊的數(shù)目。簡單路徑----指一條路徑上的所有頂點(diǎn)均不同。復(fù)雜路徑----指一條路徑上的頂點(diǎn)有所重復(fù)?；芈?環(huán)cycle)----指一條路徑上的前后兩端點(diǎn)相同。back連通和連通分量在無向圖G中，假設(shè)從頂點(diǎn)vi到頂點(diǎn)vj有路徑，那么稱vi和vj是連通的。假設(shè)圖G中任意兩個頂點(diǎn)都是連通的，那么稱G為連通圖，否那么為非連通圖。無向圖G的極大連通子圖稱為G的連通分量。一個連通圖有多個連通分量，且每個連通分量都能連通所有頂點(diǎn)；而非連通圖的每個連通分量只能連通其中一局部頂點(diǎn)，不能連通全部頂點(diǎn)。back強(qiáng)連通圖和強(qiáng)連通分量在有向圖G中，假設(shè)從頂點(diǎn)vi到vj有路徑，那么稱從vi到vj是連通的。假設(shè)有向圖G中任意兩個頂點(diǎn)vi和vj都連通，即從vi到vj都存在路徑，那么稱有向圖G是強(qiáng)連通圖。有向圖G的極大連通子圖稱為G的強(qiáng)連通分量。一個強(qiáng)連通的有向圖至少包含一個強(qiáng)連通分量；一個非強(qiáng)連通的有向圖一定包含多個強(qiáng)連通分量。back權(quán)和網(wǎng)在一圖中，每條邊上標(biāo)記上具有某種含義的數(shù)值，此數(shù)值稱為該邊的權(quán)(weight)。邊上帶權(quán)的圖稱做帶權(quán)圖或者網(wǎng)(network)。back圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)又稱作圖的存儲表示或圖的表示，常用的有三種：鄰接矩陣鄰接表邊集數(shù)組back鄰接矩陣(adjacencymatrix)鄰接矩陣是表示圖中頂點(diǎn)間相鄰關(guān)系的矩陣。設(shè)G=(V,E)是具有n個頂點(diǎn)的圖，頂點(diǎn)序號依次為ni(0≤i≤n-1)，那么G的鄰接矩陣具有如下定義的n階方陣。1無向圖(vi,vj)或(vj,vi)∈E(G)；A[i,j]=有向圖<vi,vj>∈E(G)0對應(yīng)邊不存在于E(G)中無向圖的鄰接矩陣是對稱的，有向圖的鄰接矩陣是不對稱的。nextnext對于帶權(quán)圖，鄰接矩陣表示為next采用鄰接矩陣表示圖，便于查找圖中任一邊或邊上的權(quán)，時間復(fù)雜度為O(1)。例：查找邊(i,j)或<i,j>，只要查A[i,j]是否為一個有效值(非零值或非MaxValue值)即可；假設(shè)為有效值那么邊存在，否那么不存在。也便于查找圖中任意頂點(diǎn)的度，時間復(fù)雜度為O(n)。例：在無向圖中，統(tǒng)計第i行(列)有效元素個數(shù)可得頂點(diǎn)vi的度；在有向圖中，統(tǒng)計第i行有效元素個數(shù)可得頂點(diǎn)vi的出度，統(tǒng)計第i列有效元素個數(shù)可得頂點(diǎn)vi的入度。next查找任一頂點(diǎn)的鄰接點(diǎn)也同樣方便，依次查找一個頂點(diǎn)所有鄰接點(diǎn)(出邊鄰接點(diǎn)或入邊鄰接點(diǎn))時間復(fù)雜度為O(n)。例：查找vi的一個鄰接點(diǎn)(無向圖)或出邊鄰接點(diǎn)(有向圖)，只要在第i行上查找出一個有效元素，以該元素所在列號j為序號的頂點(diǎn)vj就是所求?？臻g復(fù)雜度：鄰接矩陣存儲需要占用n*n個整數(shù)存儲位置表示頂點(diǎn)的相鄰關(guān)系，還需要一個n個元素的一維數(shù)組存儲頂點(diǎn)信息，空間復(fù)雜度為O(n2)。適合稠密圖。next鄰接矩陣的類型定義：#defineMaxVertexNum8#defineMaxEdgeNum20#defineMaxValue1000typedefintVertexType;typedefVertexTypeVexlist[MaxVertexNum];typedefintAdjmatrix[MaxVertexNum][MaxVertexNum];next算法7-1生成無向帶權(quán)圖頂點(diǎn)數(shù)組和鄰接矩陣的算法p128-129voidCreate1(VexlistGV,AdjmatrixGA,intn,inte){inti,j,k,w;printf(“輸入%d個頂點(diǎn)數(shù)據(jù)：〞,n);for(i=0;i<n;i++)scanf(“%d〞,&GV[i]);nextfor(i=0;i<n;i++)for(j=0;j<n;j++){if(i==j)GA[i][j]=0;elseGA[i][j]=MaxValue;}printf(“\n輸入&d條無向帶權(quán)邊：\n〞,e);for(k=1;k<=e;k++){scanf(“%d%d%d〞,&i,&j,&w);GA[i][j]=GA[j][i]=w;}}back鄰接表(adjacencylist)鄰接表是對圖中每個頂點(diǎn)建立一個鄰接關(guān)系的單鏈表，并把它們的表頭指針用向量存儲的一種圖的表示方法。為頂點(diǎn)vi建立的鄰接關(guān)系的單鏈表稱做vi鄰接表。鄰接表中每個結(jié)點(diǎn)存儲該頂點(diǎn)為端點(diǎn)/起點(diǎn)的一條邊的信息，稱為邊結(jié)點(diǎn)。next無向圖的vi鄰接表的邊結(jié)點(diǎn)數(shù)，等于vi的邊數(shù)/鄰接點(diǎn)數(shù)/度數(shù)；有向圖的vi鄰接表的邊結(jié)點(diǎn)數(shù)，等于vi的出邊數(shù)/出邊鄰接點(diǎn)數(shù)/出度數(shù)。邊結(jié)點(diǎn)包含三個域：▲鄰接點(diǎn)域(adjvex)：存儲頂點(diǎn)vi的一個鄰接頂點(diǎn)vj的序號j；▲權(quán)域(weight)：存儲邊(vi,vj)/<vi,vj>的權(quán)；(無權(quán)圖不需要)▲鏈域(next)：用以鏈接下一個邊結(jié)點(diǎn)next用一個n個元素的一維數(shù)組存儲n個頂點(diǎn)的鄰接表的表頭指針。無向圖的鄰接表：next有向圖的鄰接表和逆鄰接表next網(wǎng)絡(luò)(帶權(quán)圖)的鄰接表next鄰接表的類型定義：#defineMaxVertexNum8#defineMaxEdgeNum20typedefintVertexType;typedefVertexTypeVexlist[MaxVertexNum];typedefstructedgenode{intadjvex,weight;structedgenode*next;}Edgenode;typedefEdgenode*Adjlist[MaxVertexNum];next算法7-2生成有向圖鄰接表算法p130-131voidCreate2(VexlistGV,AdjlistGL,intn,inte){inti,j,k;printf(“輸入%d個頂點(diǎn)數(shù)據(jù)：〞,n);for(i=0;i<n;i++)scanf(“%d〞,&GV[i]);for(i=0;i<n;i++)GL[i]=NULL;printf(“\n輸入%d條有向無權(quán)邊：\n〞,e);nextfor(k=1;k<=e;k++){Edgenode*p;sacnf(“%d%d〞,&i,&j);p=(Edgenode*)malloc(sizeof(Edgenode));p->adjvex=j;p->next=GL[i];//頭插法GL[i]=p;}}next圖的鄰接表中便于查找一個頂點(diǎn)的邊/出邊或鄰接點(diǎn)/出邊鄰接點(diǎn)，時間復(fù)雜度O(e/n)。例：只要首先從表頭向量中取出對應(yīng)表頭指針，然后從表頭指針出發(fā)進(jìn)行查找即可。對于那些經(jīng)常需要查找頂點(diǎn)入邊/入邊鄰接點(diǎn)的運(yùn)算，可以專門建立對應(yīng)的逆鄰接表(contraryadjacencylist)，該表每個頂點(diǎn)存儲所有入邊的信息，鄰接點(diǎn)域存儲的是入邊鄰接點(diǎn)的序號。next把有向圖的鄰接表和逆鄰接表結(jié)合起來構(gòu)成十字鄰接表(orthogonaladjacencylist)。在十字鄰接表中，每個邊結(jié)點(diǎn)對應(yīng)圖中一條有向邊，包含5個域：邊起點(diǎn)域、邊終點(diǎn)域、邊上權(quán)域、入邊鏈域，出邊鏈域。入邊鏈域指向同一頂點(diǎn)的下條入邊結(jié)點(diǎn)。出邊鏈域指向同一頂點(diǎn)的下條出邊結(jié)點(diǎn)。表頭向量中的每個分量包括兩個與：入邊表的表頭指針域和出邊表的表頭指針域。next有向圖的十字鄰接表：next圖的鄰接表、逆鄰接表、十字鄰接表表示中，表頭指針向量數(shù)組占用n個或2n個指針存儲空間，所有邊結(jié)點(diǎn)需要占用2e(無向圖)或e(有向圖)個邊結(jié)點(diǎn)空間，空間復(fù)雜度為O(n+e)。適合于稀疏圖。圖的鄰接表與鄰接矩陣的關(guān)系：鄰接表中每個頂點(diǎn)vi的單鏈表對應(yīng)鄰接矩陣的第i行；你連接表中每個頂點(diǎn)vi的單鏈表對應(yīng)鄰接矩陣的第i列。back邊集數(shù)組(edgesetarray)邊集數(shù)組是利用一維數(shù)組存儲圖中所有邊的一種圖的表示法。數(shù)組中每個元素用來存儲一條邊的起點(diǎn)、終點(diǎn)、權(quán)值。邊集數(shù)組織存儲邊的信息，假設(shè)需要存儲頂點(diǎn)信息同樣需要一個n個元素的一維數(shù)組。next000112123233012345起點(diǎn)終點(diǎn)001123344152634656281016141222182524012345678起點(diǎn)終點(diǎn)權(quán)next邊集數(shù)組的類型：#defineMaxEdgeNum20typedefintVertexType;typedefVertexTypeVexlist[MaxVertexNum];typedefstructedgeElem{intfromvex,endvex,weight;}EdgeElem;typedefEdgeElemEdgeset[MaxEdgeNum];next算法7-3建立帶權(quán)圖邊集數(shù)組p133voidCreate3(VexlistGV,EdgesetGE,intn,inte){inti,k,j,w;printf(“輸入%d個頂點(diǎn)數(shù)據(jù)：〞,n);for(i=0;i<n;i++)scanf(“%d〞,&GV[i]);printf(“\n輸入%d條帶權(quán)邊：\n〞,e);for(k=0;k<e;k++){scanf(“%d%d%d〞,&I,&j,&w);GE[k].fromvex=i;GE[k].endvex=j;GE[k].weight=w;}}next在邊集數(shù)組中查找一條邊或一個頂點(diǎn)的度的時間復(fù)雜度為O(e)。邊集數(shù)組適合那些對邊依次進(jìn)行處理的運(yùn)算，不適合對頂點(diǎn)的運(yùn)算，也不適合對任一條邊的運(yùn)算。邊集數(shù)組的空間復(fù)雜度為O(e)，適合表示稀疏圖。back圖的遍歷圖的遍歷就是從初始點(diǎn)出發(fā)，按照一定的搜索方法對圖中的所有頂點(diǎn)各做一次訪問的過程。設(shè)置輔助數(shù)組visited[n]，記住每個頂點(diǎn)是否被訪問過。元素值0說明未訪問過，1表示已經(jīng)訪問過。圖的遍歷有兩種方法：▲深度優(yōu)先搜索遍歷▲廣度優(yōu)先搜索遍歷next深度優(yōu)先搜索(depth-firstsearch)遍歷深度有限搜索遍歷的定義----一個遞歸過程：首先訪問一個頂點(diǎn)vi(一開始為初始點(diǎn))，并標(biāo)記visited[i]=1；然后從vi的任一未被訪問過的鄰接點(diǎn)/出邊鄰接點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索遍歷，當(dāng)vi所有鄰接點(diǎn)均被訪問過，那么退回到上一頂點(diǎn)vk，從vk的另一未被訪問過的鄰接點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索遍歷，直到退回到初始點(diǎn)且沒有未被訪問過的鄰接點(diǎn)為止。next深度優(yōu)先搜索遍歷的過程：結(jié)合上圖分析以A頂點(diǎn)作為初始點(diǎn)的深度優(yōu)先搜索遍歷過程。next⑴訪問序號為0的頂點(diǎn)A，visited[0]=1，從A的一個未被訪問的鄰接點(diǎn)序號為1的頂點(diǎn)B(A的三個鄰接點(diǎn)B、C、D都未被訪問過，假定先取B訪問)出發(fā)進(jìn)行深度優(yōu)先搜索遍歷；⑵訪問頂點(diǎn)B，visited[1]=1，從B的一個未被訪問的鄰接點(diǎn)序號為2的頂點(diǎn)E(B的三個鄰接點(diǎn)僅A被訪問過，E、C都未被訪問過，假定先取E訪問)出發(fā)進(jìn)行深度優(yōu)先搜索遍歷；⑶訪問頂點(diǎn)E，visited[2]=1，從E僅有的一個未被訪問的鄰接點(diǎn)序號為3的頂點(diǎn)G(E的另一個鄰接點(diǎn)B已經(jīng)被訪問過)出發(fā)進(jìn)行深度優(yōu)先搜索遍歷；next⑷訪問頂點(diǎn)G，visited[3]=1，G僅有一個鄰接點(diǎn)E且已經(jīng)被訪問過，原路退回到上一頂點(diǎn)E，E的兩個鄰接點(diǎn)B、G都已經(jīng)被訪問過，原路退回到到上一頂點(diǎn)B，選取B剩下的另一未被訪問的鄰接點(diǎn)序號為4的頂點(diǎn)C(B另外兩個鄰接點(diǎn)A、E都已經(jīng)被訪問過)出發(fā)進(jìn)行深度優(yōu)先搜索遍歷；⑸訪問頂點(diǎn)C，visited[4]=1，從C的一個未被訪問的鄰接點(diǎn)序號為5的頂點(diǎn)E(C的兩個鄰接點(diǎn)A已經(jīng)被訪問過，僅剩下F未被訪問)出發(fā)進(jìn)行深度優(yōu)先搜索遍歷；next⑹訪問頂點(diǎn)F，visited[5]=1，從F的一個未被訪問的鄰接點(diǎn)序號為6的頂點(diǎn)D(F的三個鄰接點(diǎn)中C已被訪問過，D、H未被訪問過，假定先取D訪問)出發(fā)進(jìn)行深度優(yōu)先搜索遍歷；⑺訪問頂點(diǎn)D，visited[6]=1，D的兩個鄰接點(diǎn)A、F已被訪問過，原路退回上一頂點(diǎn)F，再取F的另外一個未被訪問的鄰接點(diǎn)序號為7的頂點(diǎn)H(F的兩個鄰接點(diǎn)D已被訪問，僅剩下H)出發(fā)進(jìn)行深度優(yōu)先搜索遍歷；next⑻訪問頂點(diǎn)H，visited[7]=1，從H的一個未被訪問的鄰接點(diǎn)序號為8的頂點(diǎn)I(H的兩個鄰接點(diǎn)中F已被訪問過，僅剩I未被訪問過)出發(fā)進(jìn)行深度優(yōu)先搜索遍歷；⑼訪問頂點(diǎn)I，visited[8]=1，I的鄰接點(diǎn)H已被訪問，原路退回上一個頂點(diǎn)H，H的兩個鄰接點(diǎn)F、I已被訪問，再原路退回上一個頂點(diǎn)F，F(xiàn)的三個鄰接點(diǎn)C、D、H都已被訪問，在原路退回上一個頂點(diǎn)C，C的三個鄰接點(diǎn)點(diǎn)A、B、F都已被訪問，再原路退回上一頂點(diǎn)B，B的兩個鄰接點(diǎn)A、E都已被訪問，再原路退回上一頂點(diǎn)A，因?yàn)锳是初始點(diǎn)，深度優(yōu)先搜索遍歷結(jié)束。next以上遍歷的結(jié)果次序?yàn)椋篈、B、E、G、C、F、D、H、I深度優(yōu)先搜索遍歷算法描述：過程是遞歸的；假定visited[MaxVertexNum]為保存頂點(diǎn)訪問標(biāo)記的全局?jǐn)?shù)組(初始化為0)?！徑泳仃噷?shí)現(xiàn)▲鄰接表實(shí)現(xiàn)next鄰接矩陣實(shí)現(xiàn)算法7-4p136voidDFS1(AdjmatrixGA,inti,intn){intj;printf(“%d〞,i);//輸出被訪問頂點(diǎn)的序號visited[i]=1；for(j=0;j<n;j++)if(GA[i][j]!=0&&GA[i][j]!=MaxValue&&!visited[j])DFS1(GA,j,n);}back鄰接表實(shí)現(xiàn)算法7-5p136voidDFS2(AdjlistGL,inti,intn){Edgenode*p;intj;printf(“%d〞,i);visited[i]=1;p=GL[i];while(!p){j=p->adjvex;if(!visited[j])DFS2(GL,j,n);p=p->next;}}back算法性能分析：▲頂點(diǎn)序號確定的情況下，鄰接矩陣的表示唯一，從初始點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索遍歷結(jié)果次序唯一；鄰接表表示不唯一，所以從初始點(diǎn)出發(fā)進(jìn)行深度優(yōu)先搜索遍歷結(jié)果次序不唯一?！秽徑泳仃嚮蜞徑颖?，指定初始點(diǎn)不同，結(jié)果次序也不同?！徑泳仃噷?shí)現(xiàn)算法時間復(fù)雜度為O(n2)；鄰接表實(shí)現(xiàn)算法時間復(fù)雜度為O(e)；兩者空間復(fù)雜度都為O(n)。back廣度優(yōu)先搜索(breadth-firstsearch)遍歷廣度優(yōu)先搜索遍歷的定義----首先訪問初始點(diǎn)vi，visited[i]=1，接著訪問vi的所有未被訪問的鄰接點(diǎn)，其訪問順序任意，假定依次為vi1,vi2,…vit，并標(biāo)記為已訪問過，然后再按照vi1,vi2,…vit的次序，訪問每一頂點(diǎn)所有未被訪問過的鄰接點(diǎn)(次序任意)，并均標(biāo)記為已訪問過，以此類推，直到圖中所有和初始點(diǎn)vi有路徑相通的頂點(diǎn)都被訪問過。next廣度優(yōu)先搜索遍歷的過程：結(jié)合上圖分析以A頂點(diǎn)作為初始點(diǎn)的廣度優(yōu)先搜索遍歷過程。next⑴訪問初始頂點(diǎn)序號0的頂點(diǎn)A，visited[0]=1；⑵訪問A的所有未被訪問過的鄰接點(diǎn)：序號1的頂點(diǎn)B，序號2的頂點(diǎn)C，序號3的頂點(diǎn)D，visited[1]=1，visited[2]=1，visited[3]=1；⑶訪問序號1的頂點(diǎn)B的未被訪問的鄰接點(diǎn)序號4的頂點(diǎn)E，visited[4]=1，序號2的頂點(diǎn)C已被訪問；⑷訪問序號2的頂點(diǎn)C的所有未被訪問的鄰接點(diǎn)序號5的頂點(diǎn)F，visited[5]=1，序號0的頂點(diǎn)A和序號1的頂點(diǎn)B已被訪問；next⑸序號3的頂點(diǎn)D的鄰接點(diǎn)序號0的頂點(diǎn)A和序號5的頂點(diǎn)F均以被訪問，此步不訪問任何頂點(diǎn)；⑹訪問序號4的頂點(diǎn)E的未被訪問的鄰接點(diǎn)序號6的頂點(diǎn)G，visited[6]=1，序號1的頂點(diǎn)B已被訪問；⑺訪問序號5的頂點(diǎn)F的未被訪問的鄰接點(diǎn)序號7的頂點(diǎn)H，visited[7]=1，序號2的頂點(diǎn)C和序號3的頂點(diǎn)D已被訪問；next⑻序號6的頂點(diǎn)G的鄰接點(diǎn)序號4的頂點(diǎn)E已被訪問，此步不訪問任何頂點(diǎn)；⑼訪問序號7的頂點(diǎn)H的未被訪問的鄰接點(diǎn)序號8的頂點(diǎn)I，visited[8]=1，序號5的頂點(diǎn)F已被訪問；⑽序號8的頂點(diǎn)I的鄰接點(diǎn)序號7的頂點(diǎn)H已被訪問，至此9個頂點(diǎn)都已被訪問過，遍歷結(jié)束。以上遍歷的結(jié)果次序?yàn)椋篈,B,C,D,E,F,G,H,Inext廣度優(yōu)先搜索遍歷算法描述：先被訪問的頂點(diǎn)，其鄰接點(diǎn)也先被訪問，使用隊(duì)列，用來一次記住被訪問過的頂點(diǎn)。算法開始時，將初始點(diǎn)vi訪問后入隊(duì)列，以后每從隊(duì)列出隊(duì)一元素，就依次訪問它的每個未被訪問過的鄰接點(diǎn)并令其入隊(duì)，當(dāng)隊(duì)列為空時，那么算法結(jié)束?！徑泳仃噷?shí)現(xiàn)▲鄰接表實(shí)現(xiàn)next鄰接矩陣實(shí)現(xiàn)算法7-6p139#defineMS20voidBFS1(AdjmatrixGA,inti,intn){intQ[MS],front=0,rear=0,j,k;printf(“%d〞,i);visited[i]=1;rear=(rear+1)%MS;if(front==rear){printf(“\n隊(duì)列空間用完！\n〞);exit(1);}Q[rear]=i;nextwhile(front!=rear){front=(front+1)%MS;k=Q[front];for(j=0;j<n;j++){if(GA[k][j]!=0&&GA[k][j]!=MaxValue&&!visited[j]){printf(“%d〞,j);visited[j]=1;rear=(rear+1)%MS;if(front==rear){printf(“隊(duì)列空間用完!\n〞);exit(1);}Q[rear]=j;}}}}back鄰接表實(shí)現(xiàn)算法7-7p140structQueueSq;voidBFS2(AdjlistGL,inti,intn){structQueueSqQ;InitQueue(&Q);printf(“%d〞,i);visited[i]=1;EnQueue(&Q,i);nextwhile(!EmptyQueue(&Q)){intk=OutQueue(&Q);Edgenode*p=GL[k];while(p){intj=p->adjvex;if(!visited[j]){printf(“%d〞,j);visited[j]=1;EnQueue(&Q,j);}p=p->next;}}}back算法性能分析：▲鄰接矩陣表示的廣度優(yōu)先搜索遍歷算法時間復(fù)雜度為O(n2)；▲鄰接表表示的廣度優(yōu)先搜索遍歷算法時間復(fù)雜度為O(e)；▲兩者的空間間復(fù)雜度均為O(n)?！徑泳仃噷?shí)現(xiàn)的訪問結(jié)果唯一，鄰接表實(shí)現(xiàn)的結(jié)果不唯一。back非連通圖的遍歷對于無向非連通圖或者有向非強(qiáng)連通圖，從初始點(diǎn)出發(fā)使用DSF或者BSF算法都不能遍歷圖中所有頂點(diǎn)。需要從未被訪問的頂點(diǎn)中再選一些頂點(diǎn)作為初始點(diǎn)進(jìn)行搜索遍歷，直到圖中所有頂點(diǎn)都備訪問過為止。要實(shí)現(xiàn)訪問到圖中所有頂點(diǎn)，那么以圖中未被訪問到的每個頂點(diǎn)作為初始點(diǎn)調(diào)用DSF或BSF即可。next圖的遍歷算法的上機(jī)調(diào)試假定選用鄰接矩陣作圖的存儲結(jié)構(gòu)，上機(jī)調(diào)試程序分三個文件：▲圖的遍歷運(yùn)算.h保存常量、全局變量、類型定義以及運(yùn)算函數(shù)的聲明▲圖的遍歷運(yùn)算函數(shù).c保存建立圖的鄰接矩陣、深度搜索遍歷、廣度搜索遍歷算法定義▲圖的遍歷運(yùn)算主程序.c保存主函數(shù)back圖的遍歷運(yùn)算.hp142-143#include<stdio.h>#include<stdlib.h>#defineMaxEdgeNum20#defineMaxValue1000#defineMS20typedefintVertexType;typedefVertexTypeVexlist[MaxVertexNum];nexttypedefintAdjmatrix[MaxVertexNum][MaxVertexNum];intvisited[MaxVertexNum];voidCreate1(VexlistGV,AdjmatrixGA,intn,inte);voidDSF1(AdjmatrixGA,inti,intn);voidBFS1(AdjmatrixGA,inti,intn);back圖的遍歷運(yùn)算函數(shù).cp143#include“圖的遍歷運(yùn)算.h〞voidCreate1(VexlistGV,AdjmatrixGA,intn,inte){/*略*/}voidDFS1(AdjmatrixGA,inti,intn){/*略*/}voidBSF1(AdjmatrixGA,inti,intn){/*略*/}back圖的遍歷運(yùn)算主程序.cp141-142voidmain(){inti,n,e;Vexlistgv;Adjmatrixga;printf(“\n輸入待處理圖的頂點(diǎn)數(shù)和邊數(shù)：〞);scanf(“%d%d〞,&n,&e);Create1(gv,ga,n,e);nextprintf(“按鄰接矩陣得到深度優(yōu)先遍歷序列：\n〞);for(i=0;i<n;i++)visited[i]=0;DFS1(ga,0,n);printf(“\n〞);printf(“按鄰接表得到廣度優(yōu)先遍歷序列：\n〞);for(i=0;i<n;i++)visited[i]=0;BFS1(ga,0,n);printf(“\n〞);}back圖的生成樹和最小生成樹圖的生成樹和最小生成樹的概念克魯斯卡爾算法back圖的生成樹和最小生成樹的概念生成樹(spanningtree)：在一個連通圖G中，假設(shè)取它的全部頂點(diǎn)和一局部邊構(gòu)成一個子圖G‘，即V(G’)=V(G)和E(G’)?E(G)假設(shè)邊集E(G’)中的邊既能夠把圖中所有頂點(diǎn)連通而又不形成回路，那么稱子圖G‘是原圖G的一棵生成樹。next一個既包含連通圖G中所有n個頂點(diǎn)又沒有回路的子圖G‘(即生成樹)，必含有n-1條邊。構(gòu)造子圖G’：首先從圖G中提取任一個頂點(diǎn)參加G’中，以后每向G‘中參加一個頂點(diǎn)，都要參加以該頂點(diǎn)為一個端點(diǎn)，以已連通的頂點(diǎn)之中的一個頂點(diǎn)為另一個端點(diǎn)的一條邊，這樣既連通了該頂點(diǎn)又不會產(chǎn)生回路，進(jìn)行n-1次后，G’中共有n個頂點(diǎn)和n-1條邊。next同一個圖可以有不同的生成樹，只要能夠連通所有的頂點(diǎn)又不產(chǎn)生回路的任何子圖都是它的生成樹。對于一個連通網(wǎng)而言，生成樹不同，每棵樹的權(quán)(樹中所有便上的權(quán)值總和)也不同。具有最小權(quán)值的生成樹稱為圖的最小生成樹(minimunspanningtree)。back克魯斯卡爾(Kruskal)算法克魯斯卡爾算法的思路：▲假設(shè)G=(V,E)是一個具有n個頂點(diǎn)的連通網(wǎng)，T=(U,TE)是G的最小生成樹，U的初值等于V，即包含有G中全部頂點(diǎn)，TE初值為空。▲根本思路：將G的邊按權(quán)值從小到大順序依次選取，假設(shè)選取的邊使T不形成回路，那么將該邊并入TE，否那么舍棄，如此進(jìn)行下去，直到TE中有n-1條邊停止，那么T即為最小生成樹。next以以下圖來說明，設(shè)圖用邊集數(shù)組表示，且數(shù)組中各邊是按權(quán)值從小到大存儲的。fromvexendvexweight012345678next實(shí)現(xiàn)克魯斯卡爾算法的關(guān)鍵：如何判斷與參加T的邊是否與生成樹中已有邊形成回路。解決方法：▲將頂點(diǎn)劃分為不同集合，每個集合中的頂點(diǎn)表示一個無回路的連通分量。算法開始時，生成樹的頂點(diǎn)集U等于圖的定點(diǎn)集V，邊集TE=Φ，所以n個頂點(diǎn)分屬于n個集合，每個集合僅有一個頂點(diǎn)說明頂點(diǎn)間互不連通。next▲當(dāng)從邊集數(shù)組按次選取一條邊時：●假設(shè)兩端點(diǎn)分屬不同的集合，那么說明此邊連通了兩個不同的分量，無回路產(chǎn)生，此邊即可參加TE，且將兩個端點(diǎn)所在的兩個集合合并；●假設(shè)兩端點(diǎn)同屬一個集合，那么有回路產(chǎn)生，該邊放棄。▲如此反復(fù)，進(jìn)行n-1普及完成操作。next應(yīng)用克魯斯卡爾算法構(gòu)造最小生成樹的過程next克魯斯卡爾算法的具體實(shí)現(xiàn)：▲設(shè)邊集數(shù)組GE按照權(quán)值從小到大順序存儲圖的所有邊；▲同類型的數(shù)組C存儲最小生成樹的邊；▲鄰接矩陣s的每行存儲每個連通子圖的頂點(diǎn)集，假設(shè)該行的s[i][j]=1那么說明頂點(diǎn)vj屬于這個集合。next▲算法7-8p147-149voidKruskal(EdgesetGE,EdgesetC,intn){inti,j,k,d,m1,m2;int**s=(int**)calloc(n,sizeof(int*));for(i=0;i<n;i++)s[i]=(int*)calloc(n,sizeof(int));for(i=0;i<n;i++)for(j=0;j<n;j++)if(i==j)s[i][j]=1;elses[i][j]=0;nextk=1;//表示待獲取的最小生成樹邊數(shù)d=0;//表示GE中待掃描邊元素的下標(biāo)位置while(k<n){/*求邊GE[d]兩端點(diǎn)所在集合的序號m1和m2*/for(i=0;i<n;i++){if(s[i][GE[d].fromvex]==1)m1=i;if(s[i][GE[D].endvex]==1)m2=i;}next/*假設(shè)m1≠m2,那么邊GE[d]是所求,參加數(shù)組C*/if(m1!=m2){C[k-1]=GE[d];k++;/*合并兩頂點(diǎn)集，將一個置空*/for(j=0;j<n;j++){s[m1][j]=s[m1][j]||s[m2][j];s[m2][j]=0;}}d++;//d后移一個位置以掃描下一條邊}}▲算法時間復(fù)雜度和空間復(fù)雜度都為O(n2)。next克魯斯卡爾算法的程序調(diào)試p148-150(單文件結(jié)構(gòu)：求圖最小生成樹運(yùn)算主程序.c)#include<stdio.h>#include<stdlib.h>#defineMaxVertexNum12#defineMaxEdgeNum20nexttypedefintVertexType;typedefVertexTypeVexlist[MaxVertexNum];typedefstructedgeElem{intfromvex;intendvex;intweight;}EdgeElem;typedefEdgeElemEdgeset[MaxEdgeNum];next/*輸出邊集數(shù)組*/voidOutputEdgeset(EdgesetGE,inte){inti;for(i=0;i<e;i++)if(i<=e-2)printf(“(%d,%d,%d),〞,GE[i].fromvex,GE[i].endvex,GE[i].weight);elseprintf(“(%d,%d,%d)〞,GE[i].fromvex,GE[i].endvex,GE[i].weight);}next/*建立n個頂點(diǎn)e條邊的定點(diǎn)數(shù)組GV和邊集數(shù)組GE*/voidCreate3(VexlistGV,EdgesetGE,intn,inte){/*略*/}/*克魯斯卡爾算法*/voidKruskal(EdgesetGE,EdgesetC,intn){/*略*/}nextvoidmain(){intn,e;Vexlistgv;Edgesetge,c;printf(“輸入待處理圖的頂點(diǎn)數(shù)和邊數(shù)：〞);scanf(“%d%d〞,&n,&e);printf(“按權(quán)值從小到大次序輸入每條邊：\n〞);Create3(gv,ge,n,e);printf(“利用克魯斯卡爾算法求最小生成樹：\n〞);Kruskal(ge,c,n);OutputEdgeset(c,n-1);}back最短路徑無權(quán)圖最短路徑的概念：▲一個圖中，假設(shè)從一頂點(diǎn)到另一頂點(diǎn)存在一條路徑(無回路的簡單路徑)，那么稱其路徑長度等于該路徑上所經(jīng)過邊數(shù)目，也等于該路徑上的頂點(diǎn)數(shù)-1?！鴥身旤c(diǎn)間多條路徑中路徑長度最短的路徑叫做最短路徑，其路徑長度叫做最短路徑長度或最短距離。next有權(quán)圖最短路徑的概念：▲把從一個頂點(diǎn)i到途中其余任一頂點(diǎn)j的一條路徑所經(jīng)過的邊的權(quán)值之和定義為該路徑的帶全路徑長度?！鴥蓚€頂點(diǎn)間多條帶權(quán)路徑中帶權(quán)路徑長度最短(值最小)的路徑成為最短路徑，其權(quán)值稱做最短路徑長度或最短距離。next上圖中，v0到v4共有三條路徑：{0,4}帶權(quán)路徑長度100{0,1,2,4}帶權(quán)路徑長度70〔最短路徑〕{0,3,4}帶權(quán)路徑長度90next從一頂點(diǎn)到其余各頂點(diǎn)的最短路徑對于一個有n個頂點(diǎn)e條邊的圖G，從一源點(diǎn)vi到其余任一終點(diǎn)vj的最短路徑，可能是邊(i,j)或<i,j>，也可能是經(jīng)過k個(1≤k≤n-2，最經(jīng)過除源點(diǎn)到終點(diǎn)之外的所有頂點(diǎn))中間頂點(diǎn)和k+1條邊所形成的路徑。狄克斯特拉(Dijkstra)算法：求從源點(diǎn)i到途中其余每一頂點(diǎn)的最短路徑。back具體做法：按照從源點(diǎn)到其余每一頂點(diǎn)的最短路徑長度的升序一次求出從源點(diǎn)到各頂點(diǎn)的最短路徑及長度，每次求出從源點(diǎn)i到一個重點(diǎn)m的最短路徑及長度后，都要以該頂點(diǎn)m作為新考慮的中間點(diǎn)，用vi到vm的最短路徑和最短路徑長度對vi到其他尚未求出最短路徑的那些終點(diǎn)的當(dāng)前最短路徑及長度作必要的地修改，使之成為當(dāng)前新的最短路徑和最短路徑長度，進(jìn)行n-2次后算法結(jié)束。next數(shù)據(jù)結(jié)構(gòu)：⑴設(shè)置一集合S，保存已求的最短路徑的終點(diǎn)序號，初值僅有源點(diǎn)i，以后每求出一個從i到終點(diǎn)m的最短路徑，就將該頂點(diǎn)m并入S集，以便作為新考慮的中間點(diǎn)；⑵設(shè)置一具有權(quán)值類型的一維數(shù)組dist[n]，dist[j]保存從源點(diǎn)i到終點(diǎn)j的目前最短路徑長度，初值為<i,j>或(i,j)的權(quán)值，無邊那么為MaxValue，每考慮一新中間點(diǎn)時，dist[j]值可能會變??；next⑶設(shè)置一個與dist數(shù)組對應(yīng)的類型為Edgenode*的一維指針數(shù)組path[n]，path[j]指向一保存著從源點(diǎn)i到終點(diǎn)j的目前最短路徑的單鏈表(即一個頂點(diǎn)序列)，當(dāng)vi到vj有邊時，那么path[j]初始指向由頂點(diǎn)i和j構(gòu)成的單鏈表，否那么為空。算法執(zhí)行過程：⑴從S外的頂點(diǎn)(待求最短路徑的終點(diǎn))所對應(yīng)的dist數(shù)組中，找最小值元素dist[m]；⑵把已求得最短路徑的終點(diǎn)m并入S；next⑶以vm作為新考慮中間點(diǎn)，對S外每個頂點(diǎn)j，假設(shè)dist[m]+GA[m][j](GA是鄰接矩陣)<dist[j]，那么是參加中間點(diǎn)vm后路徑變短，那么以之替換dist[j]原值，同時把path[m]單鏈表復(fù)制到path[j]上，并在其后插入vj接點(diǎn)，構(gòu)成從源點(diǎn)i到終點(diǎn)j的目前最短路徑；⑷重復(fù)n-2次⑴⑵⑶，即可在dist數(shù)組中得到從源點(diǎn)i到其余每個頂點(diǎn)的最短路徑長度，在path數(shù)組中得到相應(yīng)的最短路徑。next算法改進(jìn)：為方便，可采用一維數(shù)組s[n]保存已求得最短路徑的終點(diǎn)集合S。▲具體做法：假設(shè)頂點(diǎn)j在S中，那么令數(shù)組s[j]值為真，否那么為假。當(dāng)判斷一頂點(diǎn)j是否在S外時，只需要判斷s[j]是否為假即可。next初始化：s、dist、path數(shù)組的初值如以下圖：⑴從s元素為0的對應(yīng)dist中，找值最小元素dist[1]=10，第一個終點(diǎn)為v1，最短距離dist[1]=10，最短路徑path[1]={0,1}，s[1]=1。以v1為新中間點(diǎn)，對s數(shù)組中元素為0的每個頂點(diǎn)j(2≤j≤4)的目前最短路徑長度dist[j]和path[j]進(jìn)行修改：10000010∞30100v0v1v0v3v0v401234sdistpathnextdist[1]+GA[1][2]=10+50=60<(dist[2]=∞)，dist[2]=60，path[1]={0,1,2}；dist[1]+GA[1][3]=10+∞=∞，不修改；dist[1]+GA[1][4]=10+∞=∞，不修改。經(jīng)修改后的s、dist、path三個數(shù)組如下：01234110000106030100v0v1v0v1v2v0v3v0v4sdistpathnext⑵從s數(shù)組中元素為0的對應(yīng)dist中查找值最小的元素dist[3]=30，第二個終點(diǎn)v3，最短距離dist[3]=30，最短路徑path[3]={0,3}，s[3]=1。以v3為新中間點(diǎn)，對s中元素為0的每個頂點(diǎn)(j=2,4)的dist[j]和path[j]進(jìn)行修改：dist[3]+GA[3][2]=30+20=50<(dist[2]=60)，dist[2]=50，path[3]={0,3,2}；dist[3]+GA[3][4]=30+60=90<(dist[4]=100)，dist[4]=90，paht[4]={0,3,4}。經(jīng)過修改后的s、dist、path三個數(shù)組如下：next11010010603090v0v1v0v3v2v0v3v0v3v4⑶從s數(shù)組0元素對應(yīng)dist找值最小元素dist[2]=50，第三個終點(diǎn)v2，最短距離dist[2]=50，最短路徑path[2]={0,3,2}，s[2]=1。以v2為新中間點(diǎn)，對s中元素為假的頂點(diǎn)(j=4)的dist[4]和path[4]進(jìn)行修改：01234sdistpathnextdist[2]+GA[2][4]=50+10=60<(dist[4]=90)，dist[4]=60，path[4]={0,3,2,4}。經(jīng)過修改后的s、dist、path三數(shù)組如下：因?yàn)閳D中僅有5個頂點(diǎn)，只需運(yùn)算n-2=3次，v4頂點(diǎn)雖未參加S，但其最短路徑及最短路距離已確定，整個運(yùn)算結(jié)束。0123411110010503060v0v1v0v3v2v0v3v0v3v2v4sdistpathback拓?fù)渑判蛞粋€較大的工程往往被劃分成許多子工程，這些子工程一般稱作活動(activity)?；顒又g可能彼此之間具有先決條件約束等。用頂點(diǎn)表示活動，邊表示活動間先后關(guān)系的有向圖稱做頂點(diǎn)活動網(wǎng)絡(luò)(activityonvertexnetwork)，簡稱AOV網(wǎng)絡(luò)。例如，計算機(jī)專業(yè)學(xué)生的學(xué)習(xí)就是一個工程，每一門課程的學(xué)習(xí)就是整個工程的一些活動。其中有些課程要求先修課程，有些那么不要求。這樣在有的課程之間有領(lǐng)先關(guān)系，有