Circles and Connectivity in Graphs - Strong connective components
(Page 3 of 4 )
Here is the solution: build the inverse order of the DFS search for the vertexes. Make an inverse of the direction (by reversing the direction of the edges). Call the DFS on the vertexes in the inverse DFS order of the vertexes on the inverse graph. Each call will show you another strong connective component of the graph.
Now we need to understand why this is a solution. You can agree that, within a graph inside a strong connective component, there can be only vertexes that are on a circle, as otherwise there would not be a road between one and any of the other vertexes. Therefore, the points that are not in any of the circles will create a strong connective sub-graph on their own.
In the last article, we learned that the topological sort would place the items into an order such that all edges coming out from the vertexes point toward vertexes in the right direction. Now, inside graphs that contain circles, we can hardly talk about topological order, as by definition, topological order can be made only from circle-free graphs. However, we ignore this fact and build this so-called topological order (the inverse order of how we leave the vertexes during a Depth-First Search). Now we will reverse the direction of the edges inside the graph.
This way the edges that build the topological order are reversed, and all that will remain as edges pointing from left to right are those that, until now, were against the topological order, pointing from right to left. These edges formed the base circle system of the graph.
Now if we call the DFS in the so-called “topological order,” each DFS will sense a strong connective component. On the inverse graph, the search can go ahead on those edges that were on a circle, and show those vertexes that are on a circle, and in the end it will drop by at each of the vertexes that maintain the circle.
Next: Show it in C >>
More Code Examples Articles
More By Gabor Bernat
/ 2 
