【正文】 t=getchar()。 //t為弧尾 ,h為弧頭 if((i=LocateVex(G,t))0) return ERROR。 //頂點(diǎn)未找到 p=(EBox*)malloc(sizeof(EBox))。pjvex=j。pjlink=NULL。 else { q=[i].firstedge。 if(qivex==i) q=qilink。 } if(rivex==i) rilink=p。 //又可能出現(xiàn)在邊結(jié)點(diǎn)的 jvex域中 }//else //插入 i 鏈表尾部 if(![j].firstedge) [j].firstedge=p。 while(q) { r=q。 else q=qilnk。 else rilink=p。 }//Build_AdjList int Pass_MGraph(MGraph G)//判斷一個(gè)鄰接矩陣存儲(chǔ)的有向圖是不是可傳遞的 ,是則返回 1,否則返回 0 { for(x=0。x++) for(y=0。y++) if([x][y]) { for(z=0。z++) if(z!=xamp。[y][z]amp。![x][z]) return 0。 }//Pass_MGraph 分析 :本算法的時(shí)間復(fù)雜度大概是 O(n^2*d). int Pass_ALGraph(ALGraph G)//判斷一個(gè)鄰接表存儲(chǔ)的有向圖是不是可傳遞的 ,是則返回 1,否則返回 0 { for(x=0。x++) for(p=[x].firstarc。p=pnextarc) { y=padjvex。q。 if(z!=xamp。!is_adj(G,x,z)) return 0。p。 return 0。 //指示頂點(diǎn)是否在當(dāng)前路徑上 int exist_path_DFS(ALGraph G,int i,int j)//深度優(yōu)先判斷有向圖 G中頂點(diǎn) i 到頂點(diǎn)j 是否有路徑 ,是則返回 1,否則返回 0 { if(i==j) return 1。 for(p=[i].firstarc。p=pnextarc) { k=padjvex。amp。//i 下游的頂點(diǎn)到 j 有路徑 }//for }//else }//exist_path_DFS int exist_path_BFS(ALGraph G,int i,int j)//廣度優(yōu)先判斷有向圖 G中頂點(diǎn) i 到頂點(diǎn)j 是否有路徑 ,是則返回 1,否則返回 0 { int visited[MAXSIZE]。 EnQueue(Q,i)。 visited[u]=1。p。 if(k==j) return 1。 }//for }//while return 0。 InitStack(S)。 //將第一個(gè)頂點(diǎn)入棧 visit(1)。 while(!StackEmpty(S)) { while(Gettop(S,i)amp。i) { j=FirstAdjVex(G,i)。amp。 visited[j]=1。 //向左走到盡頭 } }//while if(!StackEmpty(S)) { Pop(S,j)。 k=NextAdjVex(G,i,j)。amp。 visited[k]=1。 } }//if }//while }//Straverse_Nonrecursive 分析 :本算法的基本思想與二叉樹的先序遍歷非遞歸算法相同 ,請(qǐng)參考 是強(qiáng)連通圖 ,所以從第一個(gè)結(jié)點(diǎn)出發(fā)一定能夠訪問到所有結(jié)點(diǎn) . 見書后解答 . Status TopoNo(ALGraph G)//按照題目要求順序重排有向圖中的頂點(diǎn) { int new[MAXSIZE],indegree[MAXSIZE]。 FindInDegree(G,indegree)。 for(i=1。i++) if(!indegree[i]) Push(S,i)。 while(!StackEmpty(S)) { Pop(S,i)。 //記錄結(jié)點(diǎn)的拓?fù)淠嫘蛐蛱?hào) count++。p。 if(!(indegree[k])) Push(S,k)。 //圖中存在環(huán) for(i=1。i++) printf(Old No:%d New No:%d\n,i,new[i]) return OK。 int exist_path_len(ALGraph G,int i,int j,int k)//判斷鄰接表方式存儲(chǔ)的有向圖 G的頂點(diǎn) i 到 j 是否存在長(zhǎng)度為 k的簡(jiǎn)單路徑 { if(i==jamp。k==0) return 1。 for(p=[i].firstarc。p=pnextarc) { l=padjvex。 //剩余路徑長(zhǎng)度減一 }//for visited[i]=0。 //沒找到 }//exist_path_len int path[MAXSIZE],visited[MAXSIZE]。 //加入當(dāng)前路徑中 visited[u]=1。 for(i=0。i++) printf(%d,path[i])。p。 if(!visited[l]) Find_All_Path(G,l,v,k+1)。 path[k]=0。 //在主函數(shù)中初次調(diào)用 ,k值應(yīng)為 0 ... }//main int GetPathNum_Len(ALGraph G,int i,int j,int len)//求鄰接表方式存儲(chǔ)的有向圖 G的頂點(diǎn) i 到 j 之間長(zhǎng)度為 len的簡(jiǎn)單路徑條數(shù) { if(i==jamp。len==0) return 1。 //sum表示通過本結(jié)點(diǎn)的路徑數(shù) visited[i]=1。p。 if(!visited[l]) sum+=GetPathNum_Len(G,l,j,len1)//剩余路徑長(zhǎng)度減一 }//for visited[i]=0。 }//GetPathNum_Len int visited[MAXSIZE]。 //暫存當(dāng)前路徑 int cycles[MAXSIZE][MAXSIZE]。 //儲(chǔ)存當(dāng)前發(fā)現(xiàn)的一個(gè)回路 int cycount=0。v。 for(v=0。v++) if(!visited[v]) DFS(G,v,0)。 path[k]=v。p。 if(!visited[w]) DFS(G,w,k+1)。path[i]!=w。 //找到 回路的起點(diǎn) for(j=0。i++) thiscycle[j]=path[i+j]。//如果該回路尚未被記錄過 ,就添加到記錄中 for(i=0。i++) thiscycle[i]=0。 visited[k]=0。 for(i=0。i++) //判斷已有的回路與 thiscycle 是否相同 { //也就是 ,所有結(jié)點(diǎn)和它們的順序都相同 j=0。 //例如 ,142857和 857142是 相同的回路 for(k=0。amp。k++)。cycles[i][k+m]。 for(n=0。n++,m++) temp[m]=cycles[i][n]。 //完全相等 for(m=0。m++) temp[m]=0。 //所有現(xiàn)存回路都不與 thiscycle 完全相等 }//exist_cycle 分析 :這個(gè)算法的思想是 ,在遍歷中暫存當(dāng)前路徑 ,當(dāng)遇到一個(gè) 結(jié)點(diǎn)已經(jīng)在路徑之中時(shí)就表明存在一條回路 。由于這種算法中 ,一條回路會(huì)被發(fā)現(xiàn)好幾次 ,所以必須先判斷該回路是否已經(jīng)在 cycles 中被記錄過 ,如果沒有才能存入cycles 的一個(gè)行向量中 .把 cycles 的每一個(gè)行向量取出來與之比較 .由于一條回路可能有多種存儲(chǔ)順序 ,比如 142857等同于 285714和 571428,所以還要調(diào)整行向量的次序 ,并存入 temp數(shù)組 ,例如 ,thiscycle 為 142857第一個(gè)結(jié)點(diǎn)為 1,cycles 的當(dāng)前向量為 857142,則找到后者中的 1,把 1后部分提到 1前部分前面 ,最終在 temp中得到 142857,與 thiscycle 比較 ,發(fā)現(xiàn)相同 ,因此 142857和 857142是同一條回路 ,不予存儲(chǔ) .這個(gè)算法太復(fù)雜 ,很難保證細(xì)節(jié)的準(zhǔn)確性 ,大家理解思路便可 .希望有人給出更加簡(jiǎn)捷的算法 . int visited[MAXSIZE]。 int count。 for(v=0。v++) visited[v]=0。v。 for(v=0。v++) visited[v]=0。i=0。 if(!visited[v]) { printf(\n)。 } }//for }//Get_SGraph void DFS1(OLGraph G,int v)//第一次深度優(yōu)先遍歷的算法 { visited[v]=