DFS找到所有可能的路径 - 我哪里错了？

-1

我需要实现DFS从顶点查找所有可能的路径，说“项目”
到目前为止，我有以下，我不明白我要去哪里错了。DFS找到所有可能的路径 - 我哪里错了？

void dfs() 
{ 
    int i; 
    for(i=1;i<=nodecount;i++) 
    { 
     visited[i]=0; 
    } 
    push(item); 
    while(top!=0) 
    { 
     pop(); 
     visited[item]=1; 
     for(i=1;i<nodecount;i++) 
     { 
      if(topo[item][i]==1) 
      { 
       if(visited[i]==0) 
       { 
        item=i; 
        visited[i]=1; 
        push(item); 
       } 
      } 
     } 
    } 
}

示例：如果我有一个无向图，其中

节点1被连接到2,4-
节点2被连接到1,4,3
节点3是连接到2,5,6
节点4连接到1,2,5
节点5连接到4,3,6
节点6连接到3,5-

有了这个代码，如果项= 2，那么我应该得到

2-1-4-5-6-3
2- 1
2-1-4
2-2-1-5-6-3

等。

但我正在逐渐

1-4
1-4-5
1-4
1-4-3

来源

2015-10-14 user24603

你认为什么是错的？ – sashas

如果项目是“1”，而不是像说“1 2 4 5”那样获得路径，那么我得到“2 3 2 4”或类似的东西。首先，即使我跟踪访问哪些节点，节点仍在重复。其次，源（项目）不在路径中的节点列表中。 – user24603

'while（top！= 0）{...}'你不会改变'top'的值，是吗？但是，您需要提供更多信息。您需要创建一个[最小，完整和可验证示例]（http://stackoverflow.com/help/mcve）。 – pzaenger

我认为你不应该覆盖（中断）item当visited[i]==0。

此外，初始化和DFS的范围不同。

还有一些更正。

void dfs() 
{ 
    int i; 
    for(i=1;i<=nodecount;i++) 
    { 
     visited[i]=0; 
    } 
    visited[item]=1; /* add this to mark the start point as visited */ 
    push(item); 
    while(top!=0) 
    { 
     pop(); 
     /* delete visited[item]=1; here */ 
     for(i=1;i<=nodecount;i++) /* changed < to <= */ 
     { 
      if(topo[item][i]==1) 
      { 
       if(visited[i]==0) 
       { 
        visited[i]=1; /* item is unchanged unless push change it */ 
        push(i); 
       } 
      } 
     } 
    } 
}

不知道，我相信push和pop做适当的工作，item和top，并有在visited足够的元素。

在push情况下，假定item将作为参数传递，试试这个来代替：

void dfs() 
{ 
    int i; 
    for(i=1;i<=nodecount;i++) 
    { 
     visited[i]=0; 
    } 
    visited[item]=1; /* add this to mark the start point as visited */ 
    push(item); 
    while(top!=0) 
    { 
     pop(); 
     /* delete visited[item]=1; here */ 
     for(i=1;i<=nodecount;i++) /* changed < to <= */ 
     { 
      if(topo[item][i]==1) 
      { 
       if(visited[i]==0) 
       { 
        int item_bak = item; 
        item = i; 
        visited[item]=1; 
        push(item); 
        item = item_bak; 
       } 
      } 
     } 
    } 
}

来源

2015-10-14 14:45:12 MikeCAT

。错过了。如果我不更改项目，那么同一个节点将被一次又一次地推入堆栈。不是吗？ – user24603

@ user24603对不起，'我'应该用来代替'item'。编辑。 – MikeCAT

我尝试了你建议的新编辑。它仍然不会按我想要的方式工作。仍然获得与原始代码相同的输出。 – user24603

什么应该是一个递归函数？

void dfs(int item) { 
    int i; 
    push(item); 
    visited[item] = 1; 
    pstack(); 

    for(i=1; i<nodecount; i++) { 
    if ((nodes[item][i] == 1) && (visited[i] == 0)) { 
     dfs(i); 
     visited[i] = 0; 
    } 
    } 
    pop(); 
}

这里的pstack（）是打印堆栈内容的功能，而这个功能必须与网页[] inited 0 使用相同的graphe比你叫我得到：

. 2 
. 2 1 
. 2 1 4 
. 2 1 4 5 
. 2 1 4 5 3 
. 2 3 
. 2 3 5 
. 2 3 5 4 
. 2 3 5 4 1 
. 2 4 
. 2 4 1 
. 2 4 5 
. 2 4 5 3

我使'item'成为函数的一个参数。注意：以1开始计数并不是真正意识到的:)

来源

2015-10-14 15:38:16 hexasoft

DFS找到所有可能的路径 - 我哪里错了？

回答

相关问题