6. In class we saw how to use DFS to compute a topological ordering of a...

Transcribed Image Text:

6. In class we saw how to use DFS to compute a topological ordering of a given graph G. Another approach is to choose source vertices from G one at a time (updating G after each choice by removing the node and its outgoing edges), and order them left to right. A source vertex is a vertex with no incoming edges in G. Describe why this algorithm gives a correct topological ordering, and show how to implement this approach in O(m + n) time. 6. In class we saw how to use DFS to compute a topological ordering of a given graph G. Another approach is to choose source vertices from G one at a time (updating G after each choice by removing the node and its outgoing edges), and order them left to right. A source vertex is a vertex with no incoming edges in G. Describe why this algorithm gives a correct topological ordering, and show how to implement this approach in O(m + n) time.

Answer rating: 100% (QA)

The described algorithm selects source vertices vertices with no incoming edges one at a time remove... View the full answer