CODEWITHSUNDEEP
topological-sort
M. Stephens
M. Stephens

Reputation: 59

Topological sort order of graph

I am having a hard time figuring out the ordering found after topological soft of this given graph. if anyone could explain to me I would appreciate it! Click here to see the graph

Upvotes: 0

Views: 1086

Answers (1)

Brandon Hass
Brandon Hass

Reputation: 41

In order to do a topological sort, you run a depth-first search on the graph. Note: for this to work, it must be a Directed Acyclic Graph. This graph is directed (edges go one-way) and acyclic (there are no cycles), so topological sort works here. You can start at any node that has no incoming edges, and then once you complete a node (that is, you've already visited all of the node's children), you add it to the front of your topological ordering. Note: There can be multiple topological orderings for a DAG.

Here, A is the only node with no incoming edges. Let's run our DFS where, when given a choice between children, we pick the one that comes first in the alphabet.

A goes to B, which goes to C, then D, then G, then F. F has no children, so that is finished and will be the last thing in our topological ordering. We go back up to G, which takes us to H, which also has no children, so we put it before F in the ordering. From here, we continue the DFS until the ordering is complete.

I won't solve it fully for you, but I hope you can see how to complete the ordering.

Upvotes: 1

Related Questions