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 回答