Articulation Edges and Vertexes - Articulation Vertexes: Code Snippet
(Page 4 of 4 )
Now that we know how it should work in theory, we shall implement it in simple C code.
int DFS_Articulation_vertex(int vertex, int szint)
{
color[vertex] =GRAY;
topological_order[vertex] = szint;
int sTMinLevBaPE = INT_MAX;
int sTMinLevBaPECur = 0;
int dropOffChilds = 0;
int childs = 0;
pListIt p;
for (p = adjacencyList[vertex]; p != NULL; p = p -> p_next)
{
if (!color[p -> value])
{
ancient[p->value] = vertex ;
++childs;
sTMinLevBaPECur =
DFS_Articulation_vertex(p->value, szint + 1);
if (sTMinLevBaPECur < szint)
{
if( sTMinLevBaPECur < sTMinLevBaPE)
{
sTMinLevBaPE = sTMinLevBaPECur;
}
}
else
{
++dropOffChilds;
}
}
else
{
if (color[p->value] == 1 &&
topological_order[p->value] < szint -1 && topological_order[p->value] < sTMinLevBaPE )
{
sTMinLevBaPE = topological_order[p->value];
}
}
}
color[vertex] = BLACK;
if (ancient[vertex])
{
if (dropOffChilds)
{
printf(" %d -> %dn", vertex, dropOffChilds);
}
else
{
if (childs > 1)
{
printf(" %d -> %dn", vertex, childs);
}
}
}
return sTMinLevBaPE;
}
The solution for the graph on the previous page:
Articulation vertexes
5 -> 1
15 -> 2
16 -> 1
13 -> 1
14 -> 1
11 -> 2
6 -> 2
3 -> 1
-->BDF.zip<--
We made it to the end of this article. The source file you may download from the above link contains everything we did during our last three articles, including how the Depth First Search works and how we may use the additional information generated during the search. We also saw how, by refining the search a little and making minimal modifications, we turned it into a complex problem-solving technique.
I am honored to catch your attention for the time you read this article, and I would like to remind you of the rating possibilities you have by simply giving a mark to the article or expressing your thoughts in the blog dedicated to this article. Eventually you may also join the DevHardware forum and act in the same manner there. During the next article, the subject will be spanning trees with minimal cost. Until next time 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. |
