Question

3. Apply Topological sort algorithm on the following graph. Then, draw the sorted graph. 11 marvel

0 0
Add a comment Improve this question Transcribed image text
Answer #1

Topological Sort using DFS :-

  Visited set. Set Sorted 3 * 5 7 11 10 2 2

Step 1: Select any node from which you want to start. So, suppose if I select 11.

Step2: Then we enter 11 into the visited set. Now, treverse all the nodes which can be reached from 11.

Step 3: From 11, I can reach 2. So, put 2 in the visited node. Now, from 2 can I reach any further node? No. So pop the node 2 and put it into a shorted set.

Step 4: Come back to 11, we again check from 11 which node can we reach i.e., 9 So, put it into a visited set & 9 has no further node. So we pop the node 9 and put it into a sorted set.  

Step 5: Repeat step 4. In this we get node 10 in the sorted set.

Step 6: Come back to 11 & check Is there any further node which can be visted from 11? The answer is No. So, we pop the node 11 and put it into a sorted set.

Step 7: Now I have to select one more node. So, suppose I select the node 7. So put it into the visted set & the check the node which can be reach from the node 7. From 7 we can reach 11 & 8 but we already visited the node 11 so we direct visit the node 8.

Step 8: Put the 8 into the visited set & then pop it and put it into the sorted set.

Step 9: Now I select one more node from 5 or 3. So suppose I select 5 so put it into visited set & from this all the node are already visited so we pop it & put it into a sorted set.

Step 10: Similarly the step 9, node 3 also has all visited node so we directly pop from the visited node & put it into a sorted node.

So, the final sorted set is 3,5,7,8,11,10,9,2

And the sorted graph will be:

Add a comment
Know the answer?
Add Answer to:
3. Apply Topological sort algorithm on the following graph. Then, draw the sorted graph. 11 marvel
Your Answer:

Post as a guest

Your Name:

What's your source?

Earn Coins

Coins can be redeemed for fabulous gifts.

Not the answer you're looking for? Ask your own homework help question. Our experts will answer your question WITHIN MINUTES for Free.
Similar Homework Help Questions
ADVERTISEMENT
Free Homework Help App
Download From Google Play
Scan Your Homework
to Get Instant Free Answers
Need Online Homework Help?
Ask a Question
Get Answers For Free
Most questions answered within 3 hours.
ADVERTISEMENT
ADVERTISEMENT
ADVERTISEMENT