Ошибка при выполнении поиска в глубину

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;
}

0

c graph depth-first-search adjacency-list

Источник

user4452643 14 янв '15 в 18:57

2 ответа

Решение

Помимо некоторых "показов", таких как вышеупомянутая попытка создать массив с постоянным размером, я чувствовал, что читаемости кода немного не хватает, а также некоторые "лучшие практики" для написания кода на C. Итак, вместо того, чтобы делать исходный код работал, я свободно "рефакторинг" его, пока я не почувствовал, что он будет отражать более удобочитаемую и более поучительную реализацию.

Основные отличия моей реализации в том, что узлам не нужно хранить идентификатор. Вместо этого все узлы хранятся в массиве в структуре Graph, и индекс в этом массиве косвенно является идентификатором узла.

Кроме того, я построил функцию-обертку вокруг первой функции рекурсивной глубины, которая заботится о правильном размещении массива флагов посещенных узлов.

Я сохранил рекурсивную форму исходного кода и добавил немного "повторного использования" в микс с помощью функции посетителя, которая вызывается во время поиска.

Изучая код здесь, не должно быть трудно принять правильные решения для реализации функции 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;
}

0

Источник

user2225104 14 янв '15 в 22:07

Другие вопросы по тегам c graph depth-first-search adjacency-list

user1925789 14 янв '15 в 19:25 2015-01-14 19:25 · Accepted Answer · 2015-01-14 19:25

Я не могу сказать, если это единственная проблема с вашим кодом, но visited массив не должен быть объявлен в стеке. То, как ваш код теперь, есть отдельный массив для каждого рекурсивного вызова вашей функции.

Вместо этого вы должны сделать это указателем на массив в куче. Чтобы реализовать это решение, вы должны ожидать, что ваша рекурсивная функция будет вызываться нерекурсивной функцией-оберткой, которая выделяет буфер из кучи, передает указатель на этот буфер рекурсивной функции и освобождает эту память при возврате рекурсивной функции.

Если вы используете эту реализацию, у вас будет bfs функция, которая принимает все параметры, которые принимает существующая функция, и переименовывает существующую функцию в bsf_recursiveи добавьте указатель int в свой список параметров. bfs функция должна выделить массив целых чисел из кучи, передать его bsf_recursive функции, а затем освободить память массива.