DFS traversal in directed graph in C

Question

I am trying to print a graph traversal with starting vertex 0 which covers all the nodes and "directed from" vertices should be visited before "directed to". I explained my question below with expected output. Here is the code,

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

typedef struct node
{
    struct node *next;
    int vertex;
}node;

node *G[20];   
//heads of linked list
int visited[20];
int n;
void read_graph(); 
//create adjacency list
void insert(int,int);  
//insert an edge (vi,vj) in te adjacency list
void DFS(int);

void main()
{
    int i;
    read_graph();
    //initialised visited to 0

    for(i=0;i<n;i++)
        visited[i]=0;

    DFS(0);
}

void DFS(int i)
{
    node *p;

    printf("\n%d",i);
    p=G[i];
    visited[i]=1;
    while(p!=NULL)
    {
       i=p->vertex;

       if(!visited[i])
            DFS(i);
        p=p->next;
    }
}

void read_graph()
{
    int i,vi,vj,no_of_edges;
    printf("Enter number of vertices:");

    scanf("%d",&n);

    //initialise G[] with a null

    for(i=0;i<n;i++)
    {
        G[i]=NULL;
        //read edges and insert them in G[]

        printf("Enter number of edges:");
           scanf("%d",&no_of_edges);

           for(i=0;i<no_of_edges;i++)
        {
            printf("Enter an edge(u,v):");
            scanf("%d%d",&vi,&vj);
            insert(vi,vj);
        }
    }
}

void insert(int vi,int vj)
{
    node *p,*q;

    //acquire memory for the new node
    q=(node*)malloc(sizeof(node));
    q->vertex=vj;
    q->next=NULL;

    //insert the node in the linked list number vi
    if(G[vi]==NULL)
        G[vi]=q;
    else
    {
        //go to end of the linked list
        p=G[vi];

        while(p->next!=NULL)
            p=p->next;
        p->next=q;
    }
}

It is traversing all the nodes, Output :-

Enter the number of vertices : 6
Enter the number of edges : 6
Enter an edge (u, v) :- 0 1
Enter an edge (u, v) :- 1 2
Enter an edge (u, v) :- 0 4
Enter an edge (u, v) :- 4 5
Enter an edge (u, v) :- 2 3
Enter an edge (u, v) :- 5 3

It is giving output :- 0 1 2 3 4 5

But, if we look closely, (u, v) = (2, 3) and (u, v) = (5, 3) we are visiting 3 before 5. 5 also directed to 3. My expected output should be :- 0 4 5 1 2 3 where we are visiting each vertices and also visiting u before v

I only understand C and prefer solutions to be in C language.

Answer 1

A total order that maintains the edge relation is called a topological sort. You can get a topo sort with a DFS that visits all the vertices in post-order. But the post-order is the reverse of what you want.

Your code visits nodes in pre-order: It prints each node before visiting its children. So move the printf down to the point after the children have been searched.

The reverse of the printed order will have the property you want.

If you need to print the correct order, then, for example, you can push the nodes on a stack as you visit them. After the search is complete, pop and print until the stack is empty.