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

Question

我需要实现 DFS 来查找来自顶点的所有可能路径，例如“item”
到目前为止，我有以下内容，但我不明白我哪里出了问题。

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

使用这段代码，如果 item = 2 那么我应该得到

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

等等。

但是我得到

• 2
• 1
• 1-4
• 1-4-5
• 1-4
• 1-4-3
• 1

Answer 1

我认为当访问[i]==0时，您不应该覆盖(中断)item。

此外，初始化和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;
                }
            }
        }
    }
}