Error implementing Depth first search

Question

I am trying to implement Depth first search in c, I have successfully built the program to make the adjacency list representation for a graph(with help). I understand the Pseudo code for Dfs in this manner

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)

I have built the code that compiles but there seems to be some logical inconsistencies with my code. Please help me out with DFS part. I have properly checked the rest of the code and it works fine without DFS however I have included the rest of the part anyway so as to make sure if the there was improper connection within the code.

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

I have here used examples for DFS where all vertices are connected . This is my code,please check out the void dfs function.

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

Depending on what you try to do with it, there are fast algorithms like A* (A-star) or variations of it to find if two nodes in the graph are connected. If it is for educational purposes only, the brute force depth first, of course is okay. If you plan to add this to a navigation system or alike, I advice to consider more efficient algorithms, though. — BitTickler
– BitTickler, Commented Jan 14, 2015 at 19:08
Thanks for the knowledge sir I had never heard of A* algorithm before , I would be very grateful if you provide me with the implemenation of A* with this code (replace it with DFs), or maybe some links to learn it better — Arafat Khan
– Arafat Khan, Commented Jan 14, 2015 at 19:21
What exactly is the problem? I see quite some issues in the code that you wrote, assuming you yourself only wrote dfs() and perhaps modified main(). "there seems to be some logical inconsistencies" is not a proper description of an error, at what point is the output not what you expected? — Ulrich Eckhardt
– Ulrich Eckhardt, Commented Jan 14, 2015 at 19:35

Arthur Laks · Accepted Answer · 2015-01-15 01:07:32Z

0

I cannot tell if this is the only problem with your code, but the visited array should not be declared on the stack. The way your code is now, there is a separate visited array for each recursive call of your function.

Instead, you should make it a pointer to an array on the heap. In order to implement this solution, you should expect your recursive function to be called by a nonrecursive wrapper function that allocates a buffer from the heap, passes a pointer to that buffer to the recursive function, and deallocates that memory when the recursive function returns.

If you use this implementation, you would have a bfs function that takes all of the parameters that your existing function takes, and rename your existing function to bsf_recursive, and add an int pointer to its parameter list. The bfs function should allocate an array of integers from the heap, pass it to the bsf_recursive function, and then free up the memory of the array.

edited Jan 15, 2015 at 1:07

answered Jan 14, 2015 at 19:25

Arthur Laks

5244 silver badges8 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

abligh Over a year ago

Or declare it in a wrapper function on the stack and pass it in as a parameter.

BitTickler Over a year ago

Making it static does not change the fact that it won't work. v is not a constant but a parameter of that function. You cannot create "variable length" arrays like that.

Arthur Laks Over a year ago

@user2225104 Thank you for pointing that out. I guess that I will have to revise my answer.

BitTickler · Accepted Answer · 2015-01-14 22:07:29Z

Aside from some "showstoppers" like the aforementioned attempt to create an array with con-constant size, I felt readability of the code was lacking a bit, as well as some "best practices" to write code in C. So, instead of making the original code work, I freely "refactored" it until I felt it would reflect a more readable and more instructive implementation.

The main differences of my implementation are, that the Nodes need not store the Id. Instead, all nodes are stored in an array within the Graph structure and the index within that array is implicitely the id of the node.

Also, I built a wrapper function around the recursive depth first function, which takes care of proper allocation of the visited nodes flag array.

I kept the recursive form of the original code and added a tiny bit of "reuse" to the mix, by means of a visitor function, which is invoked during search.

By studying the code here, it should not be hard to make the right decisions to implement the DSF function in the original code.

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

Collectives™ on Stack Overflow

Error implementing Depth first search

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related