寻找接合点
寻找接合点
提问于 2015-04-08 01:33:59
我读了一些关于在图表中找到拼音点的教程，偶然发现了这一点。
1
在G中执行深度优先搜索，从任何节点开始。设T是深度优先搜索生成的树，对于图中的每一个节点v，设prenumv为搜索指定的数目。
2
按后序遍历树T。对于所访问的每个节点v，计算lowestv作为每个节点w的最小值，使得G中存在一个在T中没有对应边的边(v，w)。
3.
现在确定的发音点如下。T的根是G的一个交点当且仅当它有一个以上的子。除T的根外的节点v是一个交点G当且仅当v有一个子x，使得lowestx≥prenumv。
但我不太懂如何计算lowestx。有人能说得更清楚点吗？谢谢!
回答 2
Stack Overflow用户
发布于 2015-04-08 03:07:48
第2步，在伪代码中：
def visit(v):
lowest[v] = prenum[v]
for w in nodes:
if v is the parent of w in T:
visit(w)
lowest[v] = min(lowest[v], lowest[w])
elif w is connected to v in G:
if w is not the parent of v in T:
lowest[v] = min(lowest[v], prenum[w])Stack Overflow用户
发布于 2015-04-10 14:23:59
迭代伪代码版本，它结合了步骤1和步骤2：
i = 0
prenum[1] = lowest[1] = i = i + 1
S = EMPTY STACK
for each edge e connected to nodes[1]:
push edge e onto S
while S is not empty:
peek at edge e on S
let (u,v) = e such that prenum[u] <= prenum[v] or prenum[v] is undefined
if e is unvisited
mark e as visited
if prenum[v] is undefined
mark e as parent of v
prenum[v] = lowest[v] = i = i + 1
for each edge e' connected to nodes[v] except e:
push edge e' onto S
else
pop e from S
lowest[v] = min( lowest[v], prenum[u] )
else
pop e from S
if e is marked as parent of v
lowest[u] = min( lowest[u], [lowest[v] )页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/29504360
复制相关文章
相似问题
腾讯云开发者
