Implementing a Graph DFS

Question

I am trying to implement a graph and perform DFS in C. but the dfs operation causes the bug that w gets allocated a random value once the pointer x runs off the queue of adjacent nodes. The condition !=NULL doesnt seem to do anything. I want it to break as soon as the queue empties, how to achieve this?

Also I wanted to know, how to implement a runtime version of the number of nodes? I believe that C does not support dynamic instance of arrays. Should I declare a very large array and use that?

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

struct node {
    int data;
    struct node* next;
};

void add(struct node **bag, int data) {
    struct node *newnode = malloc(sizeof(struct node));
    newnode->data = data;
    newnode->next = *bag;
    *bag = newnode;
}

int V;
struct node *adj[7];
bool marked[7];
int edgeTo[7 * 6];

void initialize() {
    int i = 0;
    for (i = 0; i < 7; ++i) {
        adj[i] = malloc(sizeof(struct node));
        marked[i] = false;
    }
}

void addEdge(int v, int w) {
    add(&adj[v], w);
    add(&adj[w], v);
}

void dfs(int v) {
    printf("%d  ", v);
    marked[v] = true;
    struct node *x = adj[v];
    while (x != NULL) {
        int w = x->data;
        if (marked[w] == false) {
            dfs(w);
        }
        x = x->next;
    }
}

int main(int argc, char **argv) {

    initialize();
    addEdge(0, 1);
    addEdge(0, 2);
    addEdge(0, 5);
    addEdge(1, 4);
    addEdge(3, 2);
    addEdge(3, 4);
    addEdge(3, 5);
    addEdge(3, 6);
    addEdge(5, 2);
    addEdge(6, 0);
    addEdge(6, 4);
    dfs(0);

    printf("done");
    return 0;
}

Why are you allocating memory twice? Do not allocate memory for adj.And also remeber to free it after you allocate — 0xF1
– 0xF1, Commented Dec 31, 2013 at 7:31
If you are new to C, you should study some more about memory management before writing(or copy-pasting from elsewhere) code like this. And for dynamic array, also check linked list in C. — moeCake
– moeCake, Commented Dec 31, 2013 at 7:43
Please explain what is the expected output and what is the result you're getting. — Uchia Itachi
– Uchia Itachi, Commented Dec 31, 2013 at 7:44
When I run this I get: 0 6 4 3 5 2 1 done Is this not what you want? — woolstar
– woolstar, Commented Dec 31, 2013 at 7:44

Digital_Reality · Accepted Answer · 2013-12-31 07:44:59Z

3

You haven't coded your initialize method correctly. Make sure you initialize your next to null adj[i]->next = NULL;

void initialize() {
    int i = 0;
    for (i = 0; i < 7; ++i) {
        adj[i] = (node*)malloc(sizeof(struct node));
        marked[i] = false;
        adj[i]->data = 0;
        adj[i]->next = NULL;
    }
}

answered Dec 31, 2013 at 7:44

Digital_Reality

4,8081 gold badge34 silver badges32 bronze badges

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

Collectives™ on Stack Overflow

Implementing a Graph DFS

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related