圖在日常生活及科學(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是頂點集，V={vi|0≤i≤n-1，n≥0，vi∈VertexType}，VertexType是頂點值類型，n為頂點數(shù)，n=0時V是空集；E是V上二元關(guān)系，即V上頂點序偶<x,y>(有向邊)或無序?qū)?x,y)(無向邊)的集合，即是邊集合?！鴮τ赩上的每個頂點，在E中都允許有任意多個前驅(qū)和后繼。next▲圖的二元組的另一個定義：圖由頂點集(vertexset)V(G)和邊集(edgeset)E(G)所組成。假設(shè)V(G)為空，那么E(G)也必然為空；假設(shè)V(G)非空，那么E(G)不一定非空?！邢驁D(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ù)語▲端點和鄰接點▲頂點的度、入度、出度▲完全圖、稠密圖、稀疏圖▲子圖▲路徑和回路▲連通和連通分量▲強連通圖和強連通分量▲權(quán)和網(wǎng)back端點(endpoint)和鄰接點(adjacent)在一無向圖中，假設(shè)有邊(vi,vj)，那么稱vi，vj為此邊的兩個端點，并稱它們互為鄰接點。在一有向圖中，假設(shè)有邊<vi,vj>，那么稱此邊是頂點vi的一條出邊(outedge)，頂點vj的一條入邊(inedge)；vi是此邊的起點/始點，vj是此邊的終點；稱vi和vj互為鄰接點，并稱vj是vi的出邊鄰接點，vi是vj的入邊鄰接點。back頂點的度、入度、出度無向圖中頂點v的度(deree)----D(v)定義為以該頂點為一個端點的邊的數(shù)目。有向圖中頂點v的度等于它的入度(ID(v))和出度(OD(v))之和，即D(v)=ID(v)+OD(v)?！攵?indegree)----ID(v)是該頂點的入邊數(shù)目?！龆?outdegree)----OD(v)是該頂點的出邊數(shù)目。next假設(shè)一個圖有n個頂點和e條邊，那么該圖所有頂點的度同邊數(shù)e滿足一下關(guān)系：證明：∵每條邊連接著兩個頂點，∴每個頂點的度數(shù)分別加1，總和加2，∴全部頂點的度數(shù)為所有邊數(shù)的2倍。back完全圖、稠密圖、稀疏圖完全圖----假設(shè)無向圖中的每兩個頂點間都存在一條邊，有向圖中每兩個頂點間都存在反方向的兩條邊，那么稱這樣的圖為完全圖。無向完全圖包含有n(n-1)/2條邊；有向完全圖包含有n(n-1)條邊。稠密圖----一個圖接近完全圖時。稀疏圖----一個圖含有較少的邊數(shù)時。back子圖設(shè)有兩個圖G=(V,E)和G’=(V’,E’)，假設(shè)V’?V，且E’?E，并且E’中的邊所涉及的頂點均屬于V’，那么稱G’是G的子圖。back路徑和回路在一圖G中，從頂點v到頂點v’的一條路徑(path)是一個頂點序列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ù)目。簡單路徑----指一條路徑上的所有頂點均不同。復(fù)雜路徑----指一條路徑上的頂點有所重復(fù)?；芈?環(huán)cycle)----指一條路徑上的前后兩端點相同。back連通和連通分量在無向圖G中，假設(shè)從頂點vi到頂點vj有路徑，那么稱vi和vj是連通的。假設(shè)圖G中任意兩個頂點都是連通的，那么稱G為連通圖，否那么為非連通圖。無向圖G的極大連通子圖稱為G的連通分量。一個連通圖有多個連通分量，且每個連通分量都能連通所有頂點；而非連通圖的每個連通分量只能連通其中一局部頂點，不能連通全部頂點。back強連通圖和強連通分量在有向圖G中，假設(shè)從頂點vi到vj有路徑，那么稱從vi到vj是連通的。假設(shè)有向圖G中任意兩個頂點vi和vj都連通，即從vi到vj都存在路徑，那么稱有向圖G是強連通圖。有向圖G的極大連通子圖稱為G的強連通分量。一個強連通的有向圖至少包含一個強連通分量；一個非強連通的有向圖一定包含多個強連通分量。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)鄰接矩陣是表示圖中頂點間相鄰關(guān)系的矩陣。設(shè)G=(V,E)是具有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è)為有效值那么邊存在，否那么不存在。也便于查找圖中任意頂點的度，時間復(fù)雜度為O(n)。例：在無向圖中，統(tǒng)計第i行(列)有效元素個數(shù)可得頂點vi的度；在有向圖中，統(tǒng)計第i行有效元素個數(shù)可得頂點vi的出度，統(tǒng)計第i列有效元素個數(shù)可得頂點vi的入度。next查找任一頂點的鄰接點也同樣方便，依次查找一個頂點所有鄰接點(出邊鄰接點或入邊鄰接點)時間復(fù)雜度為O(n)。例：查找vi的一個鄰接點(無向圖)或出邊鄰接點(有向圖)，只要在第i行上查找出一個有效元素，以該元素所在列號j為序號的頂點vj就是所求。空間復(fù)雜度：鄰接矩陣存儲需要占用n*n個整數(shù)存儲位置表示頂點的相鄰關(guān)系，還需要一個n個元素的一維數(shù)組存儲頂點信息，空間復(fù)雜度為O(n2)。適合稠密圖。next鄰接矩陣的類型定義：#defineMaxVertexNum8#defineMaxEdgeNum20#defineMaxValue1000typedefintVertexType;typedefVertexTypeVexlist[MaxVertexNum];typedefintAdjmatrix[MaxVertexNum][MaxVertexNum];next算法7-1生成無向帶權(quán)圖頂點數(shù)組和鄰接矩陣的算法p128-129voidCreate1(VexlistGV,AdjmatrixGA,intn,inte){inti,j,k,w;printf(“輸入%d個頂點數(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)鄰接表是對圖中每個頂點建立一個鄰接關(guān)系的單鏈表，并把它們的表頭指針用向量存儲的一種圖的表示方法。為頂點vi建立的鄰接關(guān)系的單鏈表稱做vi鄰接表。鄰接表中每個結(jié)點存儲該頂點為端點/起點的一條邊的信息，稱為邊結(jié)點。next無向圖的vi鄰接表的邊結(jié)點數(shù)，等于vi的邊數(shù)/鄰接點數(shù)/度數(shù)；有向圖的vi鄰接表的邊結(jié)點數(shù)，等于vi的出邊數(shù)/出邊鄰接點數(shù)/出度數(shù)。邊結(jié)點包含三個域：▲鄰接點域(adjvex)：存儲頂點vi的一個鄰接頂點vj的序號j；▲權(quán)域(weight)：存儲邊(vi,vj)/<vi,vj>的權(quán)；(無權(quán)圖不需要)▲鏈域(next)：用以鏈接下一個邊結(jié)點next用一個n個元素的一維數(shù)組存儲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個頂點數(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圖的鄰接表中便于查找一個頂點的邊/出邊或鄰接點/出邊鄰接點，時間復(fù)雜度O(e/n)。例：只要首先從表頭向量中取出對應(yīng)表頭指針，然后從表頭指針出發(fā)進行查找即可。對于那些經(jīng)常需要查找頂點入邊/入邊鄰接點的運算，可以專門建立對應(yīng)的逆鄰接表(contraryadjacencylist)，該表每個頂點存儲所有入邊的信息，鄰接點域存儲的是入邊鄰接點的序號。next把有向圖的鄰接表和逆鄰接表結(jié)合起來構(gòu)成十字鄰接表(orthogonaladjacencylist)。在十字鄰接表中，每個邊結(jié)點對應(yīng)圖中一條有向邊，包含5個域：邊起點域、邊終點域、邊上權(quán)域、入邊鏈域，出邊鏈域。入邊鏈域指向同一頂點的下條入邊結(jié)點。出邊鏈域指向同一頂點的下條出邊結(jié)點。表頭向量中的每個分量包括兩個與：入邊表的表頭指針域和出邊表的表頭指針域。next有向圖的十字鄰接表：next圖的鄰接表、逆鄰接表、十字鄰接表表示中，表頭指針向量數(shù)組占用n個或2n個指針存儲空間，所有邊結(jié)點需要占用2e(無向圖)或e(有向圖)個邊結(jié)點空間，空間復(fù)雜度為O(n+e)。適合于稀疏圖。圖的鄰接表與鄰接矩陣的關(guān)系：鄰接表中每個頂點vi的單鏈表對應(yīng)鄰接矩陣的第i行；你連接表中每個頂點vi的單鏈表對應(yīng)鄰接矩陣的第i列。back邊集數(shù)組(edgesetarray)邊集數(shù)組是利用一維數(shù)組存儲圖中所有邊的一種圖的表示法。數(shù)組中每個元素用來存儲一條邊的起點、終點、權(quán)值。邊集數(shù)組織存儲邊的信息，假設(shè)需要存儲頂點信息同樣需要一個n個元素的一維數(shù)組。next000112123233012345起點終點001123344152634656281016141222182524012345678起點終點權(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個頂點數(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ù)組中查找一條邊或一個頂點的度的時間復(fù)雜度為O(e)。邊集數(shù)組適合那些對邊依次進行處理的運算，不適合對頂點的運算，也不適合對任一條邊的運算。邊集數(shù)組的空間復(fù)雜度為O(e)，適合表示稀疏圖。back圖的遍歷圖的遍歷就是從初始點出發(fā)，按照一定的搜索方法對圖中的所有頂點各做一次訪問的過程。設(shè)置輔助數(shù)組visited[n]，記住每個頂點是否被訪問過。元素值0說明未訪問過，1表示已經(jīng)訪問過。圖的遍歷有兩種方法：▲深度優(yōu)先搜索遍歷▲廣度優(yōu)先搜索遍歷next深度優(yōu)先搜索(depth-firstsearch)遍歷深度有限搜索遍歷的定義----一個遞歸過程：首先訪問一個頂點vi(一開始為初始點)，并標(biāo)記visited[i]=1；然后從vi的任一未被訪問過的鄰接點/出邊鄰接點出發(fā)進行深度優(yōu)先搜索遍歷，當(dāng)vi所有鄰接點均被訪問過，那么退回到上一頂點vk，從vk的另一未被訪問過的鄰接點出發(fā)進行深度優(yōu)先搜索遍歷，直到退回到初始點且沒有未被訪問過的鄰接點為止。next深度優(yōu)先搜索遍歷的過程：結(jié)合上圖分析以A頂點作為初始點的深度優(yōu)先搜索遍歷過程。next⑴訪問序號為0的頂點A，visited[0]=1，從A的一個未被訪問的鄰接點序號為1的頂點B(A的三個鄰接點B、C、D都未被訪問過，假定先取B訪問)出發(fā)進行深度優(yōu)先搜索遍歷；⑵訪問頂點B，visited[1]=1，從B的一個未被訪問的鄰接點序號為2的頂點E(B的三個鄰接點僅A被訪問過，E、C都未被訪問過，假定先取E訪問)出發(fā)進行深度優(yōu)先搜索遍歷；⑶訪問頂點E，visited[2]=1，從E僅有的一個未被訪問的鄰接點序號為3的頂點G(E的另一個鄰接點B已經(jīng)被訪問過)出發(fā)進行深度優(yōu)先搜索遍歷；next⑷訪問頂點G，visited[3]=1，G僅有一個鄰接點E且已經(jīng)被訪問過，原路退回到上一頂點E，E的兩個鄰接點B、G都已經(jīng)被訪問過，原路退回到到上一頂點B，選取B剩下的另一未被訪問的鄰接點序號為4的頂點C(B另外兩個鄰接點A、E都已經(jīng)被訪問過)出發(fā)進行深度優(yōu)先搜索遍歷；⑸訪問頂點C，visited[4]=1，從C的一個未被訪問的鄰接點序號為5的頂點E(C的兩個鄰接點A已經(jīng)被訪問過，僅剩下F未被訪問)出發(fā)進行深度優(yōu)先搜索遍歷；next⑹訪問頂點F，visited[5]=1，從F的一個未被訪問的鄰接點序號為6的頂點D(F的三個鄰接點中C已被訪問過，D、H未被訪問過，假定先取D訪問)出發(fā)進行深度優(yōu)先搜索遍歷；⑺訪問頂點D，visited[6]=1，D的兩個鄰接點A、F已被訪問過，原路退回上一頂點F，再取F的另外一個未被訪問的鄰接點序號為7的頂點H(F的兩個鄰接點D已被訪問，僅剩下H)出發(fā)進行深度優(yōu)先搜索遍歷；next⑻訪問頂點H，visited[7]=1，從H的一個未被訪問的鄰接點序號為8的頂點I(H的兩個鄰接點中F已被訪問過，僅剩I未被訪問過)出發(fā)進行深度優(yōu)先搜索遍歷；⑼訪問頂點I，visited[8]=1，I的鄰接點H已被訪問，原路退回上一個頂點H，H的兩個鄰接點F、I已被訪問，再原路退回上一個頂點F，F(xiàn)的三個鄰接點C、D、H都已被訪問，在原路退回上一個頂點C，C的三個鄰接點點A、B、F都已被訪問，再原路退回上一頂點B，B的兩個鄰接點A、E都已被訪問，再原路退回上一頂點A，因為A是初始點，深度優(yōu)先搜索遍歷結(jié)束。next以上遍歷的結(jié)果次序為：A、B、E、G、C、F、D、H、I深度優(yōu)先搜索遍歷算法描述：過程是遞歸的；假定visited[MaxVertexNum]為保存頂點訪問標(biāo)記的全局?jǐn)?shù)組(初始化為0)?！徑泳仃噷崿F(xiàn)▲鄰接表實現(xiàn)next鄰接矩陣實現(xiàn)算法7-4p136voidDFS1(AdjmatrixGA,inti,intn){intj;printf(“%d〞,i);//輸出被訪問頂點的序號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鄰接表實現(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算法性能分析：▲頂點序號確定的情況下，鄰接矩陣的表示唯一，從初始點出發(fā)進行深度優(yōu)先搜索遍歷結(jié)果次序唯一；鄰接表表示不唯一，所以從初始點出發(fā)進行深度優(yōu)先搜索遍歷結(jié)果次序不唯一。▲同一鄰接矩陣或鄰接表，指定初始點不同，結(jié)果次序也不同。▲鄰接矩陣實現(xiàn)算法時間復(fù)雜度為O(n2)；鄰接表實現(xiàn)算法時間復(fù)雜度為O(e)；兩者空間復(fù)雜度都為O(n)。back廣度優(yōu)先搜索(breadth-firstsearch)遍歷廣度優(yōu)先搜索遍歷的定義----首先訪問初始點vi，visited[i]=1，接著訪問vi的所有未被訪問的鄰接點，其訪問順序任意，假定依次為vi1,vi2,…vit，并標(biāo)記為已訪問過，然后再按照vi1,vi2,…vit的次序，訪問每一頂點所有未被訪問過的鄰接點(次序任意)，并均標(biāo)記為已訪問過，以此類推，直到圖中所有和初始點vi有路徑相通的頂點都被訪問過。next廣度優(yōu)先搜索遍歷的過程：結(jié)合上圖分析以A頂點作為初始點的廣度優(yōu)先搜索遍歷過程。next⑴訪問初始頂點序號0的頂點A，visited[0]=1；⑵訪問A的所有未被訪問過的鄰接點：序號1的頂點B，序號2的頂點C，序號3的頂點D，visited[1]=1，visited[2]=1，visited[3]=1；⑶訪問序號1的頂點B的未被訪問的鄰接點序號4的頂點E，visited[4]=1，序號2的頂點C已被訪問；⑷訪問序號2的頂點C的所有未被訪問的鄰接點序號5的頂點F，visited[5]=1，序號0的頂點A和序號1的頂點B已被訪問；next⑸序號3的頂點D的鄰接點序號0的頂點A和序號5的頂點F均以被訪問，此步不訪問任何頂點；⑹訪問序號4的頂點E的未被訪問的鄰接點序號6的頂點G，visited[6]=1，序號1的頂點B已被訪問；⑺訪問序號5的頂點F的未被訪問的鄰接點序號7的頂點H，visited[7]=1，序號2的頂點C和序號3的頂點D已被訪問；next⑻序號6的頂點G的鄰接點序號4的頂點E已被訪問，此步不訪問任何頂點；⑼訪問序號7的頂點H的未被訪問的鄰接點序號8的頂點I，visited[8]=1，序號5的頂點F已被訪問；⑽序號8的頂點I的鄰接點序號7的頂點H已被訪問，至此9個頂點都已被訪問過，遍歷結(jié)束。以上遍歷的結(jié)果次序為：A,B,C,D,E,F,G,H,Inext廣度優(yōu)先搜索遍歷算法描述：先被訪問的頂點，其鄰接點也先被訪問，使用隊列，用來一次記住被訪問過的頂點。算法開始時，將初始點vi訪問后入隊列，以后每從隊列出隊一元素，就依次訪問它的每個未被訪問過的鄰接點并令其入隊，當(dāng)隊列為空時，那么算法結(jié)束。▲鄰接矩陣實現(xiàn)▲鄰接表實現(xiàn)next鄰接矩陣實現(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隊列空間用完！\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(“隊列空間用完!\n〞);exit(1);}Q[rear]=j;}}}}back鄰接表實現(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)?！徑泳仃噷崿F(xiàn)的訪問結(jié)果唯一，鄰接表實現(xiàn)的結(jié)果不唯一。back非連通圖的遍歷對于無向非連通圖或者有向非強連通圖，從初始點出發(fā)使用DSF或者BSF算法都不能遍歷圖中所有頂點。需要從未被訪問的頂點中再選一些頂點作為初始點進行搜索遍歷，直到圖中所有頂點都備訪問過為止。要實現(xiàn)訪問到圖中所有頂點，那么以圖中未被訪問到的每個頂點作為初始點調(diào)用DSF或BSF即可。next圖的遍歷算法的上機調(diào)試假定選用鄰接矩陣作圖的存儲結(jié)構(gòu)，上機調(diào)試程序分三個文件：▲圖的遍歷運算.h保存常量、全局變量、類型定義以及運算函數(shù)的聲明▲圖的遍歷運算函數(shù).c保存建立圖的鄰接矩陣、深度搜索遍歷、廣度搜索遍歷算法定義▲圖的遍歷運算主程序.c保存主函數(shù)back圖的遍歷運算.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圖的遍歷運算函數(shù).cp143#include“圖的遍歷運算.h〞voidCreate1(VexlistGV,AdjmatrixGA,intn,inte){/*略*/}voidDFS1(AdjmatrixGA,inti,intn){/*略*/}voidBSF1(AdjmatrixGA,inti,intn){/*略*/}back圖的遍歷運算主程序.cp141-142voidmain(){inti,n,e;Vexlistgv;Adjmatrixga;printf(“\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è)取它的全部頂點和一局部邊構(gòu)成一個子圖G‘，即V(G’)=V(G)和E(G’)?E(G)假設(shè)邊集E(G’)中的邊既能夠把圖中所有頂點連通而又不形成回路，那么稱子圖G‘是原圖G的一棵生成樹。next一個既包含連通圖G中所有n個頂點又沒有回路的子圖G‘(即生成樹)，必含有n-1條邊。構(gòu)造子圖G’：首先從圖G中提取任一個頂點參加G’中，以后每向G‘中參加一個頂點，都要參加以該頂點為一個端點，以已連通的頂點之中的一個頂點為另一個端點的一條邊，這樣既連通了該頂點又不會產(chǎn)生回路，進行n-1次后，G’中共有n個頂點和n-1條邊。next同一個圖可以有不同的生成樹，只要能夠連通所有的頂點又不產(chǎn)生回路的任何子圖都是它的生成樹。對于一個連通網(wǎng)而言，生成樹不同，每棵樹的權(quán)(樹中所有便上的權(quán)值總和)也不同。具有最小權(quán)值的生成樹稱為圖的最小生成樹(minimunspanningtree)。back克魯斯卡爾(Kruskal)算法克魯斯卡爾算法的思路：▲假設(shè)G=(V,E)是一個具有n個頂點的連通網(wǎng)，T=(U,TE)是G的最小生成樹，U的初值等于V，即包含有G中全部頂點，TE初值為空?！舅悸罚簩的邊按權(quán)值從小到大順序依次選取，假設(shè)選取的邊使T不形成回路，那么將該邊并入TE，否那么舍棄，如此進行下去，直到TE中有n-1條邊停止，那么T即為最小生成樹。next以以下圖來說明，設(shè)圖用邊集數(shù)組表示，且數(shù)組中各邊是按權(quán)值從小到大存儲的。fromvexendvexweight012345678next實現(xiàn)克魯斯卡爾算法的關(guān)鍵：如何判斷與參加T的邊是否與生成樹中已有邊形成回路。解決方法：▲將頂點劃分為不同集合，每個集合中的頂點表示一個無回路的連通分量。算法開始時，生成樹的頂點集U等于圖的定點集V，邊集TE=Φ，所以n個頂點分屬于n個集合，每個集合僅有一個頂點說明頂點間互不連通。next▲當(dāng)從邊集數(shù)組按次選取一條邊時：●假設(shè)兩端點分屬不同的集合，那么說明此邊連通了兩個不同的分量，無回路產(chǎn)生，此邊即可參加TE，且將兩個端點所在的兩個集合合并；●假設(shè)兩端點同屬一個集合，那么有回路產(chǎn)生，該邊放棄?！绱朔磸?fù)，進行n-1普及完成操作。next應(yīng)用克魯斯卡爾算法構(gòu)造最小生成樹的過程next克魯斯卡爾算法的具體實現(xiàn)：▲設(shè)邊集數(shù)組GE按照權(quán)值從小到大順序存儲圖的所有邊；▲同類型的數(shù)組C存儲最小生成樹的邊；▲鄰接矩陣s的每行存儲每個連通子圖的頂點集，假設(shè)該行的s[i][j]=1那么說明頂點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]兩端點所在集合的序號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++;/*合并兩頂點集，將一個置空*/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)：求圖最小生成樹運算主程序.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個頂點e條邊的定點數(shù)組GV和邊集數(shù)組GE*/voidCreate3(VexlistGV,EdgesetGE,intn,inte){/*略*/}/*克魯斯卡爾算法*/voidKruskal(EdgesetGE,EdgesetC,intn){/*略*/}nextvoidmain(){intn,e;Vexlistgv;Edgesetge,c;printf(“輸入待處理圖的頂點數(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è)從一頂點到另一頂點存在一條路徑(無回路的簡單路徑)，那么稱其路徑長度等于該路徑上所經(jīng)過邊數(shù)目，也等于該路徑上的頂點數(shù)-1?！鴥身旤c間多條路徑中路徑長度最短的路徑叫做最短路徑，其路徑長度叫做最短路徑長度或最短距離。next有權(quán)圖最短路徑的概念：▲把從一個頂點i到途中其余任一頂點j的一條路徑所經(jīng)過的邊的權(quá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從一頂點到其余各頂點的最短路徑對于一個有n個頂點e條邊的圖G，從一源點vi到其余任一終點vj的最短路徑，可能是邊(i,j)或<i,j>，也可能是經(jīng)過k個(1≤k≤n-2，最經(jīng)過除源點到終點之外的所有頂點)中間頂點和k+1條邊所形成的路徑。狄克斯特拉(Dijkstra)算法：求從源點i到途中其余每一頂點的最短路徑。back具體做法：按照從源點到其余每一頂點的最短路徑長度的升序一次求出從源點到各頂點的最短路徑及長度，每次求出從源點i到一個重點m的最短路徑及長度后，都要以該頂點m作為新考慮的中間點，用vi到vm的最短路徑和最短路徑長度對vi到其他尚未求出最短路徑的那些終點的當(dāng)前最短路徑及長度作必要的地修改，使之成為當(dāng)前新的最短路徑和最短路徑長度，進行n-2次后算法結(jié)束。next數(shù)據(jù)結(jié)構(gòu)：⑴設(shè)置一集合S，保存已求的最短路徑的終點序號，初值僅有源點i，以后每求出一個從i到終點m的最短路徑，就將該頂點m并入S集，以便作為新考慮的中間點；⑵設(shè)置一具有權(quán)值類型的一維數(shù)組dist[n]，dist[j]保存從源點i到終點j的目前最短路徑長度，初值為<i,j>或(i,j)的權(quán)值，無邊那么為MaxValue，每考慮一新中間點時，dist[j]值可能會變??；next⑶設(shè)置一個與dist數(shù)組對應(yīng)的類型為Edgenode*的一維指針數(shù)組path[n]，path[j]指向一保存著從源點i到終點j的目前最短路徑的單鏈表(即一個頂點序列)，當(dāng)vi到vj有邊時，那么path[j]初始指向由頂點i和j構(gòu)成的單鏈表，否那么為空。算法執(zhí)行過程：⑴從S外的頂點(待求最短路徑的終點)所對應(yīng)的dist數(shù)組中，找最小值元素dist[m]；⑵把已求得最短路徑的終點m并入S；next⑶以vm作為新考慮中間點，對S外每個頂點j，假設(shè)dist[m]+GA[m][j](GA是鄰接矩陣)<dist[j]，那么是參加中間點vm后路徑變短，那么以之替換dist[j]原值，同時把path[m]單鏈表復(fù)制到path[j]上，并在其后插入vj接點，構(gòu)成從源點i到終點j的目前最短路徑；⑷重復(fù)n-2次⑴⑵⑶，即可在dist數(shù)組中得到從源點i到其余每個頂點的最短路徑長度，在path數(shù)組中得到相應(yīng)的最短路徑。next算法改進：為方便，可采用一維數(shù)組s[n]保存已求得最短路徑的終點集合S?！唧w做法：假設(shè)頂點j在S中，那么令數(shù)組s[j]值為真，否那么為假。當(dāng)判斷一頂點j是否在S外時，只需要判斷s[j]是否為假即可。next初始化：s、dist、path數(shù)組的初值如以下圖：⑴從s元素為0的對應(yīng)dist中，找值最小元素dist[1]=10，第一個終點為v1，最短距離dist[1]=10，最短路徑path[1]={0,1}，s[1]=1。以v1為新中間點，對s數(shù)組中元素為0的每個頂點j(2≤j≤4)的目前最短路徑長度dist[j]和path[j]進行修改：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，第二個終點v3，最短距離dist[3]=30，最短路徑path[3]={0,3}，s[3]=1。以v3為新中間點，對s中元素為0的每個頂點(j=2,4)的dist[j]和path[j]進行修改：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，第三個終點v2，最短距離dist[2]=50，最短路徑path[2]={0,3,2}，s[2]=1。以v2為新中間點，對s中元素為假的頂點(j=4)的dist[4]和path[4]進行修改：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ù)組如下：因為圖中僅有5個頂點，只需運算n-2=3次，v4頂點雖未參加S，但其最短路徑及最短路距離已確定，整個運算結(jié)束。0123411110010503060v0v1v0v3v2v0v3v0v3v2v4sdistpathback拓?fù)渑判蛞粋€較大的工程往往被劃分成許多子工程，這些子工程一般稱作活動(activity)?；顒又g可能彼此之間具有先決條件約束等。用頂點表示活動，邊表示活動間先后關(guān)系的有向圖稱做頂點活動網(wǎng)絡(luò)(activityonvertexnetwork)，簡稱AOV網(wǎng)絡(luò)。例如，計算機專業(yè)學(xué)生的學(xué)習(xí)就是一個工程，每一門課程的學(xué)習(xí)就是整個工程的一些活動。其中有些課程要求先修課程，有些那么不要求。這樣在有的課程之間有領(lǐng)先關(guān)系，有