0

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アルゴリズムの実装について良い考えを持っていると思います。コードを理解することに懸念がある場合は、私に知らせてください。

4

1 に答える 1

0

のアルゴリズムdfsが壊れています。ノード1からのエッジを調べると、ノード1からノード2へのエッジが検出され、1が2の親としてマークされます。その後、ノード5からノード2へのエッジが検出され、5が親としてマークされます。 2の、parent配列内の前のエントリを置き換えます。

後で、1から5（から1）のサイクルがあると判断すると、を呼び出しますfind_path(5, 1)。ただし、find_pathノード1を見つけることはできません。これは、5から親をたどると、4、3、2になり、5に戻るためです。

于 2012-09-14T17:20:33.697 に答える