|
圖的基本操作算法
查看(2030) 回復(fù)(0) |
|
|
發(fā)表于 2010-08-24 00:04
樓主
1.void CreatGraph (AdjList g) //建立有n個(gè)頂點(diǎn)和m 條邊的無(wú)向圖的鄰接表存儲(chǔ)結(jié)構(gòu)
{ int n,m; scanf("%d%d",&n,&m); for(i =1,i<=n;i++) //輸入頂點(diǎn)信息,建立頂點(diǎn)向量 { scanf(&g.vertex); g.firstarc=null;} for(k=1;k<=m;k++) //輸入邊信息 { scanf(&v1,&v2); //輸入兩個(gè)頂點(diǎn) i=GraphLocateVertex (g,v1); j=GraphLocateVertex (g,v2); //頂點(diǎn)定位 p=(ArcNode *)malloc(sizeof(ArcNode)); //申請(qǐng)邊結(jié)點(diǎn) p->adjvex=j; p->next=g.firstarc; g.firstarc=p; //將邊結(jié)點(diǎn)鏈入 p=(ArcNode *)malloc(sizeof(ArcNode)); //無(wú)向圖雙向連接 p->adjvex=i; p->next=g[j].firstarc; g[j].firstarc=p; } }//算法CreatGraph結(jié)束 2.void CreatAdjList(AdjList g) //建立有向圖的鄰接表存儲(chǔ)結(jié)構(gòu) { int n; scanf("%d",&n); for (i=1;i<=n;j++) { scanf(&g.vertex); g.firstarc=null; }//輸入頂點(diǎn)信息 scanf(&v1, &v2); while(v1 && v2) //題目要求兩頂點(diǎn)之一為0表示結(jié)束 { i=GraphLocateVertex(g2,v1); p=(ArcNode*)malloc(sizeof(ArcNode)); //有向圖 只需要單邊 p->adjvex=j; p->next=g.firstarc; g.firstarc=p; scanf(&v1,&v2); } } 5．void InvertAdjList(AdjList gin,gout） //將有向圖的出度鄰接表改為按入度建立的逆鄰接表 { for(i=1;i<=n;i++) //設(shè)有向圖有n個(gè)頂點(diǎn)，建逆鄰接表的頂點(diǎn)向量。 { gin.vertex=gout.vertex; gin.firstarc=null; } //逆鄰接表 頂點(diǎn)初始化 for(i=1;i<=n;i++) //鄰接表轉(zhuǎn)為逆鄰接表 { p=gout.firstarc; //取指向鄰接表的指針 鄰接表 頭結(jié)點(diǎn)i的第一條邊 while(p!=null) { j=p->adjvex; // 鄰接表<i,j>邊結(jié)點(diǎn)中的j頂點(diǎn)信息 s=(ArcNode *)malloc(sizeof(ArcNode)); //申請(qǐng)逆鄰接表的邊結(jié)點(diǎn)空間 s->adjvex=i; //對(duì)逆鄰接表的<j,i>邊結(jié)點(diǎn) 頂點(diǎn)信息賦值 s->next=gin[j].firstarc; //對(duì)逆鄰接表的<j,i>邊結(jié)點(diǎn) 下一邊信息賦值 gin[j].firstarc=s; // <j,i>邊結(jié)點(diǎn)鏈入逆鄰接表 p=p->next; // 鄰接表中找下一個(gè)鄰接點(diǎn)。 }//while }//for } 6.void AdjListToAdjMatrix(AdjList gl, AdjMatrix gm) //將圖的鄰接表表示轉(zhuǎn)換為鄰接矩陣表示 { for(i=1;i<=n;i++) //設(shè)圖有n個(gè)頂點(diǎn)，鄰接矩陣初始化。 for(j=1;j<=n;j++) gm[j]=0; for(i=1;i<=n;i++) { p=gl.firstarc; //取第一個(gè)鄰接點(diǎn)。 while(p!=null) { gm[p->adjvex]=1; p=p->next; } //下一個(gè)鄰接點(diǎn) }//for }//算法結(jié)束 7.void AdjMatrixToAdjList( AdjMatrix gm, AdjList gl ) //圖的鄰接矩陣表示法轉(zhuǎn)換為鄰接表表示法 { for(i=1;i<=n;i++) //鄰接表表頭向量初始化。 { scanf(&gl.vertex); gl.firstarc=null; } for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(gm[j]==1) { p=(ArcNode *)malloc(sizeof(ArcNode)) ; //申請(qǐng)結(jié)點(diǎn)空間。 p->adjvex=j; //頂點(diǎn)i的鄰接點(diǎn)是j p->next=gl.firstarc; //下一個(gè)鄰接邊結(jié)點(diǎn) gl.firstarc=p; //鏈入頂點(diǎn)i的鄰接點(diǎn)鏈表中 } }//end [算法討論] 算法中鄰接表中頂點(diǎn)在向量表中的下標(biāo)與其在鄰接矩陣中的行號(hào)相同。 9.void DeletEdge(AdjList g,int i,j) //在用鄰接表方式存儲(chǔ)的無(wú)向圖g中，刪除邊(i,j) { p=g.firstarc; pre=null; //刪頂點(diǎn)i 的邊結(jié)點(diǎn)(i,j),pre是前驅(qū)指針 while(p) if(p->adjvex==j) //找到了要?jiǎng)h除的結(jié)點(diǎn) { if(pre==null) g.firstarc=p->next; //要?jiǎng)h除的是第一個(gè)鄰接點(diǎn)，重新設(shè)置第一鄰接點(diǎn) else pre->next=p->next; //要?jiǎng)h除的不是第一鄰接點(diǎn) 重新設(shè)置pre后鏈 跳過(guò)p 鏈上p->next free(p);} //釋放結(jié)點(diǎn)空間。 else { pre=p; p=p->next;} //沒(méi)找到，沿鏈表繼續(xù)查找 p=g[j].firstarc; pre=null; //刪頂點(diǎn)j 的邊結(jié)點(diǎn)(j,i) while(p) if(p->adjvex==i) { if(pre==null)g[j].firstarc=p->next; else pre->next=p->next; free(p);}//釋放結(jié)點(diǎn)空間。 else { pre=p; p=p->next;} //沿鏈表繼續(xù)查找 }// DeletEdge [算法討論] 算法中假定給的i，j 均存在，否則應(yīng)檢查其合法性。若未給頂點(diǎn)編號(hào)，而給出頂點(diǎn)信息，則先用頂點(diǎn)定位函數(shù)求出其在鄰接表頂點(diǎn)向量中的下標(biāo)i和j。 10.void DeleteArc（AdjList g,vertype vi,vj） //刪除以鄰接表存儲(chǔ)的有向圖g的一條弧<vi,vj>，假定頂點(diǎn)vi和vj存在 { i=GraphLocateVertex(g,vi); j=GraphLocateVertex(g,vj); //頂點(diǎn)定位 p=g.firstarc; pre=null; while(p) if(p->adjvex==j) { if(pre==null) g.firstarc=p->next; else pre->next=p->next; free(p);}//釋放結(jié)點(diǎn)空間。 else { pre=p; p=p->next;} }//結(jié)束 不用再查找j 比無(wú)向圖省事 ★★圖的遍歷算法★★ 12.在有向圖的鄰接表中，求頂點(diǎn)的出度容易，只要簡(jiǎn)單在該頂點(diǎn)的鄰接點(diǎn)鏈表中查結(jié)點(diǎn)個(gè)數(shù)即可。而求頂點(diǎn)的入度，則要遍歷整個(gè)鄰接表。 int count (AdjList g , int k ) //在n個(gè)頂點(diǎn)以鄰接表表示的有向圖g中，求指定頂點(diǎn)k(1<=k<=n)的入度。 { int count =0; for(i=1;i<=n;i++) //求頂點(diǎn)k的入度要遍歷整個(gè)鄰接表。 if(i!=k) //頂點(diǎn)k的鄰接鏈表不必計(jì)算 { p=g.firstarc;//取頂點(diǎn) i 的鄰接邊 while(p) { if(p->adjvex==k) count++; p=p->next; }//while }//if return(count); //頂點(diǎn)k的入度. } 8.在有向圖中，判斷頂點(diǎn)Vi和頂點(diǎn)Vj間是否有路徑，可采用遍歷的方法，從頂點(diǎn)Vi出發(fā)，不論是深度優(yōu)先遍歷（dfs）還是寬度優(yōu)先遍歷（bfs），在未退出dfs或bfs前,若訪問(wèn)到Vj，則說(shuō)明有通路，否則無(wú)通路。設(shè)一全程變量flag，初始化為0，若有通路，則flag=1。 算法1：int visited[]=0; //全局變量，訪問(wèn)數(shù)組初始化 int dfs(AdjList g , vertype vi ,vj) //以鄰接表為存儲(chǔ)結(jié)構(gòu)的有向圖g，判斷頂點(diǎn)Vi到Vj是否有通路,返回1或0表示有或無(wú) { visited[vi]=1; //visited是訪問(wèn)數(shù)組，假設(shè)頂點(diǎn)的信息就是頂點(diǎn)編號(hào)。 p=g[vi].firstarc; //第一個(gè)鄰接點(diǎn)。 while( p!=null) { j=p->adjvex; if (j==vj) { flag=1; return（1）;} //vi 和 vj 有通路。 if (visited[j]==0) dfs(g,j,vj); //遞歸進(jìn)行深度遍歷 p=p->next； //遍歷完返回，繼續(xù)下一邊 }//while if(!flag) return(0); //最后沒(méi)有通路 返回0 }//結(jié)束 [算法討論] 若頂點(diǎn)vi和vj 不是編號(hào)，必須先用頂點(diǎn)定位函數(shù),查出其在鄰接表頂點(diǎn)向量中的下標(biāo)i和j。下面算法2輸出vi 到 vj的路徑，其思想是用一個(gè)棧存放遍歷的頂點(diǎn)，遇到頂點(diǎn)vj時(shí)輸出路徑。 算法2：void dfs(AdjList g , int i,j) //有向圖g的頂點(diǎn)vi（編號(hào)i）和頂點(diǎn)vj（編號(hào)j）間是否有路徑，如有，則輸出。 { int top=0, stack[]; //stack是存放頂點(diǎn)編號(hào)的棧 visited=1; //visited 數(shù)組在進(jìn)入dfs前已初始化。 stack[++top]=i; p=g.firstarc; //求第一個(gè)鄰接弧結(jié)點(diǎn). while(p) { if(p->adjvex==j) //弧p的頂點(diǎn)即為j，遇到頂點(diǎn)vj 輸出路徑 { stack[++top]=j; //頂點(diǎn)j入棧 printf( "頂點(diǎn) vi 和 vj 的路徑為： "); for(i=1; i<=top; i++) printf( "%4d",stack); exit(0); }//if else if (visited[p->adjvex]==0) //弧p的頂點(diǎn)p->adjvex尚未被訪問(wèn) { dfs(g,p->adjvex,j); top--; p=p->next;} // 遞歸進(jìn)行深度遍歷 出棧 }//while }//結(jié)束算法2 算法3：本題用非遞歸算法求解。 int Connectij (AdjList g , vertype vi , vj ) //判斷n個(gè)頂點(diǎn)以鄰接表表示的有向圖g中，頂點(diǎn) Vi 各Vj 是否有路徑，有則返回1，否則返回0。 { for(i=1;i<=n;i++) visited=0; //訪問(wèn)標(biāo)記數(shù)組初始化。 i=GraphLocateVertex(g,vi); //頂點(diǎn)定位，不考慮 vi或 vj不在圖中的情況。 j=GraphLocateVertex(g,vj); int stack[],top=0;stack[++top]=i; while(top>0) { k=stack[top--]; p=g[k].firstarc; while(p!=null && visited[p->adjvex]==1) p=p->next; //查第k個(gè)鏈表中第一個(gè)未訪問(wèn)的弧結(jié)點(diǎn)。 if(p==null) top--; else { i=p->adjvex; if(i==j) return(1); //頂點(diǎn)vi和vj 間有路徑。 else {visited=1; stack[++top]=i;}//else }//else }while return(0); } //頂點(diǎn)vi和vj 間無(wú)通路。 13.有向圖判斷回路要比無(wú)向圖復(fù)雜。利用深度優(yōu)先遍歷，將頂點(diǎn)分成三類(lèi)：未訪問(wèn)；已訪問(wèn)但其鄰接點(diǎn)未訪問(wèn)完;已訪問(wèn)且其鄰接點(diǎn)已訪問(wèn)完。下面用0，1，2表示這三種狀態(tài)。前面已提到，若dfs（v）結(jié)束前出現(xiàn)頂點(diǎn)u到v的回邊，則圖中必有包含頂點(diǎn)v和u的回路。對(duì)應(yīng)程序中v的狀態(tài)為1，而u是正訪問(wèn)的頂點(diǎn)，若我們找出u的下一鄰接點(diǎn)的狀態(tài)為1，就可以輸出回路了。 ●void Print(int v,int start ) //輸出從頂點(diǎn)start開(kāi)始的回路。 { for(i=1;i<=n;i++) if(g[v]!=0 && visited==1 ) //若存在邊（v,i），且頂點(diǎn)i的狀態(tài)為1。 { printf(“%d”,v); if(i==start) printf(“ ”); else Print(i,start); //遞歸 break;} ●void dfs(int v) { visited[v]=1; //0:未訪問(wèn);1:已訪問(wèn)但其鄰接點(diǎn)未訪問(wèn)完; 2:已訪問(wèn)且其鄰接點(diǎn)已訪問(wèn)完 for(j=1;j<=n;j++ ) if (g[v][j]!=0) //存在邊(v,j) if (visited[j]!=1) //0:未訪問(wèn) 或 2:已訪問(wèn)且其鄰接點(diǎn)已訪問(wèn)完 { if(!visited[j]) dfs(j); } //0:未訪問(wèn)j未訪問(wèn) 深度遍歷j else {cycle=1; Print(j,j);} // 1:已訪問(wèn)且其鄰接點(diǎn)未訪問(wèn)完 visited[v]=2; //訪問(wèn)v完成 2:已訪問(wèn)且其鄰接點(diǎn)已訪問(wèn)完 }//dfs ●void find_cycle() //判斷是否有回路，有則輸出鄰接矩陣。visited數(shù)組為全局變量。 { for(i=1;i<=n;i++) visited=0; for(i=1;i<=n;i++ ) if(!visited) dfs(i); }//find_cycle 16.本題應(yīng)使用深度優(yōu)先遍歷，從主調(diào)函數(shù)進(jìn)入dfs(v)時(shí) ，開(kāi)始記數(shù)，若退出dfs()前，已訪問(wèn)完有向圖的全部頂點(diǎn)（設(shè)為n個(gè)），則有向圖有根，v為根結(jié)點(diǎn)。將n個(gè)頂點(diǎn)從1到n編號(hào)，各調(diào)用一次dfs()過(guò)程，就可以求出全部的根結(jié)點(diǎn)。題中有向圖的鄰接表存儲(chǔ)結(jié)構(gòu)、記頂點(diǎn)個(gè)數(shù)的變量、以及訪問(wèn)標(biāo)記數(shù)組等均設(shè)計(jì)為全局變量。建立有向圖g的鄰接表存儲(chǔ)結(jié)構(gòu)參見(jiàn)上面第2題，這里只給出判斷有向圖是否有根的算法。 int num=0， visited[]=0 //num記訪問(wèn)頂點(diǎn)個(gè)數(shù),訪問(wèn)數(shù)組visited初始化。 const n=用戶定義的頂點(diǎn)數(shù); AdjList g ; //用鄰接表作存儲(chǔ)結(jié)構(gòu)的有向圖g。 void dfs(v) { visited[v]=1; num++; //訪問(wèn)的頂點(diǎn)數(shù)＋1 if(num==n) { printf(“%d是有向圖的根。 ”,v); num=0;} //重新計(jì)數(shù) p=g[v].firstarc; //第一邊結(jié)點(diǎn) while (p) { if(visied[p->adjvex]==0) dfs(p->adjvex); //未訪問(wèn) 遞歸深度遍歷 p=p->next;} //while visited[v]=0; num--; //恢復(fù)頂點(diǎn)v 全局變量重新計(jì)數(shù) 便于后邊遍歷 }//dfs void JudgeRoot() //判斷有向圖是否有根，有根則輸出之。 { static int i ; for(i=1;i<=n;i++ ) //從每個(gè)頂點(diǎn)出發(fā)，調(diào)用dfs()各一次。 { num=0; visited[1..n]=0; dfs(i); } }// JudgeRoot 算法中打印根時(shí)，輸出頂點(diǎn)在鄰接表中的序號(hào)（下標(biāo)），若要輸出頂點(diǎn)信息，可使用g.vertex。 17.圖的遍歷可以求出圖的連通分量。進(jìn)入dfs或bfs一次，就可以訪問(wèn)到圖的一個(gè)連通分量的所有頂點(diǎn)。 void dfs () { visited[v]=1; printf (“%3d”,v); //輸出連通分量的頂點(diǎn)。 p=g[v].firstarc; while(p!=null) { if（visited[p->adjvex]==0） dfs(p->adjvex); //深度遞歸訪問(wèn) p=p->next; }//while }// dfs void Count() //深度優(yōu)先遍歷求圖中連通分量的個(gè)數(shù) { int k=0 ; static AdjList g ; //設(shè)無(wú)向圖g有n個(gè)結(jié)點(diǎn) for(i=1;i<=n;i++ ) if(visited==0) { printf (" 第%d個(gè)連通分量: ",++k); dfs(i);} }//Count 算法中visited[]數(shù)組是全程變量，每個(gè)連通分量的頂點(diǎn)集按遍歷順序輸出。這里設(shè)頂點(diǎn)信息就是頂點(diǎn)編號(hào)，否則應(yīng)取其g.vertex分量輸出。 18.void bfs(AdjList GL，vertype v ) //從v發(fā)非遞歸廣度優(yōu)先遍歷以鄰接表為存儲(chǔ)結(jié)構(gòu)的無(wú)向圖GL。 { visited[v]=1; printf( "%3d",v); //輸出第一個(gè)遍歷的頂點(diǎn)。 QueueInit(Q); QueueIn(Q ,v); //先置空隊(duì)列，然后第一個(gè)頂點(diǎn)v入隊(duì)列，設(shè)隊(duì)列容量足夠大 while(!QueueEmpty(Q)) { v=QueueOut(Q); // v出隊(duì)列。 p=GL[v].firstarc; // GL是全局變量，第一個(gè)鄰接邊結(jié)點(diǎn) while(p!=null) { if(visited[p->adjvex]==0) //第一個(gè)鄰接點(diǎn)未訪問(wèn) { printf("%3d",p->adjvex); visited[p->adjvex]=1; QueueIn(Q,p->adjvex);}//if //訪問(wèn)入隊(duì) p=p->next; //下一個(gè)鄰接邊結(jié)點(diǎn) 即廣度優(yōu)先 }//while }// while (!QueueEmpty(Q)) }//bfs void BFSCOM() //廣度優(yōu)先搜索，求無(wú)向圖Ｇ的連通分量。 { int count=0; //記連通分量個(gè)數(shù)。 for (i=1;i<=n;i++) visited=0; for (i=1;i<=n;i++) if (visited==0) {printf(" 第%d個(gè)連通分量: ",++count); bfs(i);}//if }//BFSCOM 27.D_搜索類(lèi)似BFS，只是用棧代替隊(duì)列，入出隊(duì)列改為入出棧。查某頂點(diǎn)的鄰接點(diǎn)時(shí)，若其鄰接點(diǎn)尚未遍歷，則遍歷之，并將其壓入棧中。當(dāng)一個(gè)頂點(diǎn)的所有鄰接點(diǎn)被搜索后，棧頂頂點(diǎn)是下一個(gè)搜索出發(fā)點(diǎn)。 void D_BFS(AdjList g ,vertype v0) // 從v0頂點(diǎn)開(kāi)始，對(duì)以鄰接表為存儲(chǔ)結(jié)構(gòu)的圖g進(jìn)行D_搜索。 { int s[], top=0; //棧，棧中元素為頂點(diǎn)，仍假定頂點(diǎn)用編號(hào)表示。 for(i=1,i<=n;i++) visited=0; //圖有n個(gè)頂點(diǎn)，visited數(shù)組為全局變量 初始化 for(i=1,i<=n;i++) //對(duì)n個(gè)頂點(diǎn)的圖g進(jìn)行D_搜索 if(visited==0) //未訪問(wèn) { s[++top]=i; visited=1; printf( "%3d",i); //入棧；訪問(wèn) while(top>0) { i=s[top--]; //退棧，準(zhǔn)備找鄰接點(diǎn) p=g.firstarc; //取第一個(gè)鄰接邊結(jié)點(diǎn) while(p!=null) //處理頂點(diǎn)的所有鄰接邊結(jié)點(diǎn) { j=p->adjvex; //鄰接點(diǎn) if(visited[j]==0) //未訪問(wèn)的鄰接點(diǎn) { visited[j]=1; printf( "%3d",i); s[++top]=j;} //訪問(wèn)并入棧 p=p->next; //廣度優(yōu)先遍歷 } //下一個(gè)鄰接點(diǎn) }//while(top>0) } //if }//D_BFS 20. void Traver(AdjList g,vertype v) //圖g以鄰接表為存儲(chǔ)結(jié)構(gòu)，算法從頂點(diǎn)v開(kāi)始實(shí)現(xiàn)非遞歸深度優(yōu)先遍歷。 { struct arc *stack[]; visited[v]=1；printf(v); //輸出頂點(diǎn)v top=0; p=g[v].firstarc; stack[++top]=p; ★★while(top>0 || p!=null) {★while(p) if( p && visited[p->adjvex]) p=p->next; //已訪問(wèn) 找下一個(gè) else{ printf(p->adjvex); visited[p->adjvex]=1; //訪問(wèn) stack[++top]=p; p=g[p->adjvex].firstarc; //入棧 深度遍歷 }//else ★if (top>0) { p=stack[top--]; p=p->next; } }//while }//算法結(jié)束。 [算法討論] 以上算法適合連通圖，若是非連通圖，則再增加一個(gè)主調(diào)算法,其核心語(yǔ)句是 for (vi=1;vi<=n;vi++) if (!visited[vi]) Traver(g,vi); 21. void dfs(v) { i=GraphLocateVertex(g ,v); //定位頂點(diǎn) visited=1; printf(v); //輸出頂點(diǎn)信息 p=g.firstarc; while(p) { if(visited[p->adjvex]==0) dfs(g[p->adjvex].vertex); p=p->next; }//while }//dfs void traver( ) //深度優(yōu)先搜索的遞歸程序；以鄰接表表示的圖g是全局變量。 { for (i=1;i<=n;i++) visited=0; //訪問(wèn)數(shù)組是全局變量初始化。 for (vi=v1;vi<=vn;vi++) if (visited[GraphLocateVertex(g，vi)]==0) dfs(vi); }//算法結(jié)束。 23.對(duì)無(wú)向圖Ｇ的深度優(yōu)先遍歷，將連通分量的頂點(diǎn)用括號(hào)括起來(lái)的算法。 void Traver( ) {for (i=1;i<=nodes(g);i++) visited=0; //visited是全局變量，初始化。 for (i=1;i<=nodes(g);i++) if (visied==0) { printf ("("); dfs(i); printf (")"); } }//Traver 24.void visit(vertype v) //訪問(wèn)圖的頂點(diǎn)v。 int nodes(graph g) //圖的頂點(diǎn)數(shù) void initqueue (vertype Q[]) //圖的頂點(diǎn)隊(duì)列Ｑ初始化。 void enqueue (vertype Q[] ,v) //頂點(diǎn)v入隊(duì)列Ｑ。 vertype delqueue (vertype Q[]) //出隊(duì)操作。 int empty (Q) //判斷隊(duì)列是否為空的函數(shù)，若空返回１，否則返回０。 vertype firstadj(graph g ,vertype v)//圖g中v的第一個(gè)鄰接點(diǎn)。 vertype nextadj(graph g ,vertype v ,vertype w)//圖g中頂點(diǎn)v的鄰接點(diǎn)中在w后的鄰接點(diǎn) void bfs (graph g ,vertype v0) //利用上面定義的圖的抽象數(shù)據(jù)類(lèi)型，從頂點(diǎn)v0出發(fā) 廣度優(yōu)先遍歷圖g。 { visit(v0); visited[v0]=1; //設(shè)頂點(diǎn)信息就是編號(hào)，visited是全局變量。 initqueue(Q); enqueue(Q,v0); //v0入隊(duì)列。 while(!empty(Q)) { v=delqueue(Q); //隊(duì)頭元素出隊(duì)列。 w=firstadj(g ,v); //求頂點(diǎn)v的第一鄰接點(diǎn) while(w!=0) //w!=0表示w存在。 { if(visited[w]==0) //若鄰接點(diǎn)未訪問(wèn)。 { visit(w); visited[w]=1; enqueue(Q,w); }//if w=nextadj(g,v,w); //求下一個(gè)鄰接點(diǎn)。 }//while }//while }//bfs void Traver(graph g) //對(duì)圖g進(jìn)行寬度優(yōu)先遍歷，圖g是全局變量。 { int n= nodes(g); for(i=1;i<=n;i++) visited=0; for(i=1;i<=n;i++) if (visited==0) bfs(i); } //Traver 25.使用深度優(yōu)先遍歷。設(shè)圖的頂點(diǎn)信息就是頂點(diǎn)編號(hào)，用num記錄訪問(wèn)頂點(diǎn)個(gè)數(shù)，當(dāng)num等于圖的頂點(diǎn)個(gè)數(shù)（題中的NODES(G)），輸出所訪問(wèn)的頂點(diǎn)序列，頂點(diǎn)序列存在path中，path和visited數(shù)組，頂點(diǎn)計(jì)數(shù)器num，均是全局變量，都已初始化。 void SPathdfs(v0) //判斷無(wú)向圖Ｇ中是否存在以v0為起點(diǎn)，包含圖中全部頂點(diǎn)的簡(jiǎn)單路徑。遞歸 { visited[v0]=1; path[++num]=v0; //訪問(wèn)起點(diǎn)v0，加入路徑 if(num==nodes(G) //有一條簡(jiǎn)單路徑，輸出之。 { for(i=1;i<=num;i++) printf( "%3d",path); printf( " "); exit(0);} //if p=g[v0].firstarc; //取第一個(gè)鄰接邊結(jié)點(diǎn) while (p) { if(visited[p->adjvex]==0) SPathdfs(p->adjvex); //未訪問(wèn)，遞歸深度優(yōu)先遍歷。 p=p->next; //下一個(gè)鄰接點(diǎn)。 }//while visited[v0]=0; num--; //取消訪問(wèn)標(biāo)記，使該頂點(diǎn)可重新使用。 }//SPathdfs 26.非遞歸算法，頂點(diǎn)信息仍是編號(hào)。 void AllSPdfs(AdjList g,vertype u,vertype v) //求有向圖g中頂點(diǎn)u到頂點(diǎn)v的所有簡(jiǎn)單路徑，初始調(diào)用形式：AllSPdfs(g,u,v) 非遞歸 { int top=0,s[]; s[++top]=u; visited=1; //起點(diǎn)加入路徑，訪問(wèn) while(top>0 || p) { p=g[s[top]].firstarc; //第一個(gè)鄰接點(diǎn)。 while(p!=null && visited[p->adjvex]==1) p=p->next; //下一個(gè)訪問(wèn)鄰接弧結(jié)點(diǎn)。 if(p==null) top--; //退棧。 else{ i=p->adjvex; //取鄰接點(diǎn)（編號(hào)）。 if(i==v) //找到從u到v的一條簡(jiǎn)單路徑，輸出。 { for(k=1;k<=top;k++) printf( "%3d",s[k]); printf( "%3d ",v);} else{ visited=1; s[++top]=i; } //未找到 else深度優(yōu)先遍歷。 }//else }//while }// AllSPdfs 28.對(duì)有向無(wú)環(huán)圖(DAG)的頂點(diǎn)，以整數(shù)適當(dāng)編號(hào)后，可使其鄰接矩陣中對(duì)角線以下元素全部為零。根據(jù)這一要求，可以按各頂點(diǎn)出度大小排序，使出度最大的頂點(diǎn)編號(hào)為1，出度次大者編號(hào)為2，出度為零的頂點(diǎn)編號(hào)為n。這樣編號(hào)后，可能出現(xiàn)頂點(diǎn)編號(hào)i<j，但卻有一條從頂點(diǎn)到j(luò)到i的弧。這時(shí)應(yīng)進(jìn)行調(diào)整，即檢查每一條弧，若有<i,j>，且i>j，則使頂點(diǎn)j的編號(hào)在頂點(diǎn)i的編號(hào)之前。 void Adjust(AdjMatrix g1 ,AdjMatrix g2) //對(duì)以鄰接矩陣存儲(chǔ)的DAG圖g1重新編號(hào)，使若有<i,j>，則編號(hào)i<j，重新編號(hào)后圖以鄰接矩陣g2存儲(chǔ)。 { typedef struct { int vertex ,out ,count }node ; //結(jié)點(diǎn)結(jié)構(gòu)：頂點(diǎn)，出度，計(jì)數(shù)。 node v[]; //頂點(diǎn)元素?cái)?shù)組。 int c[]; //中間變量 ①for(i=1;i<=n;i++) //頂點(diǎn)信息數(shù)組初始化，設(shè)圖有n個(gè)頂點(diǎn)。 { v.vertex=i; v.out=0; v.count=1; c=1; } //count=1為最小 ②for(i=1;i<=n;i++) //計(jì)算每個(gè)頂點(diǎn)的出度。 for (j=1;j<=n;j++) v.out+=g1[j]; ③for(i=n;i>=2;i--) //對(duì)v的出度域進(jìn)行計(jì)數(shù)排序，出度大者，count域中值小。 for(j=i-1;j>=1;j--) if(v.count<=v[j].count) v.count++; else v[j].count++; ④for(i=1;i<=n;i++) //第二次調(diào)整編號(hào)。若<i,j>且i>j，則頂點(diǎn)j的編號(hào)在頂點(diǎn)i的編號(hào)之前 for(j=i;j<=n;j++) if(g1[j]==1 && v.count>v[j].count) { v.count=v[j].count; v[j].count++; } ⑤for(i=n;i>=2;i--)) //對(duì)v的計(jì)數(shù)域v.count排序，按count域從小到大順序存到數(shù)組c中。 for(j=i-1;j>=1;j--) if(v.count<v[j].count) c[j]++; else c++; ⑥for(i=1;i<=n;i++) v.count=c; //將最終編號(hào)存入count 域中。 ⑦for(i=1;i<=n;i++) //賦值 for(j=1;j<=n;j++) g2[v.count][v[j].count]=g1[v.vertex][v[j].vertex]; }//算法結(jié)束 29.將頂點(diǎn)放在兩個(gè)集合V1和V2。對(duì)每個(gè)頂點(diǎn)，檢查其和鄰接點(diǎn)是否在同一個(gè)集合中，如是，則為非二部圖。為此，用整數(shù)1和2表示兩個(gè)集合。再用一隊(duì)列結(jié)構(gòu)存放圖中訪問(wèn)的頂點(diǎn)。 int BPGraph (AdjMatrix g) //判斷以鄰接矩陣表示的圖g是否是二部圖。 { int s[]; //頂點(diǎn)向量，元素值表示其屬于那個(gè)集合（值1和2表示兩個(gè)集合） int Q[];//Q為隊(duì)列，元素為圖的頂點(diǎn)，這里設(shè)頂點(diǎn)信息就是頂點(diǎn)編號(hào)。 int f=0,r,visited[]; //f和r分別是隊(duì)列的頭尾指針,visited[]是訪問(wèn)數(shù)組 for (i=1;i<=n;i++) { visited=0; s=0; } //初始化，各頂點(diǎn)未確定屬于那個(gè)集合 Q[1]=1; r=1; s[1]=1; //頂點(diǎn)1放入集合S1 while(f<r) { v=Q[++f]; if (s[v]==1) jh=2; else jh=1; //準(zhǔn)備v的鄰接點(diǎn)的集合號(hào) if(!visited[v]) //未訪問(wèn)v則訪問(wèn)之 {visited[v]=1; //確保對(duì)每一個(gè)頂點(diǎn)，都要檢查與其鄰接點(diǎn)不應(yīng)在一個(gè)集合中 for(j=1,j<=n;j++) //對(duì)v的每一邊<i,j>檢查鄰接點(diǎn)j if(g[v][j]==1) //連通 有邊 { if(!s[j]) { s[j]=jh; Q[++r]=j; } //二部圖 鄰接點(diǎn)入隊(duì)列 else if(s[j]==s[v]) return(0); } //非二部圖 }//if (!visited[v]) }//while return(1); }//是二部圖 [算法討論] 題目給的是連通無(wú)向圖，若非連通，則算法要修改。 30.連通圖的生成樹(shù)包括圖中的全部n個(gè)頂點(diǎn)和足以使圖連通的n-1條邊，最小生成樹(shù)是邊上權(quán)值之和最小的生成樹(shù)。故可按權(quán)值從大到小對(duì)邊進(jìn)行排序，然后從大到小將邊刪除。每刪除一條當(dāng)前權(quán)值最大的邊后，就去測(cè)試圖是否仍連通，若不再連通，則將該邊恢復(fù)。若仍連通，繼續(xù)向下刪；直到剩n-1條邊為止。 void SpnTree (AdjList g) //用“破圈法”求解帶權(quán)連通無(wú)向圖的一棵最小代價(jià)生成樹(shù)。 { typedef struct { int i,j,w }node; //設(shè)頂點(diǎn)信息就是頂點(diǎn)編號(hào)，權(quán)是整型數(shù) node edge[]; scanf( "%d%d",&e,&n) ; //輸入邊數(shù)和頂點(diǎn)數(shù)。 for(i=1;i<=e;i++) //輸入e條邊：頂點(diǎn)，權(quán)值。 scanf("%d%d%d" ,&edge.i ,&edge.j ,&edge.w); for(i=2;i<=e;i++) //按邊上的權(quán)值大小，對(duì)邊進(jìn)行逆序排序。 { edge[0]=edge; j=i-1; while(edge[j].w<edge[0].w) edge[j+1]=edge[j--]; edge[j+1]=edge[0]; }//for k=1; eg=e; while(eg>=n) //破圈，直到邊數(shù)e=n-1. { if(connect(k)) //刪除第k條邊若仍連通。 { edge[k].w=0; eg--; }//測(cè)試下一條邊edge[k]，權(quán)值置0表示該邊被刪除 k++; //下條邊 }//while }//算法結(jié)束。 connect()是測(cè)試圖是否連通的函數(shù)，可用圖的遍歷實(shí)現(xiàn)，若是連通圖，一次進(jìn)入dfs或bfs就可遍歷完全部結(jié)點(diǎn)，否則，因?yàn)閯h除該邊而使原連通圖成為兩個(gè)連通分量時(shí)，該邊不應(yīng)刪除。前面第17,18就是測(cè)連通分量個(gè)數(shù)的算法。 31.求單源點(diǎn)最短路徑問(wèn)題，存儲(chǔ)結(jié)構(gòu)用鄰接表表示，這里先給出所用的鄰接表中的邊結(jié)點(diǎn)的定義： struct node { int adjvex,weight; struct node *next; }p; void Shortest_Dijkstra(AdjList cost ,vertype v0) //在帶權(quán)鄰接表cost中，用Dijkstra方法求從頂點(diǎn)v0到其它頂點(diǎn)的最短路徑。 { int dist[],s[]; //dist數(shù)組存放最短路徑，s數(shù)組存頂點(diǎn)是否找到最短路徑的信息。 for(i=1;i<=n;i++) {dist=INFINITY; s=0; } //初始化，INFINITY是機(jī)器中最大的數(shù) s[v0]=1; p=g[v0].firstarc; while(p) //頂點(diǎn)的最短路徑賦初值 { dist[p->adjvex]=p->weight; p=p->next;} for(i=1;i<n;i++) //在尚未確定最短路徑的頂點(diǎn)集中選有最短路徑的頂點(diǎn)u { mindis=INFINITY; //INFINITY是機(jī)器中最大的數(shù)，代表無(wú)窮大 ●for(j=1;j<=n;j++) if(s[j]==0 && dist[j]<mindis) { u=j; mindis=dist[j]; } ●s=1; //頂點(diǎn)u已找到最短路徑。 p=g.firstarc; ●while(p) //修改從v0到其它頂點(diǎn)的最短路徑 { j=p->adjvex; if(s[j]==0 && dist[j]>dist+p->weight) dist[j]=dist+p->weight; p=p->next; } }// for (i=1;i<n;i++) 這里只是執(zhí)行n-1次 循環(huán)內(nèi)容與i無(wú)關(guān) }//Shortest_Dijkstra 39.按Dijkstra路徑增序求出源點(diǎn)和各頂點(diǎn)間的最短路徑，上面已有。求出最小生成樹(shù)，即以源點(diǎn)為根，其路徑權(quán)值之和最小的生成樹(shù)。在確定頂點(diǎn)的最短路徑時(shí)，總是知道其（弧出自的）前驅(qū)（雙親）頂點(diǎn)，可用向量p[1..n]記錄各頂點(diǎn)的雙親信息，源點(diǎn)為根，無(wú)雙親，向量中元素值用-1表示。 void Shortest_PTree ( AdjMatrix G, vertype v0) //利用從源點(diǎn)v0到其余各點(diǎn)的最短路徑的思想，產(chǎn)生以鄰接矩陣表示的圖G的最小生成樹(shù) { int d[] ,s[] ; //d數(shù)組存放各頂點(diǎn)最短路徑，s數(shù)組存放頂點(diǎn)是否找到最短路徑。 int p[] ; //p數(shù)組存放頂點(diǎn)在生成樹(shù)中雙親結(jié)點(diǎn)的信息。 for(i=1;i<=n;i++) //初始化 { d=G[v0]; s=0; if(d<MAXINT) p=v0; //MAXINT是機(jī)器最大數(shù)，v0是i的前驅(qū)（雙親）。 else p=-1; }//for //i目前無(wú)前驅(qū)，p數(shù)組各量初始化為-1。 s[v0]=1; d[v0]=0; p[v0]=-1; //從v0開(kāi)始，求其最小生成樹(shù)。 ★for(i=1;i<n;i++) { mindis=MAXINT; ●for(j=1;j<=n;j++) if(s[j]==0 && d[j]<mindis) //尚未找到最短 有通路 { u=j; mindis=d[j];} //for循環(huán)查找 直到最小 ●s=1; //頂點(diǎn)u已找到最短路徑。 ●for(j=1;j<=n;j++) //修改j的最短路徑及雙親。 if (s[j]==0 && d[j]>d+G[j]) {d[j]=d+G[j]; p[j]=u;} }//for (i=1;i<=n;i++) ★for(i=1;i<=n;i++) //輸出最短路徑及其長(zhǎng)度，路徑是逆序輸出。 if(i!=v0) { pre=p; printf( " 最短路徑長(zhǎng)度＝%d，路徑是：%d，",d,i); while(pre!=-1) { printf( ",%d",pre); pre=p[pre]; } //一直回溯到根結(jié)點(diǎn)。 }//if }//算法結(jié)束 32. FLOYD算法直接求解如下： void ShortPath_FLOYD(AdjMatrix g) //求具有n個(gè)頂點(diǎn)的有向圖每對(duì)頂點(diǎn)間的最短路徑 { AdjMatrix length; //length[j]存放頂點(diǎn)vi到vj的最短路徑長(zhǎng)度。 for (i=1;i<=n;i++) for (j=1;j<=n;j++) length[j]=g[j]; //初始化。 for (k=1;k<=n;k++) for (i=1;i<=n;i++) for (j=1;j<=n;j++) if (length[k]+length[k][j]<length[j]) length[j]=length[k]+length[k][j]; }//算法結(jié)束 35.用寬度優(yōu)先遍歷求解。若以v0作生成樹(shù)的根為第1層，則距頂點(diǎn)v0最短路徑長(zhǎng)度為K的頂點(diǎn)均在第K+1層�？捎藐�(duì)列存放頂點(diǎn)，將遍歷訪問(wèn)頂點(diǎn)的操作改為入隊(duì)操作。隊(duì)列中設(shè)頭尾指針f和r，用level表示層數(shù)。 void bfs_K ( graph g ,int v0 ,K) //輸出無(wú)向連通圖g（未指定存儲(chǔ)結(jié)構(gòu)）中距頂點(diǎn)v0最短路徑長(zhǎng)度為K的頂點(diǎn)。 { int Q[]; //Q為頂點(diǎn)隊(duì)列，容量足夠大。 int f=0,r=0,t=0; //f和r分別為隊(duì)頭和隊(duì)尾指針，t指向當(dāng)前層最后頂點(diǎn)。 int level=0,flag=0; //層數(shù)和訪問(wèn)成功標(biāo)記。 visited[v0]=1; //設(shè)v0為根。 Q[++r]=v0; t=r; level=1; //v0入隊(duì)。 ★★while(f<r && level<=K+1) { v=Q[++f]; //出隊(duì)頭 w=GraphFirstAdj(g,v); ★while(w!=0) //w!=0 表示鄰接點(diǎn)存在 { if (visited[w]==0) //未訪問(wèn) { Q[++r]=w; visited[w]=1; //鄰接點(diǎn)入隊(duì)列尾 訪問(wèn) if(level==K+1) { printf("距頂點(diǎn)v0最短路徑為k的頂點(diǎn)%d ",w); flag=1; } //成功訪問(wèn) }//if w=GraphNextAdj(g ,v ,w); //廣度遍歷 }//while(w!=0) ★if(f==t) { level++；t=r; } //當(dāng)前層處理完，修改層數(shù)，t指向下一層最后一個(gè)頂點(diǎn) }//while(f<r && level<=K+1) ★★if(flag==0) printf( "圖中無(wú)距v0頂點(diǎn)最短路徑為%d的頂點(diǎn)。 ",K); }//算法結(jié)束。 [設(shè)法討論]亦可采取另一個(gè)算法。由于在生成樹(shù)中結(jié)點(diǎn)的層數(shù)等于其雙親層次數(shù)加1，故可設(shè)頂點(diǎn)和層次數(shù)2個(gè)隊(duì)列，其入隊(duì)和出隊(duì)操作同步，其核心語(yǔ)句段如下： QueueInit(Q1) ; QueueInit(Q2); //Q1和Q2是頂點(diǎn)和頂點(diǎn)所在層次數(shù)的隊(duì)列。 visited[v0]=1; //訪問(wèn)數(shù)組初始化，置v0被訪問(wèn)標(biāo)記。 level=1; flag=0; //是否有層次為K的頂點(diǎn)的標(biāo)志 QueueIn(Q1,v0); QueueIn(Q2,level); //頂點(diǎn)和層數(shù)入隊(duì)列。 ★while(!empty(Q1) && level<=K+1) { v=QueueOut(Q1); level=QueueOut(Q2);//頂點(diǎn)和層數(shù)出隊(duì)。 w=GraphFirstAdj(g,v0); ▲while(w!=0) //鄰接點(diǎn)存在。 { if(visited[w]==0) if(level==K+1) { printf("距離頂點(diǎn)v0最短路徑長(zhǎng)度為K的頂點(diǎn)是%d ",w); visited[w]=1; flag=1; QueueIn(Q1 ,w); QueueIn(Q2,level+1); }//if w=GraphNextAdj(g ,v ,w); }//while(w!=0) }//while(!empty(Q1) && level<K+1) ★if (flag==0) printf( "圖中無(wú)距v0頂點(diǎn)最短路徑為%d的頂點(diǎn)。 ",K); 37.利用FLOYD算法求出每對(duì)頂點(diǎn)間的最短路徑矩陣w，然后對(duì)矩陣w，求出每列j的最大值，得到頂點(diǎn)j的偏心度。然后在所有偏心度中，取最小偏心度的頂點(diǎn)v就是有向圖的中心點(diǎn)。 void FLOYD_PXD(AdjMatrix g) //對(duì)以帶權(quán)鄰接矩陣表示的有向圖g，求其中心點(diǎn)。 { AdjMatrix w=g ; //將帶權(quán)鄰接矩陣復(fù)制到w。 for(k=1;k<=n;k++) //求每對(duì)頂點(diǎn)間的最短路徑。 for(i=1;i<=n;i++) for(j=1;j<=n;j++) if( w[j]>w[k]+w[k][j]) w[j]=w[k]+w[k][j]; v=1; dist=MAXINT; //中心點(diǎn)初值頂點(diǎn)v為1，偏心度初值為機(jī)器最大數(shù)。 for(j=1;j<=n;j++) { s=0; for(i=1;i<=n;i++) if(w[j]>s) s=w[j]; //求每列中的最大值為該頂點(diǎn)的偏心度 if(s<dist) { dist=s; v=j; }//各偏心度中最小值為中心點(diǎn) }//for printf( "有向圖g的中心點(diǎn)是頂點(diǎn)%d,偏心度%d ",v,dist); }//算法結(jié)束 41.對(duì)有向圖進(jìn)行深度優(yōu)先遍歷可以判定圖中是否有回路。若從有向圖某個(gè)頂點(diǎn)v出發(fā)遍歷，在dfs(v)結(jié)束之前，出現(xiàn)從頂點(diǎn)u到頂點(diǎn)v的回邊，圖中必存在環(huán)。這里設(shè)定visited訪問(wèn)數(shù)組和finished數(shù)組為全局變量，若finished=1,表示頂點(diǎn)i的鄰接點(diǎn)已搜索完畢。由于dfs產(chǎn)生的是逆拓?fù)渑判�，故設(shè)一類(lèi)型是指向鄰接表的邊結(jié)點(diǎn)的全局指針變量final，在dfs函數(shù)退出時(shí)，把頂點(diǎn)v插入到final所指的鏈表中，鏈表中的結(jié)點(diǎn)就是一個(gè)正常的拓?fù)湫蛄小? int visited[]=0; finished[]=0; flag=1; //flag測(cè)試拓?fù)渑判蚴欠癯晒?br /> ArcNode *final=null; //final是指向頂點(diǎn)鏈表的指針，初始化為0 void dfs(AdjList g,vertype v) //以頂點(diǎn)v開(kāi)始深度優(yōu)先遍歷有向圖g，假定頂點(diǎn)信息就是頂點(diǎn)編號(hào). { ArcNode *t; //指向邊結(jié)點(diǎn)的臨時(shí)變量 printf("%d",v); visited[v]=1; p=g[v].firstarc; while(p!=null) { j=p->adjvex; if(visited[j]==1 && finished[j]==0) //已訪問(wèn) 未搜索完 flag=0 //dfs結(jié)束前出現(xiàn)回邊 else if(visited[j]==0) //未訪問(wèn) { dfs(g,j); finished[j]=1; } //遞歸訪問(wèn) j的遞歸退出后 對(duì)j搜索完成 p=p->next; }//while t=(ArcNode *)malloc(sizeof(ArcNode));//申請(qǐng)邊結(jié)點(diǎn) t->adjvex=v; t->next=final; final=t; //將該頂點(diǎn)插入鏈表 } //dfs結(jié)束 int dfs-Topsort(Adjlist g) //對(duì)以鄰接表為存儲(chǔ)結(jié)構(gòu)的有向圖進(jìn)行拓?fù)渑判�，拓�(fù)渑判虺晒Ψ祷?，否則返回0 { i=1; while(flag && i<=n) if(visited==0) { dfs(g,i); finished=1; } //if return(flag); }// dfs-Topsort 42.地圖涂色問(wèn)題可以用“四染色“定理。將地圖上的國(guó)家編號(hào)（1到n），從編號(hào)1開(kāi)始逐一涂色，對(duì)每個(gè)區(qū)域用1色，2色，3色，4色（下稱“色數(shù)”）依次試探，若當(dāng)前所取顏色與周?chē)淹可珔^(qū)域不重色，則將該區(qū)域顏色進(jìn)棧；否則，用下一顏色。若1至4色均與相鄰某區(qū)域重色，則需退棧回溯,修改棧頂區(qū)域的顏色。用鄰接矩陣數(shù)據(jù)結(jié)構(gòu)C[n][n]描敘地圖上國(guó)家間的關(guān)系。n個(gè)國(guó)家用n階方陣表示，若第i個(gè)國(guó)家與第j個(gè)國(guó)家相鄰，則Cij=1，否則Cij=0。用棧s記錄染色結(jié)果，棧的下標(biāo)值為區(qū)域號(hào)，元素值是色數(shù)。 void MapColor(AdjMatrix C) //以鄰接矩陣C表示的n個(gè)國(guó)家的地區(qū)涂色 { int s[]; //棧的下標(biāo)是國(guó)家編號(hào)，內(nèi)容是色數(shù) s[1]=1； //編號(hào)01的國(guó)家涂1色 i=2;j=1; //i為國(guó)家號(hào)，j為涂色號(hào) ★while(i<=n) {▼while(j<=4 && i<=n) //4色定理 { k=1; //k指已涂色區(qū)域號(hào) ●while(k<i && s[k]*C[k]!=j) k++; //判相鄰區(qū)是否已涂色 ●if(k<i) j=j+1; //用j+1色繼續(xù)試探 else { s=j; i++; j=1;}//與相鄰區(qū)不重色，涂色結(jié)果進(jìn)棧，繼續(xù)對(duì)下一區(qū)涂色試探 進(jìn)棧;j重新開(kāi)始試探 }//while (j<=4 && i<=n) ▲if(j>4) { i--; j=s+1;} //退棧 變更棧頂區(qū)域的顏色。 }//while }//結(jié)束MapColor 36. 對(duì)于無(wú)環(huán)連通圖，頂點(diǎn)間均有路徑，樹(shù)的直徑是生成樹(shù)上距根結(jié)點(diǎn)最遠(yuǎn)的兩個(gè)葉子間的距離，利用深度優(yōu)先遍歷可求出圖的直徑。 int dfs(Graph g ,vertype parent ,vertype child ,int len) //深度優(yōu)先遍歷，返回從根到結(jié)點(diǎn)child所在的子樹(shù)的葉結(jié)點(diǎn)的最大距離。 {current_len=len; maxlen=len; v=GraphFirstAdj(g ,child); while (v!=0) //鄰接點(diǎn)存在。 if (v!=parent) {len=len+length(g ,child ,c); dfs(g ,child ,v ,len); if (len>maxlen) maxlen=len; v=GraphNextAdj(g ,child ,v); len=current_len; } //if len=maxlen; return(len); }//結(jié)束dfs。 int Find_Diamenter (Graph g) //求無(wú)向連通圖的直徑，圖的頂點(diǎn)信息為圖的編號(hào)。 {maxlen1=0; maxlen2=0; //存放目前找到的根到葉結(jié)點(diǎn)路徑的最大值和次大值。 len=0; ///深度優(yōu)先生成樹(shù)根到某葉結(jié)點(diǎn)間的距離 w=GraphFirstAdj(g,1); //頂點(diǎn)１為生成樹(shù)的根。 while (w!=0) //鄰接點(diǎn)存在。 {len=length(g ,1 ,w); if (len>maxlen1) {maxlen2=maxlen1; maxlen1=len;} else if (len>maxlen2) maxlen2=len; w=GraphNextAdj(g ,1 ,w);//找頂點(diǎn)1的下一鄰接點(diǎn)。 }//while printf( "無(wú)向連通圖g的最大直徑是%d " ,maxlen1+maxlen2); return(maxlen1+maxlen2); }//結(jié)束find_diamenter 算法主要過(guò)程是對(duì)圖進(jìn)行深度優(yōu)先遍歷。若以鄰接表為存儲(chǔ)結(jié)構(gòu)，則時(shí)間復(fù)雜度為O(n+e)。 FUNC find_diameter( g: Graph):integer; {利用深度優(yōu)先遍歷方法求出根結(jié)點(diǎn)到每一個(gè)葉結(jié)點(diǎn)的距離，maxlen1存放的是目前找到根到葉結(jié)點(diǎn)的最大值，maxlen2存放的是目前找到根到葉結(jié)點(diǎn)的次大值，len記錄深度優(yōu)先遍歷中到某一葉結(jié)點(diǎn)的距離，設(shè)圖g的頂點(diǎn)編號(hào)為1到vtxnum，以頂點(diǎn)1為根生成深度優(yōu)先樹(shù)} maxlen1:=0; maxlen2:=0; len:=0; w:=firstadj(g，1) {w為頂點(diǎn)1的鄰接點(diǎn)} WHILE w!=0 DO BEGIN {當(dāng)鄰接點(diǎn)存在時(shí)} len:=length(g，1，w) {頂點(diǎn)1到頂點(diǎn)w的距離} dfs(g，1，w，len); IF len > maxlen1 THEN BEGIN maxlen2:=maxlen1; maxlen1:=len; END ELSE IF len > maxlen2 maxlen2:=len w:=nextdaj(g，1，w); END return(maxlen1+maxlen2); ENDF;{find_diameter} PROC dfs(g:Graph; parent，child:vtxptr; VAR len:integer); { dfs返回時(shí)，len中存放的是從根到結(jié)點(diǎn)child所在的子樹(shù)的葉結(jié)點(diǎn)的最大距離} current_len:=len; {保存到當(dāng)前結(jié)點(diǎn)的路徑長(zhǎng)度} maxlen:=len; v:=firstadj(g，child); WHILE v!=0 DO BEGIN IF v=parent CONTINUE; len:=len+length(g，child，v); dfs(g，child，v，len); IF len>maxlen THEN maxlen:=len; v:=nextadj(g，child.v); len:=current_len; END len:=maxlen; ENDP;{dfs} 算法的主要過(guò)程是對(duì)圖g進(jìn)行深度優(yōu)先遍歷，若圖g以鄰接表的形式存儲(chǔ)，則時(shí)間復(fù)雜度為O(n+e)。 40.由關(guān)節(jié)點(diǎn)定義及特性可知，若生成樹(shù)的根有多于或等于兩棵子樹(shù)，則根結(jié)點(diǎn)是關(guān)節(jié)點(diǎn)；若生成樹(shù)某非葉子頂點(diǎn)v，其子樹(shù)中的結(jié)點(diǎn)沒(méi)有指向v的祖先的回邊，則v是關(guān)節(jié)點(diǎn)。因此，對(duì)圖G＝(v,{Edge})，將訪問(wèn)函數(shù)visited[v]定義為深度優(yōu)先遍歷連通圖時(shí)訪問(wèn)頂點(diǎn)v的次序號(hào)，并定義一個(gè)low( )函數(shù)： low(v)＝Min(visited[v],low[w],visited[k]) 其中(v,w)∈Edge，(v,k)∈Edge，w是v在深度優(yōu)先生成樹(shù)上的孩子結(jié)點(diǎn)，k是v在深度優(yōu)先生成樹(shù)上的祖先結(jié)點(diǎn)。在如上定義下，若low[w]>=visited[v]，則v是根結(jié)點(diǎn)，因w及其子孫無(wú)指向v的祖先的回邊。由此，一次深度優(yōu)先遍歷連通圖，就可求得所有關(guān)節(jié)點(diǎn)。 int visited[] ,low[]; //訪問(wèn)函數(shù)visited和low函數(shù)為全局變量。 int count; //記訪問(wèn)頂點(diǎn)個(gè)數(shù)。 AdjList g; //圖g以鄰接表方式存儲(chǔ) void dfs_articul(vertype v0) //深度優(yōu)先遍歷求關(guān)節(jié)點(diǎn)。 {count++; visited[v0]=count; //訪問(wèn)頂點(diǎn)順序號(hào)放入visited min=visited[v0]; //初始化訪問(wèn)初值。 p=g[v0].firstarc; //求頂點(diǎn)v的鄰接點(diǎn)。 while (p!=null) {w=p->adjvex; //頂點(diǎn)v的鄰接點(diǎn)。 if (visited[w]==0) //w未曾訪問(wèn)，w是v0的孩子。 {dfs_articul(g ,w); if (low[w]<min) min =low[w]; if (low[w]>=visited[v0]) printf(g[v0].vertex); //v0是關(guān)節(jié)點(diǎn)。 }//if else //w已被訪問(wèn)，是v的祖先。 if (visited[w]<min) min=visited[w]; p=p->next; }//while low[v0]=min; }//結(jié)束dfs_articul void get_articul( ) //求以鄰接表為存儲(chǔ)結(jié)構(gòu)的無(wú)向連通圖g的關(guān)節(jié)點(diǎn)。 {for (vi=1;vi<=n;vi++) visited[vi]=0; //圖有n個(gè)頂點(diǎn)，訪問(wèn)數(shù)組初始化。 count=1; visited[1]=1; //設(shè)鄰接表上第一個(gè)頂點(diǎn)是生成樹(shù)的根。 p=g[1].firstarc; v=p->adjvex; dfs_articul(v); if (count<n) //生成樹(shù)的根有兩棵以上子樹(shù)。 {printf(g[1].vertex);//根是關(guān)節(jié)點(diǎn) while(p->next!=null) {p=p->next; v=p->adjvex; if(visited[v]==0) dfs-articul(v); }//while }//if }//結(jié)束get-articul //DFSArticul()公有成員函數(shù) //遞歸:從v0出發(fā),通過(guò)深度優(yōu)先遍歷當(dāng)前圖, //查找并輸出該深度優(yōu)先生成樹(shù)上的所有關(guān)節(jié)點(diǎn) //算法描述概要:定義了dfn[]函數(shù),存放結(jié)點(diǎn)的DFS遍歷 //序數(shù),low[]函數(shù)存放通過(guò),當(dāng)前結(jié)點(diǎn)可以 ///////////////////////////////////////////////// template<class T,class E> int Graphlink<T,E>:  FSArticul(int v0,int* dfn,int* low){ static int count=0; //得到DFS序數(shù)的計(jì)數(shù)器 count++; int min=count; //當(dāng)前訪問(wèn)的結(jié)點(diǎn)v0的DFS序數(shù) dfn[v0]=count; //得到當(dāng)前訪問(wèn)頂點(diǎn)的DFS序數(shù) for(int ptr=getFirstNeighbor(v0) ;ptr!=-1 //遍歷結(jié)點(diǎn)v0所有的鄰接結(jié)點(diǎn) ;ptr=getNextNeighbor(v0,ptr)) { int w=ptr; //w是v0的鄰接結(jié)點(diǎn),w也是v0的子結(jié)點(diǎn) if(dfn[w]==0) //如果v0的子結(jié)點(diǎn)w沒(méi)有被訪問(wèn)過(guò) { DFSArticul( //遞歸:對(duì)以w為開(kāi)始頂點(diǎn)的子圖進(jìn)行遞歸求關(guān)節(jié)點(diǎn) w,dfn,low); if(low[w]<min) //退出遞歸以后,如果子結(jié)點(diǎn)u能達(dá)到的頂點(diǎn)DFS序數(shù)比 min=low[w]; //比v0能達(dá)到的更小 if(low[w]>=dfn[v0])//如果子結(jié)點(diǎn)u所能到達(dá)的頂點(diǎn)的DFS序數(shù)還沒(méi)有v0大 cout<<v0<<":" //說(shuō)明v0就是一個(gè)關(guān)節(jié)點(diǎn) <<getValue(v0) <<"是一個(gè)關(guān)節(jié)點(diǎn)."<<endl; } else if(dfn[w]<min) //如果w的DFS序數(shù)比當(dāng)前v0的最小回邊系數(shù)更小 min=dfn[w]; //說(shuō)明w已經(jīng)在v0之前訪問(wèn)過(guò)了<v0,w>是一條回邊 } low[v0]=min; //得到當(dāng)前結(jié)點(diǎn)v0的low[]函數(shù)值 return count; //返回當(dāng)前遍歷過(guò)的頂點(diǎn)的個(gè)數(shù) }; /////////////////////DFSArticul()公有成員函數(shù)結(jié)束 //FindArticul()公有成員函數(shù) //調(diào)用DFSArticul()函數(shù)找出當(dāng)前圖的 //所有的關(guān)節(jié)點(diǎn),并顯示出來(lái),思想：首先判斷根結(jié)點(diǎn) //是否有多于一個(gè)子樹(shù),如果是說(shuō)明根也是關(guān)節(jié)點(diǎn)，然后 //以根的每棵子樹(shù)根結(jié)點(diǎn)為起點(diǎn)繼續(xù)找關(guān)節(jié)點(diǎn) ///////////////////////////////////////////////// template<class T,class E> void Graphlink<T,E>::FindArticul() { int n=numVertices; int* dfn=new int[n]; //dfn[]函數(shù)的數(shù)組 int* low=new int[n]; //low[]函數(shù)的數(shù)組 for(int i=0;i<n;i++) //初始化dfn[]函數(shù) dfn=0; dfn[0]=1; //以0號(hào)頂點(diǎn)為遍歷的根結(jié)點(diǎn) int p=getFirstNeighbor(0); //獲取根結(jié)點(diǎn)0的第一個(gè)子結(jié)點(diǎn) int k=DFSArticul(p,dfn,low);//對(duì)第一棵子樹(shù)進(jìn)行尋找,得到第一棵子樹(shù)頂點(diǎn)個(gè)數(shù) if(k!=n-1) //如果頂點(diǎn)個(gè)數(shù)不是總頂點(diǎn)數(shù)-1 { //怎說(shuō)明根結(jié)點(diǎn)是關(guān)節(jié)點(diǎn) cout<<0<<":"<<getValue(0) <<"是一個(gè)關(guān)節(jié)點(diǎn)."<<endl; p=getNextNeighbor(0,p); //獲得子樹(shù)p的兄弟子樹(shù) while(p!=-1) //對(duì)其他的子樹(shù)進(jìn)行再次的關(guān)節(jié)點(diǎn)尋找 { if(dfn[p]==0) //如果p還沒(méi)有被訪問(wèn)過(guò),就從該頂點(diǎn)開(kāi)始尋找 DFSArticul(p,dfn,low); p=getNextNeighbor(0,p); }; }; }; |
|
回復(fù)話題 |
||
|
|
|
|