【文章內(nèi)容簡介】 adjvex=i。 snext=gin[j].firstarc。 gin[j].firstarc=s。 p=pnext。//下一個鄰接點。 }//while }//for } 6. void AdjListToAdjMatrix(AdjList gl, AdjMatrix gm) //將圖的鄰接表表示轉(zhuǎn)換為鄰接矩陣表示。 {for (i=1。i=n。i++) //設(shè)圖有 n個頂點，鄰接矩陣初始化。 for (j=1。j=n。j++) gm[i][j]=0。 for (i=1。i=n。i++) {p=gl[i].firstarc。 //取第一個鄰接點。 while (p!=null) {gm[i][padjvex]=1。p=pnext。 }//下一個鄰接點 }//for }//算法結(jié)束 7. void AdjMatrixToAdjList( AdjMatrix gm, AdjList gl ) //將圖的鄰接矩陣表示法轉(zhuǎn)換為鄰接表表示法。 {for (i=1。i=n。i++) //鄰接表表頭向量初始化。 {scanf(amp。gl[i].vertex)。 gl[i].firstarc=null。} for (i=1。i=n。i++) for (j=1。j=n。j++) if (gm[i][j]==1) {p=(ArcNode *)malloc(sizeof(ArcNode)) 。//申請結(jié)點空間。 padjvex=j。//頂點 I的鄰接點是 j pnext=gl[i].firstarc。 gl[i].firstarc=p。 //鏈入頂點 i的鄰接點鏈表中 } }//end [算法討論 ] 算法中鄰接表中頂點在向量表中的下標(biāo)與其在鄰接矩陣中的行號相同。 8.[題目分析 ] 在有向圖中，判斷頂點 Vi 和頂點 Vj間是否有路徑，可采用遍 歷的方法，從頂點 Vi出發(fā)，不論是深度優(yōu)先遍歷（ dfs）還是寬度優(yōu)先遍歷（ bfs），在未退出 dfs或 bfs前 ,若訪問到 Vj，則說明有通路，否則無通路。設(shè)一全程變量 flag。初始化為 0，若有通路，則 flag=1。 算法 1： int visited[]=0。 //全局變量，訪問數(shù)組初始化 int dfs(AdjList g , vi) //以鄰接表為存儲結(jié)構(gòu)的有向圖 g，判斷頂點 Vi 到 Vj 是否有通路 ,返回 1 或 0 表示有或無 { visited[vi]=1。 //visited是訪問數(shù)組，設(shè)頂點的信息就 是頂點編號。 p=g[vi].firstarc。 //第一個鄰接點。 while ( p!=null) { j=padjvex。 if (vj==j) { flag=1。 return（ 1） 。} //vi 和 vj 有通路。 if (visited[j]==0) dfs(g,j)。 p=pnext； }//while if (!flag) return(0)。 }//結(jié)束 [算法討論 ] 若頂點 vi 和 vj 不是編號，必須先用頂點定位函數(shù) ,查出其在鄰接表頂點向量中的下標(biāo) i 和 j。下面算法 2輸出 vi 到 vj 的路徑，其思想是用一個棧存放遍歷的頂點，遇到頂點 vj時輸出路徑。 算法 2： void dfs(AdjList g , int i) //有向圖 g的頂點 vi（編號 i）和頂點 vj（編號 j）間是否有路徑，如有，則輸出。 {int top=0,stack[]。 //stack是存放頂點編號的棧 visited[i]=1。 //visited 數(shù)組在進(jìn)入 dfs前已初始化。 stack[++top]=i。 p=g[i].firstarc。 /求第一個鄰接點 . while (p) {if (padjvex==j) {stack[++top]=j。 printf( 頂點 vi 和 vj 的路徑為： \n)。 for (i=1。 i=top。 i++) printf( %4d,stack[i])。 exit(0)。 }//if else if (visited[padjvex]==0) {dfs(g,gadjvex)。 top。 p=pnext。}//else if }//while }//結(jié)束算法 2 算法 3：本題用非遞歸算法求解。 int Connectij (AdjList g , vertype vi , vj ) //判斷 n個頂點以鄰接表表示的有向圖 g中，頂點 Vi 各 Vj 是否有路徑，有則返回 1，否則返回 0。 { for (i=1。i=n。i++) visited[i]=0。 //訪問標(biāo)記數(shù)組初始化。 i=GraphLocateVertex(g,vi)。 //頂點定位，不考慮 vi或 vj不在圖中的情況。 j=GraphLocateVertex(g,vj)。 int stack[],top=0。stack[++top]=i。 while(top0) {k=stack[top]。 p=g[k].firstarc。 while(p!=null amp。amp。 visited[padjvex]==1) p=pnext。 //查第 k個鏈表中第一個未訪問的弧結(jié)點。 if(p==null) top。 else {i=padjvex。 if(i==j) return(1)。 //頂點 vi和 vj 間有路徑。 else {visited[i]=1。 stack[++top]=i。}//else }//else }while return(0)。 } //頂點 vi和 vj 間無通路。 9. void DeletEdge(AdjList g,int i,j) //在用鄰接表方式存儲的無向圖 g中，刪除邊 (i,j) {p=g[i].firstarc。 pre=null。 //刪頂點 i 的邊 結(jié)點 (i,j),pre是前驅(qū)指針 while (p) if (padjvex==j) {if(pre==null)g[i].firstarc=pnext。else prenext=pnext。free(p)。}//釋放結(jié)點空間。 else {pre=p。 p=pnext。} //沿鏈表繼續(xù)查找 p=g[j].firstarc。 pre=null。 //刪頂點 j 的邊結(jié)點 (j,i) while (p) if (padjvex==i) {if(pre==null)g[j].firstarc=pnext。else prenext=pnext。free(p)。}//釋放結(jié)點空間。 else {pre=p。 p=pnext。} //沿鏈表繼續(xù)查找 }// DeletEdge [算法討論 ] 算法中假定給的 i， j 均存在，否則應(yīng)檢查其合法性。若未給頂點編號，而給出頂點信息，則先用頂點定位函數(shù)求出其在鄰接表頂點向量中的下標(biāo) 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[i].firstarc。 pre=null。 while (p) if (padjvex==j) {if(pre==null) g[i].firstarc=pnext。else prenext=pnext。free(p)。}//釋放結(jié) 點空間。 else { pre=p。 p=pnext。} }//結(jié)束 11. void InsertArc ( OrthList g ,vertype vi,vj) //在以十字鏈表示的有向圖 g中插入弧 vi,vj { i=GraphLocateVertex(g,vi)。 //頂點定位 . j=GraphLocateVertex(g,vj)。 p=(OrArcNode *)malloc(sizeof(OrArcNode))。 p=headvex=j。 p=tailvex=i。 //填寫弧 結(jié)點信息并插入十字鏈表。 pheadlink=g[j].firstin。 g[j].firstin=p。 ptaillink=g[i].firstout。 g[i].firstout=p。 }//算法結(jié)束 12. [題目分析 ]在有向圖的鄰接表中，求頂點的出度容易，只要簡單在該頂點的鄰接點鏈表中查結(jié)點個數(shù)即可。而求頂點的入度，則要遍歷整個鄰接表。 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[i].firstarc。//取頂點 i 的鄰接表。 while (p) {if (padjvex==k) count++。 p=pnext。 }//while }//if return(count)。 //頂點 k的入度 . } 13. [題目分析 ]有向圖判斷回路要比無向圖復(fù)雜。利用深度優(yōu)先遍歷，將頂 點分成三類：未訪問；已訪問但其鄰接點未訪問完 。已訪問且其鄰接點已訪問完。下面用 0， 1， 2表示這三種狀態(tài)。前面已提到，若 dfs（ v）結(jié)束前出現(xiàn)頂點 u 到 v 的回邊，則圖中必有包含頂點 v和 u的回路。對應(yīng)程序中 v的狀態(tài)為 1，而 u是正訪問的頂點，若我們找出 u的下一鄰接點的狀態(tài)為 1，就可以輸出回路了。 void Print(int v,int start ) //輸出從頂點 start開始的回路。 {for(i=1。i=n。i++) if(g[v][i]!=0 amp。amp。 visited[i]==1 ) //若存 在邊（ v,i），且頂點 i的狀態(tài)為 1。 {printf(“%d”,v)。 if(i==start) printf(“ \n”)。 else Print(i,start)。break。}//if }//Print void dfs(int v) {visited[v]=1。 for(j=1。j=n。j++ ) if (g[v][j]!=0) //存在邊 (v,j) if (visited[j]!=1) {if (!visited[j]) dfs(j)。 }//if else {cycle=1。 Print(j,j)。} visited[v]=2。 }//dfs void find_cycle() //判斷是否有回路，有則輸出鄰接矩陣。 visited數(shù)組為全局變量。 {for (i=1。i=n。i++) visited[i]=0。 for (i=1。i=n。i++ ) if (!visited[i]) dfs(i)。 }//find_cycle 14． [題目分析 ]有幾種方法判斷有向圖是否存在環(huán)路，這里使用拓?fù)渑判蚍?。?有向圖的頂點進(jìn)行拓?fù)渑判?，若拓?fù)渑判虺晒?，則無環(huán)路；否則，存在環(huán)路。題目已假定有向圖用十字鏈表存儲，為方便運算，在頂點結(jié)點中，再增加一個入度域 indegree，存放頂點的入度。入度為零的頂點先輸出。為節(jié)省空間，入度域還起棧的作用。值得注意的是，在鄰接表中，頂點的鄰接點非常清楚，頂點的單鏈表中的鄰接點域都是頂點的鄰接點。由于十字鏈表邊（?。┙Y(jié)點個數(shù)與邊（?。﹤€數(shù)相同（不象無向圖邊結(jié)點個數(shù)是邊的二倍），因此，對某頂點 v, 要判斷其鄰接點是 headvex還是 tailvex。 int Topsor(OrthList g) //判斷以十字鏈表為存儲結(jié)構(gòu)的有向圖 g是否存在環(huán)路，如是，返回 1，否則，返回0。 {int top=0。 //用作棧頂指針 for (i=1。i=n。i++) //求各頂點的入度。設(shè)有向圖 g有 n個頂點，初始時入度域均為 0 {p=g[i].firstin。 //設(shè)頂點信息就是頂點編號，否則，要進(jìn)行頂點定位 while(p) {g[i].indegree++。 //入度域增 1 if (p