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