Thread: DFS in C

  1. #1
    Registered User
    Join Date
    Mar 2022
    Posts
    2

    DFS in C

    Hi, I'm trying to implement DFS for graphs in C using an iterative process using the following algorithm:

    Code:
    Step 1: SET STATUS = 1 (ready state) for each node in G
    Step 2: Push the starting node A on the stack and set
    its STATUS = 2 (waiting state)
    Step 3: Repeat Steps 4 and 5 until STACK is empty
    Step 4:
    Pop the top node N. Process it and set its
    STATUS = 3 (processed state)
    Step 5:
    Push on the stack all the neighbours of N that
    are in the ready state (whose STATUS = 1) and
    set their STATUS = 2 (waiting state)
    [END OF LOOP]
    Step 6: EXIT
    The code I have developed for this is as follows:
    Code:
    #include <stdio.h>
    #define SIZE 10
    
    typedef struct
    {
        int element[SIZE];
        int top;
    }stack;
    
    void push(stack *s, int item)
    {
        if(s->top >= (SIZE - 1))
            return;
        s->element[++(s->top)] = item;
    }
    
    
    int pop(stack *s)
    {
        if(s->top <= -1)
            return -1;
        
        return s->element[(s->top)--];
    }
    
    void inputadjmat(int matrix[SIZE][SIZE], int n)
    {
        int i, j;
        printf("Enter elements of %dx%d adjacency matrix\n", n, n);
    
    
        for(i = 0; i < n; i++)
            for(j = 0; j < n; j++)
                scanf("%d", &matrix[i][j]);
    }
    
    void dfs(int adj[SIZE][SIZE], int start, int visited[], int n, stack* s)
    {
        int i;
        push(s, start);
        visited[start] = 1;
    
        while(s->top != -1)
        {
            int node = pop(s);
            printf("%d\t", node);
    
            // for(i = n; i >= 0; i--)
            for(i = 0; i < n; i++)
            {
                if(adj[node][i] == 1 && visited[i] == 0)
                {
                    push(s, i);
                    visited[i] = 1;
                }
            }
    
    
        }
        printf("\n");
    }
    
    
    
    
    void main()
    {
        stack s;
        int adj[SIZE][SIZE], visited[SIZE], n, start;
        s.top = -1;
    
        printf("Enter no. of vertices\n");
        scanf("%d", &n);
        inputadjmat(adj, n);
    
        printf("Enter starting vertex\n");
        scanf("%d", &start);
        dfs(adj, start, visited, n, &s);   
    }
    The iterative approach seems to yield a different result when compared to the recursive approach, even if I change the direction of traversing the array. I did refer a few books which trace the algorithm and this does seem to be correct I guess.
    Can anyone see if it's correct or am I missing something?
    Thanks

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,407
    Perhaps it would be easier if you provided your implementation of the recursive approach too, as well as your test input data that demonstrates the different result.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    Mar 2022
    Posts
    2
    Quote Originally Posted by laserlight View Post
    Perhaps it would be easier if you provided your implementation of the recursive approach too, as well as your test input data that demonstrates the different result.
    My recursive approach is as follows:

    Code:
    DFS-recursive(G, s):
            mark s as visited
            for all neighbours w of s in Graph G:
                if w is not visited:
                    DFS-recursive(G, w)
    Code:
    void dfs1(int i, int visited[], int adj[SIZE][SIZE], int n)
    {
        printf("%d", i);
        visited[i] = 1;
        for(int j = 0; j < n; j++)
        {
            if(adj[i][j] == 1 && !visited[j])
            dfs1(j, visited, adj, n);
        }
    }
    Input Adjacency Matrix is
    Code:
    0 1 1 1 0 0 0
    1 0 1 0 0 0 0
    1 1 0 1 1 0 0
    1 0 1 0 1 0 0
    0 0 1 1 0 1 1
    0 0 0 0 1 0 0
    0 0 0 0 1 0 0
    Starting vertex as 1 yields different results.

    I realise why it yields different results and also the fact that the way you traverse the adjacency matrix also matters so different valid traversals are possible.
    In the recursive approach, only one unvisited neighbour of a vertex is pushed onto the stack at a time but in the iterative version all unvisited neighbours are pushed onto the stack. It's just that the recursive version seems to be the most popular version in most online guides and I'm unsure as to if my approach gives another valid traversal or is just incorrect in some way.
    Last edited by codetest12; 03-11-2022 at 04:24 AM.

Popular pages Recent additions subscribe to a feed

Tags for this Thread