c - 实现深度优先搜索时出错

Question

我正在尝试在c中实现深度优先搜索，我已经成功构建了程序来为图制作邻接列表表示(在帮助下)。我以这种方式理解Dfs的伪代码

procedure DFS(G,v):
  label v as discovered
  for all edges from v to w in G.adjacentEdges(v) do
    if vertex w is not labeled as discovered then
      recursively call DFS(G,w)  

我已经构建了可以编译的代码，但似乎与我的代码存在一些逻辑不一致。请帮我解决 DFS 部分。我已经正确检查了代码的其余部分，并且在没有 DFS 的情况下它也可以正常工作，但是无论如何我都包含了其余部分，以确保代码中是否存在不正确的连接。

When I enter the input 
3
Enter the number of Edges
2
Enter the Edges
0 1
1 2
I get the output as just 
1

我在这里使用了所有顶点都连接的 DFS 示例。这是我的代码，请查看 void dfs 函数。

#include <stdlib.h>
#include <stdio.h>

struct grnode;
struct grconn;

struct grconn {                 /* Connection to node (linked list) */
    struct grnode *dest;
    struct grconn *next;
};

struct grnode {                 /* Node in graph */
    int id;
    struct grconn *conn;
};

struct graph {
    int nnode;
    struct grnode *node;
};


/*
*      Create new connection to given node
*/
struct grconn *grconn_new(struct grnode *nd)
{
    struct grconn *c = malloc(sizeof(*c));

    if (c) {
        c->dest = nd;
        c->next = NULL;
    }

    return c;
}

/*
*      Clean up linked list of connections
*/
void grconn_delete(struct grconn *c)
{ 
    while (c) {
        struct grconn *p = c->next;

        free(c);
        c = p;
    }
}

/*
*      Print connectivity list of a node
*/
void grnode_print(struct grnode *nd)
{
    struct grconn *c;

    printf("%d:", nd->id);

    c = nd->conn;
    while (c) {
        printf(" %d", c->dest->id);
        c = c->next;
    }

    printf("\n");
} 



 /*
 *      Create new graph with given number of nodes
 */
struct graph *graph_new(int n)
{
    struct graph *g = malloc(sizeof(*g));
    int i;

    if (g == NULL) return g;

    g->nnode = n;
    g->node = malloc(n * sizeof(*g->node));
    if (g->node == NULL) {
        free(g);
        return NULL;
    }

    for (i = 0; i < n; i++) {
        g->node[i].id = i;
        g->node[i].conn = NULL;
    }

    return g;
}

/*
*      Delete graph and all dependent data
*/
void graph_delete(struct graph *g)
{
    int i;

    for (i = 0; i < g->nnode; i++) {
        grconn_delete(g->node[i].conn);
    }

    free(g->node);
    free(g);
}

/*
*      Print connectivity of all nodes in graph
*/
void graph_print(struct graph *g)
{
    int i;

    for (i = 0; i < g->nnode; i++) {
        grnode_print(&g->node[i]);
    }
}

/*
*      Create one-way connection from node a to node b
*/
void graph_connect(struct graph *g, int a, int b)
{
    struct grnode *nd;
    struct grconn *c;

    if (a < 0 || a >= g->nnode) return;
    if (b < 0 || b >= g->nnode) return;

    nd = &g->node[a];
    c = grconn_new(&g->node[b]);

    c->next = nd->conn;
    nd->conn = c;
}

/*
*      Create two-way connection between nodes a and b
*/
void graph_connect_both(struct graph *g, int a, int b)
{
    graph_connect(g, a, b);
    graph_connect(g, b, a);
}
// The code above is for the functions for the adjacency list 
// so now we have an array of integers which keeps whether we have visited something
void dfs(struct graph *g,int u, int *b,int v,struct grnode *nd)
{
    int visited[v];
    struct grconn *c;
    visited[u]=1;
    c = nd->conn;printf("%d",c->dest->id);
    c=c->next;
    while(c)
    {
        printf("%d",c->dest->id);
        u=c->dest->id;
        dfs(g,u,b,v,&g->node[0]);
    }

}

// The code below is for the representation of something in the form of adjacency list 
int main()
{
    printf("Enter the number of Vertices\n");
    int i,n,d,x,y;
    scanf("%d",&n);
    struct graph *g = graph_new(n);int b[n];

    printf("Enter the number of Edges\n");
    scanf("%d",&d);
    printf("Enter the Edges\n");
    for(i=0;i<d;i++)
    {
        scanf("%d %d",&x,&y);
        graph_connect_both(g, x, y);
    }
    printf("\n");
    for(i=0;i<n;i++)b[i]=0;
    dfs(g,0, b,n,&g->node[0]);
    graph_delete(g);

    return 0;
}

Answer 1

我无法判断这是否是您的代码的唯一问题，但 visited 数组不应在堆栈上声明。按照您的代码现在的方式，函数的每个递归调用都有一个单独的访问数组。

相反，您应该将其设为指向堆上数组的指针。为了实现此解决方案，您应该期望递归函数由非递归包装函数调用，该函数从堆中分配缓冲区，将指向该缓冲区的指针传递给递归函数，并在递归函数返回时释放该内存。

如果您使用此实现，您将拥有一个 bfs 函数，该函数采用现有函数采用的所有参数，并将现有函数重命名为 bsf_recursive，并且添加一个 int 指针到它的参数列表。 bfs 函数应从堆中分配一个整数数组，将其传递给 bsf_recursive 函数，然后释放该数组的内存。