DFSアルゴリズムを使用してグラフ内のサイクルを見つけるためのコードを書いています。しかし、サイクルのパスを印刷しようとすると、非常に奇妙なことが起こります。コメントで私の懸念を読んでください。
#include <iostream>
#include "graph.h"
#include <stdio.h>
using namespace std;
int discovered[MAXV+1];
int parent[MAXV+1];
//Printing path that contains the cycle
void find_path(int start, int end)
{
int s = start;
int e = end;
while(s != e)
{
cout<<s<<" ";
s = parent[s];
}
/*The loop above does not stops ;
which means the condition parent[s] == e ;
does not meet . However , on printing out the
values of s , parent[s] , and e , on successive iteration
I can see that the value of parent[s] and e becomes
equal after a certain time , even though the loop does not
terminate.
*/
}
void dfs(graph *g , int start)
{
int dis = 1;
int u = 0 ;
edgenode *p;
p = g->edges[start];
discovered[start] = dis;
while(p!= NULL)
{
u = p->y;
parent[u] = start;
if(discovered[u]== 1){ cout<<"Cycle"<<start<<u<<endl; find_path(start,u);}
else dfs(g,u);
p = p->next;
}
discovered[start] = dis +1;
printf("\n");
}
int main()
{
for(int i= 1; i<=MAXV+1; i++)
{
discovered[i] = false;
parent[i] = -1;
}
graph *g = new graph();
read_graph(g,true);
dfs(g,1);
}
それで、上記の再帰を呼び出す際の私のロジックに欠陥がありますか、または私のg++コンパイラが奇妙に動作しています。私のコードをよく読んでいただければ幸いです。ありがとう 。
PS:私はすでにグラフ構造を実装していると想定できます。これはコンパイル時に組み込みます。そして、私はあなたがBFSアルゴリズムの実装について良い考えを持っていると思います。コードを理解することに懸念がある場合は、私に知らせてください。