topological sort using queue in a graph

This Algorithm is of topological sort using queue written in my Text bookif in the given graph initially 7 5 3 has in-degree zero then they will be inserted in the queue but for any of the vertices adjacent to <code>7 5 3</code> we are not having any vertex with degree 1 This imply <code>if(--indegree[w]==0)</code> will not hold true for <code>7 5 3</code> hence there will be no further enqueue inside queue hence algorithm will not process further vertices and graph is also DAG then i want to ask why this algorithm is failing I am adding this image as a part  of proof that my algorithm is correct and taken from famous indian writer's textbook

Can anyone tell me why my algorithm is failing if this algorithm is partially incorrect if you think then Please make the required changes and I know that we can also implement topological sort using DFS ,but i want to implement the below algorithm

void topologicalsort(struct Graph* G){
    struct queue* Q;
    int counter;
    int v,w;
    Q=createqueue();
    counter=0;
    for(v=0;v<G->V;v++){
       if(indegree[v]==0)
          enqueue(Q,v);
       while(!isemptyqueue(Q)){
          v=dequeue(Q);
          topologicalorder[v]=++counter;
          for each w to adjacent to v
             if(--indegree[w]==0){
             enqueue(Q,w);
             }


       }
    } 
} 

if in the given graph initially 7 5 3 has in-degree zero then they will be inserted in the queue but for any of the vertices adjacent to 7 5 3 we are not having any vertex with degree 1 This imply if(--indegree[w]==0) will not hold true for 7 5 3 hence there will be no further enqueue inside queue hence algorithm will not process further vertices and graph is also DAG then i want to ask why this algorithm is failing Note-> Algorithm is failing for above graph

1 answer

  • answered 2018-11-08 06:31 nightfury1204

    Your algorithm implementation is incorrect. Here while(!isemptyqueue(Q)) isn't under the for(v=0;v<G->V;v++) (See the indentation in the algorithm). See below for more clarification:

    void topologicalsort(struct Graph* G){
        struct queue* Q;
        int counter;
        int v,w;
        Q=createqueue();
        counter=0;
        for(v=0;v<G->V;v++){
           if(indegree[v]==0)
              enqueue(Q,v);
        }
    
        while(!isemptyqueue(Q)){
             v=dequeue(Q);
             topologicalorder[v]=++counter;
             for each w to adjacent to v {
                 if(--indegree[w]==0){
                     enqueue(Q,w);
                 }
             }
        }
    }
    

    This will work for every DAG.