3. Use the following graph for the questions on this page: If possible, list two

Question

3. Use the following graph for the questions on this page: If possible, list two valid topological orderings of the nodes in the graph above. If there is only one valid topological ordering, list that one ordering. If there is no valid topological ordering, state why one does not exist. a. b. What is the worst case big-O running time of topological sort for a graph represented as an adjacency list? (use V and E rather than N in your answer) No explanation is needed. c. This graph is: (Circle all that are true): directed weakly connected undirected complete acyclic strongly connected

Explanation / Answer

Hi,
a. Topological order for Directed Acyclic Graph (DAG) is a linear ordering of vertices such that for every directed edge uv, vertex u comes before v in the ordering.
In the graph there is a cycle between B C and E, that is, whichever order we choose, the third edge will lose the order of UV, since u should come before v in topological ordering

b. The worst case complexity of the topological sort is same as that of Depth first search of a graph where we traverse all the vertices depth wise and o/p them according the directed edges, hence its O(V+E)
c.
Directed graph: A directed graph is the one where there are specific directions between vertices, which is TRUE in this case
weakly/strongly connected:A directed graph is called strongly connected if there if every vertex is reachable from every other vertex otherwise its called weakly connected.
complete: A complete digraph is a directed graph in which every pair of distinct vertices is connected by a pair of unique edges (one in each direction) which is FALSE here since every pair is not connected with unique edges in both directions, here D is not reachable from E, hence its NOT strongly connected
acyclic: Acyclic graph is a graph which doesnt have a cycle, but we already established this graph has cycle, hence its CYCLIC
Thumbs up if this was helpful, otherwise let me know in comments

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.