BYR Achieve · 镜像论坛

【问题】对于数据结构图论算法深度优先搜索双联通性不理解

2017/10/24镜像同步1 回复

初学数据结构的小菜鸟，用的是《数据结构与算法分析——C语言描述》。目前看到第9章（图论算法）中的9.6.2节（双连通性），对于其中一段话非常不理解。段落为：深度优先搜索提供一种找出连通图中的所有割点的线性时间算法。首先，从图中任一顶点开始，执行深度优先搜索并在顶点被访问时给它们编号。对于每一个顶点v我们称其先序编号为Num（V）。然后，对于深度优先搜索生成树上的每一个顶点v，计算编号最低的顶点，我们称之为Low（V)，该店从V开始，通过树的零条或多条边且有可能还有一条背向边而（以该序）到达。图9-63中的深度优先搜索树首先指出先序编号，然后指出在上述法则下可达到的最低编号顶点。对于上面红色的这句话，我理解是：对于图中任一一点V，该点能通过树的零条或多条边（最多包含一条背向边）而到达的编号最低的顶点【称之为Low（V)】的先序编号是该点V的Low。我的理解对么？谢谢

订阅后，新回复会通过你的通知中心匿名送达。