Depth-First Search in Graphs - The topological order
(Page 4 of 4 )
The topological sorting is all about constructing an order of the vertexes which will make sure that, by drawing the vertexes from left to right, all of the edges will be directed in the right direction. Now from this we can conclude that this kind of order is possible only out of a directed and circle-free graph.
This order is in fact the inverse order of the DFS tree, or in other words the inverse order of how the vertexes become black. What assures that this will be correct ? Whenever we step forward from a node and mark it as visited fully (painted black), all of its children are already visited; otherwise, we would not leave that point.
Therefore, if we insert it now inside the list, all of the vertexes that stand at the other end of the out-going edges are already visited, and are on the left side of this item in the DFS order. From this we conclude that, in the inverse of this order, they will be on the right side.
In code snippet terms, we only need to add a couple of lines after we mark an item as black (fully visited). We use a global variable to count the number of already-inserted items into the order; nevertheless, we could also inverse the order after the search:
// add to the topological order
++atPos;
topological_order[n-atPos] = vertex;
-->Image Courtesy of Kátai Zoltán- Introduction to Graphs<--
The execution of the application will print for us similar result to the upper image:
1 4 3 6 10 9 11 14 18 17 13 16 22 21 12 15 20 19 2 5 8 7
For all this and something extra, I've provided a little C file you can study. Inside it you will find the solution for the determination of the strong connecting components, the base circle system and the articulation edges and vertexes as a bonus to what we've learned so far.
If you do not understand any of this, do not worry, as we will look over those items in detail during the next couple of articles related to graphs. Feel free to explore them until next time, when I will be back for another lesson on graphs.
Thank you for investing the time to read my article and taking the effort to improve yourself. I want to encourage you to rate my article accordingly and to post your ideas and questions related to your experience with graphs here on the blog, or over on our friendly forum running under the name of DevHardware. Until next time, remember to Live With Passion!
| DISCLAIMER: The content provided in this article is not warranted or guaranteed by Developer Shed, Inc. The content provided is intended for entertainment and/or educational purposes in order to introduce to the reader key ideas, concepts, and/or product reviews. As such it is incumbent upon the reader to employ real-world tactics for security and implementation of best practices. We are not liable for any negative consequences that may result from implementing any information covered in our articles or tutorials. If this is a hardware review, it is not recommended to open and/or modify your hardware. |
/ 5 
