(20 pts.) Topological Sort. Run the DFS-based topological ordering algorithm on the following graph. Whenever you...

Transcribed Image Text:

(20 pts.) Topological Sort. Run the DFS-based topological ordering algorithm on the following graph. Whenever you have a choice of vertices to explore, always pick the one that is alphabetically first. A B C D E F G (c) What topological ordering is found by the algorithm? (d) How many topological orderings does this graph have? Why? H (a) Indicate the pre and post numbers of the nodes. Please put your answers in the format of "A : 1,2" for each vertex, with 1 as A's pre number you found and 2 as A's post number. Note this is only an example for the illustrative purpose that has nothing to do with the correct solution. (b) What are the sources and sinks of the graphs? Please put your answers in the format of "Sources: ...; Sinks: ...". (20 pts.) Topological Sort. Run the DFS-based topological ordering algorithm on the following graph. Whenever you have a choice of vertices to explore, always pick the one that is alphabetically first. A B C D E F G (c) What topological ordering is found by the algorithm? (d) How many topological orderings does this graph have? Why? H (a) Indicate the pre and post numbers of the nodes. Please put your answers in the format of "A : 1,2" for each vertex, with 1 as A's pre number you found and 2 as A's post number. Note this is only an example for the illustrative purpose that has nothing to do with the correct solution. (b) What are the sources and sinks of the graphs? Please put your answers in the format of "Sources: ...; Sinks: ...".

Answer rating: 100% (QA)

To find the topological ordering of the given graph using the DFSbased algorithm we star... View the full answer