用于查找关节点或切割图的顶点的算法的说明
我搜索了网络,找不到DFS算法的任何解释来查找图的所有关节顶点。甚至没有维基页面。用于查找关节点或切割图的顶点的算法的说明
从阅读中,我了解了这里的基本事实。 PDF
在每个节点上都有一个变量,它实际上是在查看后端边缘并找到朝向根节点的最近和最上方的节点。在处理完所有边后,将会找到它。
但我不明白如何在执行DFS期间在每个节点上找到这个向上变量&。这个变量究竟在做什么?
请说明算法。
谢谢。
查找关节顶点是DFS的应用程序。
简而言之,
- 应用上的曲线图的DFS。获取DFS树。
- 较早访问的节点是那些到达并稍后访问的节点的“父”。
- 如果一个节点的任何孩子没有到其父代的任何祖先的路径,这意味着删除这个节点会使这个孩子与图表分离。
- 有一个例外:树的根。如果它有不止一个孩子,那么它是一个关节点,否则不是。
点3本质上意味着这个节点是一个关节点。
现在对于一个孩子来说,这条通往节点祖先的路径将通过它的后端或其任何子节点。
所有这一切在这PDF精美地解释。
如果u
后代的low
大于u
的dfsnum
大,那么u
据说是关节点。
int adjMatrix[256][256];
int low[256], num=0, dfsnum[256];
void cutvertex(int u){
low[u]=dfsnum[u]=num++;
for (int v = 0; v < 256; ++v)
{
if(adjMatrix[u][v] && dfsnum[v]==-1)
{
cutvertex(v);
if(low[v]>dfsnum[u])
cout<<"Cut Vertex: "<<u<<"\n";
low[u]=min(low[u], low[v]);
}
else{
low[u]=min(low[u], dfsnum[v]);
}
}
}
我会尽力制定关于如何算法的工作一个直观的了解,并给予评论伪输出双组件以及桥梁。
实际上很容易为关节点开发一个强力算法。只需取出一个顶点,然后在图上运行BFS或DFS。如果它保持连接,那么顶点不是关节点,否则是。这将运行在O(V(E+V)) = O(EV)
时间。面临的挑战是如何在线性时间内做到这一点(即O(E+V)
)。
铰接点连接两个(或更多)子图。这意味着从一个子图到另一个子图没有边。所以想象你在这些子图之一内并访问它的节点。在您访问节点时,您会标记该节点,然后使用某个可用边移动到下一个无标记节点。当你这样做时,你怎么知道你还在同一个子图里?这里的见解是,如果你在同一个子图中,你最终将在访问一个未被标记的节点时通过边缘看到一个被标记的节点。这被称为后沿,表明你有一个循环。一旦找到后端边缘,您可以确信,通过该标记节点的所有节点到您正在访问的节点都是同一子图的一部分,并且两者之间没有关联点。如果您没有看到任何后缘,那么到目前为止您访问的所有节点都是关节点。
所以我们需要为当前存在访问过节点返回边缘的目标之间的访问顶点和标记所有点为同一子图内的算法。子图中显然可能有子图,所以我们需要选择我们迄今为止最大的子图。这些子图被称为双组分。我们可以通过为每个双分量分配一个初始化的ID作为我们到目前为止访问的顶点数量的计数来实现这个算法。后来,当我们找到边缘时,我们可以将双亲ID重置为迄今为止我们发现的最低。
我们显然需要两遍。在第一遍中,我们想要确定哪个顶点可以通过后边缘从每个顶点看到,如果有的话。在第二遍中,我们希望访问相反方向的顶点并收集最小的双组分ID(即可从任何后代访问的最早的祖先)。 DFS自然适合这里。在DFS中,我们先下去,然后再回来,所以上述两个过程都可以在单个DFS遍历中完成。
现在事不宜迟,这里的伪代码:
time = 0
visited[i] = false for all i
GetArticulationPoints(u)
visited[u] = true
u.st = time++
u.low = v.st //keeps track of highest ancestor reachable from any descendants
dfsChild = 0 //needed because if no child then removing this node doesn't decompose graph
for each ni in adj[i]
if not visited[ni]
GetArticulationPoints(ni)
++dfsChild
parents[ni] = u
u.low = Min(u.low, ni.low) //while coming back up, get the lowest reachable ancestor from descendants
else if ni <> parent[u] //while going down, note down the back edges
u.low = Min(u.low, ni.st)
//For dfs root node, we can't mark it as articulation point because
//disconnecting it may not decompose graph. So we have extra check just for root node.
if (u.low = u.st and dfsChild > 0 and parent[u] != null) or (parent[u] = null and dfsChild > 1)
Output u as articulation point
Output edges of u with v.low >= u.low as bridges
output u.low as bicomponent ID
看起来连接到根节点的桥切割节点的情况是在这里丢失(直接链接到其相同组件中的根节点的桥接节点将不会被识别为关节点) – 2015-06-22 15:29:47
@MarcoA。 - 我认为最后的第二个条件应该这样做(如果我理解你的陈述是正确的)。顺便说一下,这个算法是由Hopcraft和Tarjan给出的,它的正确性已经在他们的论文中得到了严格的证明。 – ShitalShah 2015-06-23 10:28:26
我很抱歉,这是一个为O(n^2)算法PDF。它也说,有O(边)时间的算法太..请解释一下 – 2013-04-08 07:07:48
你可以试一下comp science forum – akonsu 2013-04-08 07:08:46
能不能发表这个表格的链接?你的意思是说我从哪里得到pdf的大学? – 2013-04-11 06:57:21