Consider a directed graph G = {V, E} with vertex set V = {A, B, C, D} and edge set E = {AB, AC, BC, BD, DC}. Which of the following is a valid topological ordering of graph G?

• The topological sorting for a directed acyclic graph is the linear ordering of vertices. For every edge U-V of a directed graph, the vertex u will come before vertex v in the ordering.
• The first vertex in topological sorting is always a vertex with in-degree as 0 (a vertex with no incoming edges.

Diagram

Therefore, the topological ordering of the given graph is ABDC

Topological sort can be performed in the time since depth-first search takes O(V + E)‚ time and it takes O(1) time to insert each of the |V| vertices onto the front of the linked list