CODEWITHSUNDEEP
calgorithmsortinggraph-theorydepth-first-search
newby
newby

Reputation: 189

topological sort using queue in a graph

The below is my reading of a topological sort algorithm on a queue, written in my textbook:

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);
             }


       }
    } 
}

The algorithm is failing for the following graph:

graph the algorithm fails on

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 implies that if(--indegree[w]==0) will not hold true for 7 5 3 hence there will be no further enqueuing inside the queue, and hence the algorithm will not process further vertices. I'd like to know why is the algorithm failing if the graph is a DAG? In which way is it incorrect?

I know that we can also implement topological sort using DFS, but I want to implement the below as-is:

the pseudocode of the algorithm I want to implement

Upvotes: 0

Views: 3939

Answers (1)

nightfury1204
nightfury1204

Reputation: 4654

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.

Upvotes: 5

Related Questions