w=p->ad if(visited w)DFS(G, w, k+1) else∥发现了一条回路 or(i=0path[=w;H+),/找到回路的起点 for(=0path计j计+) thiscycle[i}= pathi+j;/把回路复制下来 if(lexist cycle) cycles[cycountt+- thiscycle/如果该回路尚未被记录过,就添 加到记录中 for(i=0; G. vexnum计+) thiscycle[}=0,/清空目前回路数组 }/f path[k=0; visited[k}=0,/注意只有当前路径上的结点vsed为真因此一旦遍历中发现当 前结点vsed为真,即表示发现了一条回路 1//DFS int exist cycle(∥)判断 r thiscycle数组中记录的回路在 cycles的记录中是否己经存在 int tempMAXSIZEI for(i=0 Account;计+)∥判断已有的回路与 thiscycle是否相同 /也就是所有结点和它们的顺序都相同 j=0;c= thiscycle&#0;∥例如,142857和857142是相同的回路 for(k=0; cycles[k]=c&& cyclesojlk]=0k+)/在 cycles的一个行向量中寻找 等于 thiscycle第一个结点的元素 if(cycles[ik])∥有与之相同的一个元素 for(m=0; cyclesikk+m); m++) temp[m=cycles[][k+m] for(n=0; n<k, n++, m++) 数丝pmJ=gyc∥调整cycs中的当前记录的循环相位并放入temp if( StrCompare(temp, thiscycle)∥与 thiscycle比较 retur1;∥完全相等 or(m=0m< G. vexnum;mn++) temp[m}=0,/清空这个数组 i//for return0,∥所有现存回路都不与 thiscycle完全相等 iexist cycle 分析这个算法的思想是在遍历中暂存当前路径当遇到一个结点已经在路径之 中时就表明存在一条回路扫描路径向量path可以获得这条回路上的所有结点 把结点序列(例如,142857)存入 thiscycle中;由于这种算法中,一条回路会被发现好 几次所以必须先判断该回路是否已经在 cycles中被记录过如果没有才能存入 cycles的一个行向量中把 cycles的每一个行向量取出来与之比较由于一条回路{ w=p->adjvex; if(!visited[w]) DFS(G,w,k+1); else //发现了一条回路 { 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<G.vexnum;i++) thiscycle[i]=0; //清空目前回路数组 }//else }//for path[k]=0; visited[k]=0; //注意只有当前路径上的结点 visited 为真.因此一旦遍历中发现当 前结点 visited 为真,即表示发现了一条回路 }//DFS int exist_cycle()//判断thiscycle数组中记录的回路在cycles的记录中是否已经存在 { int temp[MAXSIZE]; for(i=0;i<cycount;i++) //判断已有的回路与 thiscycle 是否相同 { //也就是,所有结点和它们的顺序都相同 j=0;c=thiscycle&#0;; //例如,142857 和 857142 是相同的回路 for(k=0;cycles[i][k]!=c&&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;n<k;n++,m++) temp[m]=cycles[i][n]; //调整 cycles 中的当前记录的循环相位并放入 temp 数组中 if(!StrCompare(temp,thiscycle)) //与 thiscycle 比较 return 1; //完全相等 for(m=0;m<G.vexnum;m++) temp[m]=0; //清空这个数组 } }//for return 0; //所有现存回路都不与 thiscycle 完全相等 }//exist_cycle 分析:这个算法的思想是,在遍历中暂存当前路径,当遇到一个结点已经在路径之 中时就表明存在一条回路;扫描路径向量 path 可以获得这条回路上的所有结点. 把结点序列(例如,142857)存入 thiscycle 中;由于这种算法中,一条回路会被发现好 几次,所以必须先判断该回路是否已经在 cycles 中被记录过,如果没有才能存入 cycles 的一个行向量中.把 cycles 的每一个行向量取出来与之比较.由于一条回路