A Topological Sort is defined as a linear ordering of all vertices in directed acyclic graph (DAG). A directed acyclic graph is defined as a graph in which all the vertices are connected through directed edges and the graph does not contain any cycles in it. The linear ordering of the vertices in topological sort is such that for every pair of vertices (u, v), where the edge moves from u to v, implies that u occurs before v.
There can be many possible ordering formed in the graph using topological sort. Hence, there is no one such unique ordering present. The condition for topological sort to exist is that the graph should be acyclic, it should contain any cycles in it.
The given graph for which topological ordering is to be found is given below:
The solution obtained is not unique. More than one topological ordering is present for the above shown graph.
One such topological ordering possible is: s, G, D, H, A, B, E, I, F, C, and t.
Initially, start from the vertex whose indegree is zero. Thus, start with vertex s. From s any vertex can be chosen next, according to weight, the next vertex opted is G. from G, the next vertex in the linear ordering chosen is d, then, H. similarly, moving further in linear ordering the other vertices are chosen and lastly, the vertex t is reached.
It should be noted that the topological ordering thus mentioned is not the unique ordering obtained. There are many other possible orders that can be hence obtained following a different linear order.
Chegg is one of the leading providers of homework help for college and high school students. Get homework help and answers to your toughest questions in math, calculus, algebra, physics, chemistry, science, accounting, English and more. Master your homework assignments with our step-by-step solutions to more than 3000 textbooks. If we don't support your textbook, don't worry! You can ask a homework question and get an answer in as little as two hours. With Chegg, homework help is just a few clicks away.