【文章內(nèi)容簡介】 ear]=i。 next while(front!=rear) { front=(front+1)%MS。 k=Q[front]。 for(j=0。 jn。 j++) { if ( GA[k][j]!=0 amp。amp。 GA[k][j]!=MaxValue amp。amp。 !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) 算法 77 p140 struct QueueSq。 void BFS2(Adjlist GL,int i,int n) { struct QueueSq Q。 InitQueue(amp。Q)。 printf(“%d”,i)。 visited[i]=1。 EnQueue(amp。Q,i)。 next while(!EmptyQueue(amp。Q)) { int k=OutQueue(amp。Q)。 Edgenode *p=GL[k]。 while(p) { int j=padjvex。 if (!visited[j]) { printf(“%d”,j)。 visited[j]=1。 EnQueue(amp。Q,j)。 } p=pnext。 } } } back ? 算法性能分析： ▲鄰接矩陣表示的廣度優(yōu)先搜索遍歷算法時間復雜度為 O(n2)； ▲鄰接表表示的廣度優(yōu)先搜索遍歷算法時間復雜度為 O(e)； ▲兩者的空間間復雜度均為 O(n)。 ▲鄰接矩陣實現(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 圖的遍歷運算 .h p142143 include include define MaxEdgeNum 20 define MaxValue 1000 define MS 20 typedef int VertexType。 typedef VertexType Vexlist[MaxVertexNum]。 next typedef int Adjmatrix[MaxVertexNum][MaxVertexNum]。 int visited[MaxVertexNum]。 void Create1(Vexlist GV,Adjmatrix GA,int n,int e)。 void DSF1(Adjmatrix GA,int i,int n)。 void BFS1(Adjmatrix GA,int i,int n)。 back 圖的遍歷運算函數(shù) .c p143 include “圖的遍歷運算 .h” void Create1(Vexlist GV,Adjmatrix GA,int n,inte) { /* 略 */ } void DFS1(Adjmatrix GA,int i,int n) { /* 略 */ } void BSF1(Adjmatrix GA,int i,int n) { /* 略 */ } back 圖的遍歷運算主程序 .c p141142 void main( ) { int i,n,e。 Vexlist gv。 Adjmatrix ga。 printf(“\n輸入待處理圖的頂點數(shù)和邊數(shù)：” )。 scanf(“%d%d”,amp。n,amp。e)。 Create1(gv,ga,n,e)。 next printf(“按鄰接矩陣得到深度優(yōu)先遍歷序列： \n”)。 for(i=0。 in。 i++) visited[i]=0。 DFS1(ga,0,n)。 printf(“\n”)。 printf(“按鄰接表得到廣度優(yōu)先遍歷序列： \n”)。 for(i=0。 in。 i++) visited[i]=0。 BFS1(ga,0,n)。 printf(“\n”)。 } back 圖的生成樹和最小生成樹 ? 圖的生成樹和最小生成樹的概念 ? 克魯斯卡爾算法 back 圖的生成樹和最小生成樹的概念 ? 生成樹 (spanning tree)： 在一個連通圖 G中，若取它的全部頂點和一部分邊構(gòu)成一個子圖 G?，即 V(G?)=V(G) 和 E(G?)?E(G) 若邊集 E(G?)中的邊既能夠把圖中所有頂點連通而又不形成回路，則稱子圖 G?是原圖 G的一棵生成樹。 next ? 一個既包含連通圖 G中所有 n個頂點又沒有回路的子圖 G?(即生成樹 )，必含有 n1條邊。 ? 構(gòu)造子圖 G?： 首先從圖 G中提取任一個頂點加入 G?中，以后每向 G?中加入一個頂點，都要加入以該頂點為一個端點，以已連通的頂點之中的一個頂點為另一個端點的一條邊，這樣既連通了該頂點又不會產(chǎn)生回路，進行 n1次后， G?中共有 n個頂點和 n1條邊。 next ? 同一個圖可以有不同的生成樹，只要能夠連通所有的頂點又不產(chǎn)生回路的任何子圖都是它的生成樹。 ? 對于一個連通網(wǎng)而言，生成樹不同，每棵樹的權 (樹中所有便上的權值總和 )也不同。 ? 具有最小權值的生成樹稱為圖的 最小生成樹(minimun spanning tree)。 back 克魯斯卡爾 (Kruskal)算法 ? 克魯斯卡爾算法的思路： ▲假設 G=(V,E)是一個具有 n個頂點的連通網(wǎng)，T=(U,TE)是 G的最小生成樹， U的初值等于 V，即包含有 G中全部頂點， TE初值為空。 ▲基本思路： 將 G的邊按權值從小到大順序依次選取，若選取的邊使 T不形成回路，則將該邊并入TE，否則舍棄，如此進行下去，直到 TE中有n1條邊停止，則 T即為最小生成樹。 next ? 以下圖來說明，設圖用邊集數(shù)組表示，且數(shù)組中各邊是按權值從小到大存儲的。 fromvex endvex weight 0 1 2 3 4 5 6 7 8 next ? 實現(xiàn)克魯斯卡爾算法的關鍵： 如何判斷與加入 T的邊是否與生成樹中已有邊形成回路。 ? 解決方法： ▲將頂點劃分為不同集合，每個集合中的頂點表示一個無回路的連通分量。算法開始時，生成樹的頂點集 U等于圖的定點集 V，邊集TE=Φ，所以 n個頂點分屬于 n個集合，每個集合僅有一個頂點表明頂點間互不連通。 next ▲ 當從邊集數(shù)組按次選取一條邊時： ●若兩端點分屬不同的集合，則表明此邊連通了兩個不同的分量，無回路產(chǎn)生，此邊即可加入 TE，且將兩個端點所在的兩個集合合并； ●若兩端點同屬一個集合，則有回路產(chǎn)生，該邊放棄。 ▲如此反復，進行 n1遍及完成操作。 next 應用克魯斯卡爾算法構(gòu)造最小生成樹的過程 next ? 克魯斯卡爾算法的具體實現(xiàn)： ▲設邊集數(shù)組 GE按照權值從小到大順序存儲圖的所有邊； ▲同類型的數(shù)組 C存儲最小生成樹的邊； ▲鄰接矩陣 s的每行存儲每個連通子圖的頂點集，若該行的 s[i][j]=1則表明頂點 vj屬于這個集合。 next ▲ 算法 78 p147149 void Kruskal(Edgeset GE,Edgeset C,int n) { int i,j,k,d,m1,m2。 int **s=(int**)calloc(n,sizeof(int*))。 for(i=0。in。i++) s[i]=(int*)calloc(n,sizeof(int))。 for(i=0。in。i++) for(j=0。jn。j++) if(i==j) s[i][j]=1。 else s[i][j]=0。 next k=1。 //表示待獲取的最小生成樹邊數(shù) d=0。 //表示 GE中待掃描邊元素的下標位置 while(kn) { /*求邊 GE[d]兩端點所在集合的序號 m1和 m2*/ for(i=0。in。i++) { if (s[i][GE[d].fromvex]==1) m1=i。 if (s[i][GE[D].endvex]==1) m2=i。 } next /*若 m1≠m2,則邊 GE[d]是所求 ,加入數(shù)組 C*/ if (m1!=m2) { C[k1]=GE[d]。 k++。 /*合并兩頂點集，將一個置空 */ for(j=0。jn。j++) { s[m1][j]=s[m1][j] || s[m2][j]。 s[m2][j]=0。 } } d++。 //d后移一個位置以掃描下一條邊 } } ▲ 算法時間復雜度和空間復雜度都為 O(n2)。 next ? 克魯斯卡爾算法的程序調(diào)試 p148150 (單文件結(jié)構(gòu)：求圖最小生成樹運算主程序 .c) include include define MaxVertexNum 12 define MaxEdgeNum 20 next typedef int VertexType。 typedef VertexType Vexlist[MaxVertexNum]。 typedef struct edgeElem { int fromvex。 int endvex。 int weight。 } EdgeElem。 typedef EdgeElem Edgeset[MaxEdgeNum]。 next /*輸出邊集數(shù)組 */ void OutputEdgeset(Edgeset GE,int e) { int i。 for(i=0。ie。i++) if (i=e2) printf(“(%d,%d,%d),”,GE[i].fromvex, GE[i].endvex,GE[i].weight)。 else printf(“(%d,%d,%d)”,GE[i].fromvex, GE[i].endvex,GE[i].weight)。 } next /*建立 n個頂點 e條邊的定點數(shù)組 GV和邊集數(shù)組GE*/ void Create3(Vexlist GV,Edgeset GE,int n,int e) { /* 略 */ } /*克魯斯卡爾算法 */ void Kruskal(Edgeset GE,Edgeset C,int n) { /* 略 */ } next void main( ) { int n,e。 Vexlist gv。 Edgeset ge,c。 printf(“輸入待處理圖的頂點數(shù)和邊數(shù)：” )。