【文章內容簡介】 visited[l]) if(exist_path_len(G,l,j,k1)) return 1。 //剩余路徑長度減一 }//for visited[i]=0。 //本題允許曾經被訪問過的結點出現(xiàn)在另一條路徑中 }//else return 0。 //沒找到 }//exist_path_len int path[MAXSIZE],visited[MAXSIZE]。 //暫存遍歷過程中的路徑 int Find_All_Path(ALGraph G,int u,int v,int k)//求有向圖 G中頂點 u到 v之間的所有簡單路徑 ,k表示當前路徑長度 { path[k]=u。 //加入當前路徑中 visited[u]=1。 if(u==v) //找到了一條簡單路徑 { printf(Found one path!\n)。 for(i=0。path[i]。i++) printf(%d,path[i])。 //打印輸出 } else for(p=[u].firstarc。p。p=pnextarc) { l=padjvex。 if(!visited[l]) Find_All_Path(G,l,v,k+1)。 //繼續(xù)尋找 } visited[u]=0。 path[k]=0。 //回溯 }//Find_All_Path main() { ... Find_All_Path(G,u,v,0)。 //在主函數中初次調用 ,k值應為 0 ... }//main int GetPathNum_Len(ALGraph G,int i,int j,int len)//求鄰接表方式存儲的有向圖 G的頂點 i 到 j 之間長度為 len的簡單路徑條數 { if(i==jamp。amp。len==0) return 1。 //找到了一條路徑 ,且長度符合要求 else if(len0) { sum=0。 //sum表示通過本結點的路徑數 visited[i]=1。 for(p=[i].firstarc。p。p=pnextarc) { l=padjvex。 if(!visited[l]) sum+=GetPathNum_Len(G,l,j,len1)//剩余路徑長度減一 }//for visited[i]=0。 //本題允許曾經被訪問過的結點出現(xiàn)在另一條路徑中 }//else return sum。 }//GetPathNum_Len int visited[MAXSIZE]。 int path[MAXSIZE]。 //暫存當前路徑 int cycles[MAXSIZE][MAXSIZE]。 //儲存發(fā)現(xiàn)的回路所包含的結點 int thiscycle[MAXSIZE]。 //儲存當前發(fā)現(xiàn)的一個回路 int cycount=0。 //已發(fā)現(xiàn)的回路個數 void GetAllCycle(ALGraph G)//求有向圖中所有的簡單回路 { for(v=0。v。v++) visited[v]=0。 for(v=0。v。v++) if(!visited[v]) DFS(G,v,0)。 //深度優(yōu)先遍歷 }//DFSTraverse void DFS(ALGraph G,int v,int k)//k表示當前結點在路徑上的序號 { visited[v]=1。 path[k]=v。 //記錄當前路徑 for(p=[v].firstarc。p。p=pnextarc) { w=padjvex。 if(!visited[w]) DFS(G,w,k+1)。 else //發(fā)現(xiàn)了一條回路 { for(i=0。path[i]!=w。i++)。 //找到 回路的起點 for(j=0。path[i+j]。i++) thiscycle[j]=path[i+j]。//把回路復制下來 if(!exist_cycle()) cycles[cycount++]=thiscycle。//如果該回路尚未被記錄過 ,就添加到記錄中 for(i=0。i。i++) thiscycle[i]=0。 //清空目前回路數組 }//else }//for path[k]=0。 visited[k]=0。 //注意只有 當前路徑上的結點 visited為真 .因此一旦遍歷中發(fā)現(xiàn)當前結點 visited為真 ,即表示發(fā)現(xiàn)了一條回路 }//DFS int exist_cycle()//判斷 thiscycle數組中記錄的回路在 cycles的記錄中是否已經存在 { int temp[MAXSIZE]。 for(i=0。icycount。i++) //判斷已有的回路與 thiscycle 是否相同 { //也就是 ,所有結點和它們的順序都相同 j=0。c=thiscycle 。 //例如 ,142857和 857142是 相同的回路 for(k=0。cycles[i][k]!=camp。amp。cycles[i][k]!=0。k++)。//在 cycles 的一個行向量中尋找等于 thiscycle 第一個結點的元素 if(cycles[i][k]) //有與之相同的一個元素 { for(m=0。cycles[i][k+m]。m++) temp[m]=cycles[i][k+m]。 for(n=0。nk。n++,m++) temp[m]=cycles[i][n]。 //調整 cycles 中的當前記錄的循環(huán)相位并放入 temp數組中 if(!StrCompare(temp,thiscycle)) //與 thiscycle 比較 return 1。 //完全相等 for(m=0。m。m++) temp[m]=0。 //清空這個數組 } }//for return 0。 //所有現(xiàn)存回路都不與 thiscycle 完全相等 }//exist_cycle 分析 :這個算法的思想是 ,在遍歷中暫存當前路徑 ,當遇到一個 結點已經在路徑之中時就表明存在一條回路 。掃描路徑向量 path可以獲得這條回路上的所有結點 .把結點序列 (例如 ,142857)存入 thiscycle 中 。由于這種算法中 ,一條回路會被發(fā)現(xiàn)好幾次 ,所以必須先判斷該回路是否已經在 cycles 中被記錄過 ,如果沒有才能存入cycles 的一個行向量中 .把 cycles 的每一個行向量取出來與之比較 .由于一條回路可能有多種存儲順序 ,比如 142857等同于 285714和 571428,所以還要調整行向量的次序 ,并存入 temp數組 ,例如 ,thiscycle 為 142857第一個結點為 1,cycles 的當前向量為 857142,則找到后者中的 1,把 1后部分提到 1前部分前面 ,最終在 temp中得到 142857,與 thiscycle 比較 ,發(fā)現(xiàn)相同 ,因此 142857和 857142是同一條回路 ,不予存儲 .這個算法太復雜 ,很難保證細節(jié)的準確性 ,大家理解思路便可 .希望有人給出更加簡捷的算法 . int visited[MAXSIZE]。 int finished[MAXSIZE]。 int count。 //count在第一次深度優(yōu)先遍歷中用于指示 finished數組的填充位置 void Get_SGraph(OLGraph G)//求十字鏈表結構儲存的有向圖 G的強連通分量 { count=0。 for(v=0。v。v++) visited[v]=0。 for(v=0。v。v++) //第一次深度優(yōu)先遍歷建立 finished數組 if(!visited[v]) DFS1(G,v)。 for(v=0。v。v++) visited[v]=0。 //清空 visited數組 for(i=。i=0。i) //第二次逆向的深度優(yōu)先遍歷 { v=finished(i)。 if(!visited[v]) { printf(\n)。 //不同的強連通分量在不同的行輸出 DFS2(G,v)。 } }//for }//Get_SGraph void DFS1(OLGraph G,int v)//第一次深度優(yōu)先遍歷的算法 { visited[v]=1。 for(p=[v].firstout。p。p=ptlink) { w=pheadvex。 if(!visited[w]) DFS1(G,w)。 }//for finished[++count]=v。 //在第一次遍歷中建立 finished數組 }//DFS1 void DFS2(OLGraph G,int v)//第二次逆向的深度優(yōu)先遍歷的算法 { visited[v]=1。 printf(%d,v)。 //在第二次遍歷中輸出結點序號 for(p=[v].firstin。p。p=phlink) { w=ptailvex。 if(!visited[w]) DFS2(G,w