I have written this code for DFS traversal of graph represented using adjacency list in C. It is based on algorithm given in Cormen. The issue with this code is the while loop within "dfs_visit" function which is not executing at all. I don't see why. Please let me know why. It is probably sufficient to just go through the dfs and dfs_visit functions but just in case you needed to go through other functions, I included all of them.

//color : '-1' for white; '0' for grey; '1' for black //white: unvisited; grey: discovered but not added yet; black: visited

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

    int time;

    struct AdjListNode
    {
        int dest;
        int color;
        int par;//parent
        int dt;//discovered time
        int ft;//finished time
        struct AdjListNode *next;
    };

    struct AdjList
    {
        struct AdjListNode *head;
    };

    struct Graph
    {
        int V;
        struct AdjList *array;
    };
    
    struct AdjListNode *addNewNode(int dest);
    void DFS_visit(struct Graph* graph,struct AdjListNode *u);
    struct Graph *createGraph(int V);
    void addEdge(struct Graph *graph, int src, int dest);
    void printGraph(struct Graph *graph);
    void printDFS(struct Graph* graph);

    struct AdjListNode *addNewNode(int dest)
    {
        struct AdjListNode *newNode = (struct AdjListNode *)malloc(sizeof(struct AdjListNode));
        newNode->dest = dest;
        newNode->dt = newNode->ft = 0;
        newNode->par = 0;
        newNode->next = NULL;
        return newNode;
    }
    
    struct Graph *createGraph(int V)
    {
        struct Graph *graph = (struct Graph *)malloc(V * (sizeof(struct Graph)));
        graph->array = (struct AdjList*)malloc(V*sizeof(struct AdjList));
        graph->V = V;
        for (int i = 0; i < V; i  )
        {
            graph->array[i].head = addNewNode(i);
        }
        return graph;
    }

    void addEdge(struct Graph *graph, int src, int dest)
    {
        struct AdjListNode *newNode = addNewNode(dest);
        // simply adding the node at the beginning
        newNode->next = graph->array[src].head->next;
        graph->array[src].head->next = newNode;
        // for undirected graph
        newNode = addNewNode(src);
        newNode->next = graph->array[dest].head->next;
        graph->array[dest].head->next = newNode;
    }


    void DFS(struct Graph* graph){
        for(int i=0;i<graph->V;i  ){
            graph->array[i].head->color = -1;
            graph->array[i].head->par = 0;
        }
        time = 0;
        for(int i=0;i<graph->V;i  ){
            if(graph->array[i].head->color == -1){
                DFS_visit(graph,graph->array[i].head);
            }
        }
    }

    void DFS_visit(struct Graph* graph,struct AdjListNode *u){
        u->color = 0;
        u->dt =   time;
        printf("%d ",u->dest);
        struct AdjListNode* temp = u->next;
        while(temp!=NULL){
            if(temp->color == -1){
                temp->par = u->dest;
                DFS_visit(graph,graph->array[temp->dest].head);
            }
            temp = temp->next;
        }
        u->color = 1;
        u->ft =   time;
    }

    void printGraph(struct Graph *graph)
    {
        for (int v = 0; v < graph->V; v  )
        {
            struct AdjListNode *temp = graph->array[v].head;
            printf("\nthe adj list of vertex %d is : head", v);
            while (temp)
            {
                printf("-> %d", temp->dest);
                temp = temp->next;
            }
            printf("\n"); 
        }
    }

    void printDFS(struct Graph* graph){
        printf("\n");
        for(int v=0;v<graph->V;v  ){
            printf("\nvertex %d has dt = %d & ft = %d",v,graph->array[v].head->dt,graph->array[v].head->ft);
        }
    }

    int main()
    {
        int V;
        printf("enter # of vertices: ");
        scanf("%d",&V);
        struct Graph *graph = createGraph(V);
    
        addEdge(graph,0,1);
        addEdge(graph,1,2);
        addEdge(graph,1,3);
        addEdge(graph,2,3);
        addEdge(graph,2,4);
        addEdge(graph,4,0);

        printGraph(graph);
        printf("\nDFS of given graph is: ");
        DFS(graph);
        printDFS(graph);
        return 0;
    }

OUTPUT for printGraph is as below and it is right.
adjacency list of vertex 0 : 0->4->1->null
adjacency list of vertex 1 : 1->3->2->0->null
adjacency list of vertex 2 : 2->4->3->1->null
adjacency list of vertex 3 : 3->2->1->null
adjacency list of vertex 4 : 4->0->2->null

Important Note : I have added node with data = vertex at the beginning of each vertex's adjacency list and made it the head of the list.

It's giving 0 1 2 3 4 as output but that is wrong. The right output is 0 4 2 3 1. Clearly, as I mentioned earlier, the while loop of "dfs_visit" is not executing. Please let me know the changes I have to make this code work. There is no issue with the 'printing of graph'. The adjacency lists are being printed correctly.

the Output it's giving for dfs is:
vertex 0 has dt = 1 and ft = 2
vertex 1 has dt = 3 and ft = 4
vertex 2 has dt = 5 and ft = 6
vertex 3 has dt = 7 and ft = 8
vertex 4 has dt = 9 and ft = 10
clearly, this is wrong output and it is as if the while loop of dfs_visit is not executing at all. But, I'm not understanding why it is not.

Any suggestions you have to optimise the code are welcome

CodePudding user response：

Your addEdge calls addNewNode twice, whether or not the edge connects new nodes.

After this

    addEdge(graph,0,1);
    addEdge(graph,1,2);

the graph will have two copies of node 1.