【正文】 t(T,closedge[k].adjvex,k)。i。 }//if closedge[k].lowcost=0。p。j++) //以下在 Prim算法基礎(chǔ)上稍作改動 if(j!=k) { closedge[j]={k,Max_int}。T)//從頂點 k出發(fā) ,構(gòu)造鄰接表結(jié)構(gòu)的有向圖 G的最小生成森林 T,用孩子兄弟鏈表存儲 { for(j=0。 if(!visited[w]) DFS2(G,w)。p。 printf(%d,v)。 }//for finished[++count]=v。p=ptlink) { w=pheadvex。 for(p=[v].firstout。 //不同的強連通分量在不同的行輸出 DFS2(G,v)。i) //第二次逆向的深度優(yōu)先遍歷 { v=finished(i)。 //清空 visited數(shù)組 for(i=。v。v++) //第一次深度優(yōu)先遍歷建立 finished數(shù)組 if(!visited[v]) DFS1(G,v)。 for(v=0。v。 //count在第一次深度優(yōu)先遍歷中用于指示 finished數(shù)組的填充位置 void Get_SGraph(OLGraph G)//求十字鏈表結(jié)構(gòu)儲存的有向圖 G的強連通分量 { count=0。 int finished[MAXSIZE]。掃描路徑向量 path可以獲得這條回路上的所有結(jié)點 .把結(jié)點序列 (例如 ,142857)存入 thiscycle 中 。 //清空這個數(shù)組 } }//for return 0。m。 //調(diào)整 cycles 中的當(dāng)前記錄的循環(huán)相位并放入 temp數(shù)組中 if(!StrCompare(temp,thiscycle)) //與 thiscycle 比較 return 1。nk。m++) temp[m]=cycles[i][k+m]。//在 cycles 的一個行向量中尋找等于 thiscycle 第一個結(jié)點的元素 if(cycles[i][k]) //有與之相同的一個元素 { for(m=0。cycles[i][k]!=0。cycles[i][k]!=camp。c=thiscycle 。icycount。 //注意只有 當(dāng)前路徑上的結(jié)點 visited為真 .因此一旦遍歷中發(fā)現(xiàn)當(dāng)前結(jié)點 visited為真 ,即表示發(fā)現(xiàn)了一條回路 }//DFS int exist_cycle()//判斷 thiscycle數(shù)組中記錄的回路在 cycles的記錄中是否已經(jīng)存在 { int temp[MAXSIZE]。 //清空目前回路數(shù)組 }//else }//for path[k]=0。i。//把回路復(fù)制下來 if(!exist_cycle()) cycles[cycount++]=thiscycle。path[i+j]。i++)。 else //發(fā)現(xiàn)了一條回路 { for(i=0。p=pnextarc) { w=padjvex。 //記錄當(dāng)前路徑 for(p=[v].firstarc。 //深度優(yōu)先遍歷 }//DFSTraverse void DFS(ALGraph G,int v,int k)//k表示當(dāng)前結(jié)點在路徑上的序號 { visited[v]=1。v。v++) visited[v]=0。 //已發(fā)現(xiàn)的回路個數(shù) void GetAllCycle(ALGraph G)//求有向圖中所有的簡單回路 { for(v=0。 //儲存發(fā)現(xiàn)的回路所包含的結(jié)點 int thiscycle[MAXSIZE]。 int path[MAXSIZE]。 //本題允許曾經(jīng)被訪問過的結(jié)點出現(xiàn)在另一條路徑中 }//else return sum。p=pnextarc) { l=padjvex。 for(p=[i].firstarc。 //找到了一條路徑 ,且長度符合要求 else if(len0) { sum=0。amp。 //回溯 }//Find_All_Path main() { ... Find_All_Path(G,u,v,0)。 //繼續(xù)尋找 } visited[u]=0。p=pnextarc) { l=padjvex。 //打印輸出 } else for(p=[u].firstarc。path[i]。 if(u==v) //找到了一條簡單路徑 { printf(Found one path!\n)。 //暫存遍歷過程中的路徑 int Find_All_Path(ALGraph G,int u,int v,int k)//求有向圖 G中頂點 u到 v之間的所有簡單路徑 ,k表示當(dāng)前路徑長度 { path[k]=u。 //本題允許曾經(jīng)被訪問過的結(jié)點出現(xiàn)在另一條路徑中 }//else return 0。 if(!visited[l]) if(exist_path_len(G,l,j,k1)) return 1。p。 //找到了一條路徑 ,且長度符合要求 else if(k0) { visited[i]=1。amp。 }//TopoNo 分析 :只要按拓撲逆序?qū)旤c編號 ,就可以使鄰接矩陣成為下三角矩陣 . int visited[MAXSIZE]。i=n。 }//for }//while if(count) return ERROR。p=pnextarc) { k=padjvex。 for(p=[i].firstarc。 new[i]=n。 //零入度結(jié)點入棧 count=0。i。 InitStack(S)。 //儲存結(jié)點的新序號 n=。 Push(S,k)。!visited[k]) { visit(k)。 //向右走一步 if(kamp。 Gettop(S,i)。 Push(S,j)。!visited[j]) { visit(j)。 if(jamp。amp。 visited =1。 Push(S,GetVex(S,1))。 }//exist_path_BFS void STraverse_Nonrecursive(Graph G)//非遞歸遍歷強連通圖 G { int visited[MAXSIZE]。 if(!visited[k]) EnQueue(Q,k)。p=pnextarc) { k=padjvex。 for(p=[i].firstarc。 while(!QueueEmpty(Q)) { DeQueue(Q,u)。 InitQueue(Q)。exist_path(k,j)) return 1。 if(!visited[k]amp。p。 //i 就是 j else { visited[i]=1。 }//is_adj int visited[MAXSIZE]。p=pnextarc) if(padjvex==n) return 1。 }//for }//for }//Pass_ALGraph int is_adj(ALGraph G,int m,int n)//判斷有向圖 G中是否存在邊 (m,n),是則返回 1,否則返回 0 { for(p=[m].firstarc。amp。q=qnextarc) { z=qadjvex。 for(q=[y].firstarc。p。x。//圖不可傳遞的條件 }//if return 1。amp。amp。z。y。x。 }//else //插入 j 鏈表尾部 }//for return OK。 } if(rjvex==j) rjlink=p。 if(qjvex==j) q=qjlink。 else { q=[i].firstedge。//注意 i 值既可能出現(xiàn)在邊結(jié)點的 ivex域中 , else rjlink=p。 else q=qjlink。 while(q) { r=q。 //邊結(jié)點賦初值 if(![i].firstedge) [i].firstedge=p。 pilink=NULL。 pivex=i。 if((j=LocateVex(G,h))0) return ERROR。h=getchar()。m=a。m++) [m].data=getchar()。 for(m=0。 if(a0) return ERROR。 scanf(%d,amp。 if(v0) return ERROR。 scanf(%d,amp。 }//Delete_Arc Status