topological sort using queue in a graph

Question

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:

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:

Also, there are no trace of the definitions of struct queue, struct Graph, createqueue(), dequeue(), enqueue() and indegree... — Ruks
– Ruks, Commented Nov 8, 2018 at 6:14
Plus that code's not even valid... for each w to ...? If you're just using psuedocode, why is this tagged C? — Shawn
– Shawn, Commented Nov 8, 2018 at 6:29
The provided algorithm is C-like psuedo code, you need to implement it in whatever language you choose such as C. — lod
– lod, Commented Nov 8, 2018 at 6:29
Punctuation is very important. It is also important to remember that we owe you nothing. Your tone seems to imply otherwise. — Mad Physicist
– Mad Physicist, Commented Nov 8, 2018 at 6:50
While this is a reasonable question, it is fundamentally just a typo - a simple transcription mistake when going from text into code. This would make the question off topic. Perhaps it should be left as-is, since the textbook it refers to is popular, and more than one person may be thrown off by it. Please include the author and title of the textbook in the question itself, so that people would have easier time if they search for this problem. — Kuba hasn't forgotten Monica
– Kuba hasn't forgotten Monica, Commented Nov 9, 2018 at 18:00

nightfury1204 · Accepted Answer · 2018-11-08 06:47:09Z

5

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.

edited Nov 8, 2018 at 6:47

answered Nov 8, 2018 at 6:31

nightfury1204

4,70422 silver badges23 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

Ruks Over a year ago

In the book, they removed the trailing brackets for the for-loop and the OP mistook the curly bracket of the while loop with the for-loop... Thus, signifying one of the major importance of having curly brackets to start a code block...

nightfury1204 Over a year ago

@Ruks you are right. I have to face problem for that many times.

newby Over a year ago

See initially you for loop will going to insert 7 5 3 in the queue after that you will come to while loop an d till now you are having 7 5 3 inside queue now you will dequeue one by one from the queue and for the further enqueue THIS statement has to be executed if(--indegree[w]==0) for this to be executed we must have a vertex adjacent 7 or 5 or 3 with indegree 1 can you tell which vertex out of 11 8 10 that are adjacent to 7 5 3 have indegree 1 @nightfury1204

nightfury1204 Over a year ago

@newby i added curly braces does that clarify? And if(--indegree[w]==0) will be executed. Also if(--indegree[w]==0) means --indegree[w]; if(indegree[w]==0))

newby Over a year ago

here indegree of 11 8 and 10 are 2 or 1 ? well thanks for helping I am from india @nightfury1204

|

Collectives™ on Stack Overflow

topological sort using queue in a graph

1 Answer 1

8 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

8 Comments

Your Answer

Sign up or log in

Post as a guest

Related