六讲贯通C++图的应用之三 无向图(1)(2)

关节点

下定义是人们认识事物的一个方法，因为概念使得人们能够区分事物――关于这个还有个绝对的运动和相对的静止的哲学观点(河水总在流，但是长江还叫长江，记得那个著名的“不可能踏进同一条河里”吗?)因此，能否有个准确的概念往往是一门学科发展程度的标志，而能否下一个准确的定义反映了一个人的思维能力。说这么多废话，原因只有一个，我没搞清楚什么叫“关节点”――参考书有限，不能仔细的考究了，如有误解，还望指正。

严版是这么说的：如果删除某个顶点，将图的一个连通分量分割成两个或两个以上的连通分量，称该顶点为关节点。――虽然没有提到图必须是无向的，但是提到了连通分量已经默认是无向图了。

殷版是这么说的：在一个无向连通图中，……(余下同严版)。

问题出来了，非连通图是否可以讨论含有关节点?我们是否可以说某个连通分量中含有关节点?遗憾的是，严版留下这个问题之后，在后面给出的算法是按照连通图给的，这样当图非连通时结果就是错的。殷版更是滑头，只输出重连通分量，不输出关节点，自己虽然假定图是连通的，同样没有连通判断。

翻翻离散数学吧，结果没找到什么“关节点”，只有“割点”，是这样的：一个无向连通图，如果删除某个顶点后，变为非连通图，该顶点称为割点。权当“割点”就是“关节点”，那么算法至少也要先判断是否连通吧?可是书上都直接当连通的了……

关于算法不再细说，书上都有。下面的示例，能输出每个连通分量的“关节点”(是不是可以这样叫，我也不清楚)。dfn储存的是每个顶点的访问序号，low是深度优先生成树上每个非叶子顶点的子女通过回边所能到达的顶点最小的访问序号。把指向双亲的边也当成回边并不影响判断，因此不必特意区分，殷版显式区分了，属于画蛇添足。这样一来，if (low[n] >= dfn[i]) cout << getV(i);这个输出关节点的判断中的>=就显得很尴尬了，因为只能等于不可能大于。还要注意的是，生成树的根(DFS的起始点)是单独判断的。

void articul()  
{  
dfn = new int[vNum()]; low = new int[vNum()]; int i, j = 0, n;  
for(i = 0; i < vNum(); i++) dfn[i] = low[i] = 0;//初始化  
for (i = 0; i < vNum(); i++)  
{  
if (!dfn[i])  
{  
cout << '(' << ++j << ')'; dfn[i] = low[i] = count = 1;  
if ((n = nextV(i)) != -1) articul(n); bool out = false;//访问树根  
while ((n = nextV(i, n)) != -1)  
{  
if (dfn[n]) continue;  
if (!out) { cout << getV(i); out = true; }//树根有不只一个子女  
articul(n);//访问其他子女  
}  
cout << endl;  
}  
}  
delete []dfn; delete []low;  
}  
 
private:  
void articul(int i)  
{  
dfn[i] = low[i] = ++count;  
for (int n = nextV(i); n != -1; n = nextV(i, n))  
{  
if (!dfn[n])  
{  
articul(n);  
if (low[n] < low[i]) low[i] = low[n];  
if (low[n] >= dfn[i]) cout << getV(i);//这里只可能＝  
}  
else if (dfn[n] < low[i]) low[i] = dfn[n];//回边判断  
}  
}  
int *dfn, *low, count;