Circles and Connectivity in Graphs - Show it in C
(Page 4 of 4 )
Quite ingenious, is it not? Moreover, here is our modified BFS algorithm. First, we call a simple DFS to tell us the inverse order of how we leave the vertexes; this will be saved inside the topological array, as shown in the previous article. Second, we invert the graph inside the inverseList array and finally call the DPS in the right order. Here is what this looks like when translated into C:
void DFS_inver(int vertex)
{
printf(" %d ", vertex);
pListIt p;
color[vertex] = GRAY;
for (p = inverseList[vertex]; p != NULL; p = p -> p_next)
if (!color[p -> value])
{
DFS_inver(p -> value);
}
}
…
for (i = 0 ; i < n; ++i)
if (!color[topological_order[i]])
{
callCount++;
printf("n%d) ", callCount);
DFS_inver(topological_order[i]);
}
This way we will get as result for the upper graph the result:
The strong connected components of the graph
1) 1 8 5 2 12 11 9 6 3 10 18 14 20 15 19
2) 4
3) 17
4) 13 22 16
5) 21
6) 7
With this, we have solved all the problems for today. Now if we want to tell what points on the map can be reached from a certain point, all we need to do is enter the map's information as input and read the result from the output file. Here is the C source file that contains all of the techniques discussed in this article. Feel free to explore it and try it out for different inputs.
-->BDF.zip<--
I would like to thank you for reading through my article and invite you to tell me your thoughts related to it here on the blog or over at our friendly forum on Dev Hardware. The subject of our next article will be articulation edges and vertexes, so if you are interested make sure to come back. Until the next time we meet, 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. |
/ 2 
