Why is the traversal not getting printed?

Question

I wrote a code for depth first search in C using linked list. I have used stack implementation using linked list in it.

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

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

struct node *head = NULL;

struct edge {
    char data;
    struct edge *next;
};

struct vertex {
    char data;
    struct vertex *next;
    struct edge *enext;
};

void push(char item);
char pop();
bool isEmpty(struct node *head);
void printGraph(struct vertex *v);

int n; //no of vertices
char d; 

int main(void) 
{
    struct vertex *v = NULL;
    printf("Enter the no. of vertices: ");
    scanf("%d", &n);
    char status[2][n];
    printf("Enter the vertices of the graph: \n");
    char c;

    //getting the vertices
    for (int i = 0; i < n; i++) 
    {
        scanf(" %c", &c);
        struct vertex *new = malloc(sizeof(struct vertex));
        new->data = c;
        new->next = v;
        v = new;
    }

    printf("Press $ to stop for the particular vertex\n");
    struct vertex *ptr = v;
    for (int i = 0; i < n; i++)
    {
        printf("Enter the vertices with which the vertex %c forms an edge: \n", ptr->data);
        ptr->enext = NULL;
        char input;

        while(1) 
        {
            scanf(" %c", &input);

            if (input == '$') 
            {
                break;
            }

            //adding vertices to the edge list of the particular vertex
            struct edge *new = malloc(sizeof(struct edge));
            new->data = input;
            new->next = ptr->enext;
            ptr->enext = new;
        }
        ptr = ptr->next;
    }
    //graph made
    printGraph(v);

    //dfs
    for (int i = 0; i < n; i++) 
    {
        status[1][i] = '1';
    }

    struct vertex *pointer = v;

    for(int i = 0; i < n; i++) 
    {
        status[0][i] = pointer->data;
        pointer = pointer->next;
    }

    d = v->data;
    // push(d);
    push(d);
    status[1][0] = '2';

    while(!isEmpty(head))
    {
        char temp = pop();
        printf("%c ", temp);

        // updating status of popped element
        for (int i = 0; i < n; i++)
        {
            if (status[0][i] == temp)
            {
                status[1][i] = '3';
                break;
            }
        }

        //to find the popped elements' neighbours
        struct vertex *ptr = v;
        for (int j = 0; j < n; j++)
        {
            if (temp == ptr->data)
            {
                struct edge *ptr1 = ptr->enext;
                while (ptr != NULL) 
                {
                    for(int i = 0; i < n; i++) 
                    {
                        if(ptr->data == status[0][i])
                        {
                            if (status[1][i] == '1')
                            {
                                d = status[0][i];
                                push(d);
                                status[1][i] = '2';
                                break;
                            }
                        }
                    }
                    ptr1 = ptr1->next;
                }
            }
            ptr = ptr->next;
        }
    }
}

void push(char item)
{
    //create new node
    struct node *newNode = malloc(sizeof(struct node));
    newNode->data = item;

    //make the new node point to the head node
    newNode->next = head;

    //make the new node as head node
    //so that head will always point the last inserted data
    head = newNode;
    printf("Item inserted.\n");
}

char pop()
{
    //temp is used to free the head node
    //struct node *temp;

    if(head == NULL)
        printf("UNDERFLOW: Stack is Empty\n");
    else
    {
        
        char deletedItem = head->data;

        //make the head node point to the next node.
        //logically removing the node
        head = head->next;
        return deletedItem;
    }
}

void printGraph(struct vertex *v)
{
    struct vertex *ptr = v;
    for (int i = 0; i < n; i++)
    {
        printf("%c ------> ", ptr->data);
        struct edge *ptr1 = ptr->enext;
        while (ptr1 != NULL)
        {
            printf("%c", ptr1->data);
            printf("-->");
            ptr1 = ptr1->next;
        }
        printf("NULL\n");
        ptr = ptr->next;
    }
}

bool isEmpty(struct node *head)
{
    if (head == NULL)
    {
        return true;
    }
    return false;
}

output:

Enter the no. of vertices: 2
Enter the vertices of the graph: 
b
a
Press $ to stop for the particular vertex
Enter the vertices with which the vertex a forms an edge:
b
$
Enter the vertices with which the vertex b forms an edge:
a
$
a ------> b-->NULL
b ------> a-->NULL
Item inserted.
a

why is the whole traversal not getting printed? I expected the output to be like: a b, but it's only 'a'. Is there any mistake after i am updating the status of the first element? Help

Answer 1

I find your graph DFS code for finding out the popped element's neighbours quite confusing. Aren't you already getting a segmentation fault in your code with the input you have shown.

You can try this simpler code instead, it will work for the input case you have given:

//to find the popped elements' neighbours
        struct vertex *ptr = v;

        while (ptr) {  // search popped element in list of vertices
            if (temp == ptr->data) break;
             ptr = ptr->next;
        }
        struct edge* edge_ptr = ptr->enext;

        while (edge_ptr) {
                for (int i = 0; i < n; i++)
                {
                    if (edge_ptr->data == status[0][i])
                    {
                        if (status[1][i] == '1') // not visited?
                        {
                            d = status[0][i];
                            push(d);
                            status[1][i] = '2'; //mark vertex pushed on stack?
                            break;
                        }
                    }
                }
                edge_ptr = edge_ptr->next;
        }

The changes above just navigate the edge adjacency list of a graph vertex and pushes the unvisited adjacent vertices onto the stack. I have tried with few inputs:

$ ./a.out
Enter the no. of vertices: 3
Enter the vertices of the graph:
a
b
c
Press $ to stop for the particular vertex
Enter the vertices with which the vertex c forms an edge:
b
$
Enter the vertices with which the vertex b forms an edge:
a
$
Enter the vertices with which the vertex a forms an edge:
b
c
$
c ------> b-->NULL
b ------> a-->NULL
a ------> c-->b-->NULL

Item inserted. c
Item inserted. b
Item inserted. a
$ ./a.out
Enter the no. of vertices: 2
Enter the vertices of the graph:
b
a
Press $ to stop for the particular vertex
Enter the vertices with which the vertex a forms an edge:
b
$
Enter the vertices with which the vertex b forms an edge:
a
$
a ------> b-->NULL
b ------> a-->NULL
Item inserted. a 
Item inserted. b

You can try with further input cases and check if it traverses as per the algorithm.