实施深度优先搜索时出错

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 数组不应在堆栈上声明。您的代码现在的方式是，函数的每个递归调用都有一个单独的访问数组。

相反，您应该使它成为指向堆上数组的指针。为了实现这个解决方案，你应该期望你的递归函数被一个非递归包装函数调用，该包装函数从堆中分配一个缓冲区，将指向该缓冲区的指针传递给递归函数，并在递归函数 returns。

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

Answer 2

除了一些 "showstoppers" ，比如前面提到的创建一个大小不变的数组的尝试，我觉得代码的可读性有点欠缺，还有一些 "best practices" 来编写代码在 C 中。因此，我没有让原始代码工作，而是自由 "refactored" 它直到我觉得它会反映出更具可读性和更具指导性的实现。

我的实现的主要区别在于，节点不需要存储 Id。相反，所有节点都存储在 Graph 结构中的数组中，并且该数组中的索引隐含地是节点的 id。

此外，我围绕递归深度优先函数构建了一个包装函数，它负责正确分配访问节点标志数组。

我保留了原始代码的递归形式，并通过在搜索期间调用的访问者函数添加了一点点 "reuse"。

通过研究这里的代码，应该不难做出正确的决定来实现原始代码中的DSF功能。

// GraphGames.cpp : Defines the entry point for the console application.
//
#define _CRT_SECURE_NO_WARNINGS
#include "stdafx.h"
#include <stdlib.h>
#include <stdio.h>
#include <stdint.h>
#include <assert.h>

// A GraphNode maintains a singly linked list of node ids, it is connected to, the connection_list.
typedef struct SizetListNode
{
    size_t nodeIndex;
    struct SizetListNode * next;
} SizetListNode_t, *SizetListNodePtr_t;

typedef struct GraphNode
{
    SizetListNodePtr_t connection_list_head;
} GraphNode_t, *GraphNodePtr_t;

// A graph consists of an array of nodes. The index within the node array is also the nodes "id", implicitely.
typedef struct Graph
{
    size_t node_array_length;
    GraphNode_t * node_array;
} Graph_t, *GraphPtr_t;

void SizetListCreate(SizetListNodePtr_t *list)
{
    (*list) = NULL;
}
void SizetListDelete(SizetListNodePtr_t *list)
{
    SizetListNodePtr_t current = *list;
    while (current != NULL)
    {
        SizetListNodePtr_t next = current->next;
        *list = next;
        free(current);
        current = next;
    }
    *list = NULL;
}
void SizetListAdd(SizetListNodePtr_t * list, size_t value)
{
    SizetListNodePtr_t newElement = (SizetListNodePtr_t)malloc(sizeof(SizetListNode_t));
    if (NULL != newElement)
    {
        newElement->nodeIndex = value;
        newElement->next = (*list);
        *list = newElement;
    }
}

// This function assumes, that the Graph_t passed in is not initialized.
void GraphCreate(GraphPtr_t graph, size_t nodeCount)
{
    graph->node_array_length = nodeCount;
    graph->node_array = (GraphNode_t *)malloc(nodeCount * sizeof(GraphNode_t));
    if (NULL != graph->node_array)
    {
        for (size_t i = 0; i < nodeCount; ++i)
        {
            SizetListCreate(&graph->node_array[i].connection_list_head);
        }
    }
    else 
    {   // out of memory. Make sure this graph is properly initialized as "empty".
        graph->node_array_length = 0;
    }
}

void GraphDestroy(GraphPtr_t graph)
{
    assert(NULL != graph);
    if (NULL != graph)
    {
        size_t nodeIndex;
        for (nodeIndex = 0; nodeIndex < graph->node_array_length; ++nodeIndex)
        {
            SizetListDelete(&graph->node_array[nodeIndex].connection_list_head);
        }
        free(graph->node_array);
        graph->node_array = NULL;
        graph->node_array_length = 0;
    }
}

void GraphConnectNodes(GraphPtr_t graph, size_t fromId, size_t toId)
{
    assert(NULL != graph); // would be mean to pass a NULL to use here!
    if (NULL != graph)
    {
        assert(fromId < graph->node_array_length);
        assert(toId < graph->node_array_length);
        assert(fromId != toId); // Not sure if we could live with nodes connected to themselves...

        SizetListAdd(&graph->node_array[fromId].connection_list_head, toId);
    }
}

void GraphConnectNodesTwoWay(GraphPtr_t graph, size_t nodeAId, size_t nodeBId)
{
    assert(NULL != graph);
    if (NULL != graph)
    {
        assert(nodeAId < graph->node_array_length);
        assert(nodeBId < graph->node_array_length);
        assert(nodeAId != nodeBId);

        SizetListAdd(&graph->node_array[nodeAId].connection_list_head, nodeBId);
        SizetListAdd(&graph->node_array[nodeBId].connection_list_head, nodeAId);
    }
}

void PrintNodeInfo(GraphPtr_t graph, size_t nodeId)
{
    assert(NULL != graph);
    if(NULL != graph)
    {
        assert(nodeId < graph->node_array_length);
        if ( nodeId < graph->node_array_length )
        {
            SizetListNodePtr_t iter = graph->node_array[nodeId].connection_list_head;
            printf("This node is connected to: ");
            while (NULL != iter)
            {
                printf("node #%d ", iter->nodeIndex);
                iter = iter->next;
            }
            printf("\n");
        }
        else
        {
            printf("Invalid node Id: %d\n", nodeId);
        }
    }
    else
    {
        printf("Not a valid graph!\n");
    }
}

void PrintGraph(GraphPtr_t graph)
{
    assert(NULL != graph);
    if (NULL != graph)
    {
        size_t nodeIndex;
        for (nodeIndex = 0; nodeIndex < graph->node_array_length; ++nodeIndex)
        {
            printf("Node %d: ", nodeIndex);
            PrintNodeInfo(graph, nodeIndex);
            printf("\n");
        }
    }
}

typedef void(*GraphNodeVisitor_t) (GraphPtr_t graph, size_t nodeId);

static size_t visitCounter = 0UL;

void PrintingAndCountingGraphNodeVisitor(GraphPtr_t graph, size_t nodeId)
{
    printf("Visiting node %d.", nodeId);
    PrintNodeInfo(graph, nodeId);
    visitCounter++;
}

void DepthFirstVisit(GraphPtr_t graph, uint8_t *visitedFlags, size_t nodeId, GraphNodeVisitor_t visitor)
{
    visitedFlags[nodeId] = 1;
    visitor(graph, nodeId);
    SizetListNodePtr_t currentEdge = graph->node_array[nodeId].connection_list_head;
    for (; NULL != currentEdge; currentEdge = currentEdge->next)
    {
        if (0 == visitedFlags[currentEdge->nodeIndex])
        {
            DepthFirstVisit(graph, visitedFlags, currentEdge->nodeIndex, visitor);
        }
    }
}

void VisitNodesDepthFirst(GraphPtr_t graph, size_t startingNodeId, GraphNodeVisitor_t visitor)
{
    assert(NULL != graph);
    if (NULL != graph)
    {
        assert(startingNodeId < graph->node_array_length);
        if (startingNodeId < graph->node_array_length)
        {
            uint8_t *visitedFlags = (uint8_t*)malloc(graph->node_array_length);
            if (NULL != visitedFlags)
            {
                for (size_t i = 0; i < graph->node_array_length; ++i)
                {
                    visitedFlags[i] = 0;
                }

                size_t currentNodeId = startingNodeId;
                visitedFlags[currentNodeId] = 1;
                visitor(graph, currentNodeId);

                SizetListNodePtr_t currentEdge = graph->node_array[currentNodeId].connection_list_head;
                for (; NULL != currentEdge; currentEdge = currentEdge->next)
                {
                    DepthFirstVisit(graph, visitedFlags, currentEdge->nodeIndex, visitor);
                }
            }
            free(visitedFlags);
        }
    }
}

int main(int argc, char* argv[])
{
    Graph_t myGraph;
    int x;
    int y;

    size_t vertexCount = 0;
    printf("Enter the number of Vertices\n");
    scanf("%d", &vertexCount);

    GraphCreate(&myGraph, vertexCount);

    size_t edgeCount = 0;
    printf("Enter the number of Edges\n");
    scanf("%d", &edgeCount);
    printf("Enter the Edges\n");
    for (size_t i = 0; i<edgeCount; i++)
    {
        scanf("%d %d", &x, &y);
        GraphConnectNodesTwoWay(&myGraph, x, y);
    }
    printf("\n");

    PrintGraph(&myGraph);
    visitCounter = 0;
    VisitNodesDepthFirst(&myGraph, 0, PrintingAndCountingGraphNodeVisitor);
    printf("%d nodes out of %d total nodes visited.\n", visitCounter, myGraph.node_array_length);

    GraphDestroy(&myGraph);
    return 0;
}

实施深度优先搜索时出错

Error implementing Depth first search

c

graph

adjacency-list

depth-first-search