简介
最近在学习一些图相关的算法时碰到一个比较有意思的问题。就是关于图中间桥的问题。在图中,一般的边是用于连接两个节点的。如果结合图的连通性来考虑,假设一个边连着图的两个部分,如果我们将这个边去掉,那么将使得图变成两个分割开的部分。那么,这个时候我们称这个边是桥。
那么,对于一个图来说,我们能否找到一些这样的桥呢?
分析
在找到具体的规律之前,我们先看一个图的示例:
从上图来看,我们需要找到一个边,这个边如果去掉之后会使得整个图被分割成两个不相连的部分。很明显,节点1和4构成的边恰好符合这个条件。而其他的边则不符合这个条件。那么这些不符合条件的边像<1, 2>, <2, 3> 为什么就删除了也不会破坏图的连通性呢?
很显然,因为这些边正好构成了一个连通的图,更精确的说,它们构成了一个环。对于一个环来说,每个节点是有两个连接的边,去掉一个对它的连通性不会有任何影响。因此,这就应该是问题的关键了。对于我们要讨论的问题来说,如果我们能够找到一个环上面所有的点,那么这些点之间的边就都可以排除成为bridge的可能性了。
现在的问题是,我们怎么来判断图中间存在环呢?就算我们判断出来了环,怎么把环上面的这些节点给标注出来? 首先一个,针对图中间环的判断,我们之前有文章进行过讨论。我们可以通过对图进行深度优先遍历,然后每次访问一个节点的时候就将该节点对应的一个标志位设置为true。在访问到某个已经之前访问过的节点,但不是当前节点的前一个节点时,我们可以判断存在环。这样子是可以解决判断环存在的问题了。
现在是,怎么把这些构成环的节点给找出来呢?或者说我们能否想到一个办法判断出哪些边构成了桥呢?在这里,我们可以在判断环存在的问题的基础上做一点修改。我们知道,判断一个环存在的话,它必然是在递归调用的过程中碰到了一个之前访问过的节点。如果我们用一个计数器来记录每次递归调用移动一步时的步数,那么这里就记录出来了从某个给定的起始节点到某个终点的步数。对于存在环的情况,在这个和之前访问过的节点相邻的节点,它到这个节点就可能有两个步数。而且两个节点一个大一个小。
这个时候,如果我们同时用另外一个数组来记录到这个节点的最短步数,那么必然这个在检测到构成环的节点位置它可以取到一个更小的步数值。如果我们循着这个思路往回退呢?就是说当我们递归调用回溯的时候,我们可以针对这个节点的前一个节点进行设置,也对应的取当前节点和它前一个节点的步数最小值。这样,我们可以这么一路倒退的回到环的起点。而这个最小步数就成了这个环里头所有元素的标记。从前面的讨论可以看到,只要存在环,那么它当前的最小步数就会比当前的累加步数小。这样就可以推导出环上的点了。
那么,对于非环上面的点呢?它不会存在有环路,所以走到某个点的时候,它必然就到头了,而这个时候,它的最小步数应该和累加步数是一样的。这样,我们就得到了一种寻找桥的方法了。
在实现的时候,我们可以采用两个数组,int[] pre, int[] low。其中pre数组用来保存记录当前的积累步数,而low节点在回溯的时候用来取它和相邻节点中的最小值。同时碰到环的时候也需要当前节点最小步数和目标节点累积步数中最小的那个。
按照这个思路,我们可以得到如下的代码:
public class Bridge { private int bridges; private int count; private int[] pre; private int[] low; public Bridge(Graph g) { low = new int[g.vertices()]; pre = new int[g.vertices()]; for(int i = 0; i < g.vertices(); i++) { low[i] = -1; pre[i] = -1; } for(int v = 0; v < g.vertices(); v++) if(pre[v] == -1) dfs(g, v, v); } public int components() { return bridges + 1; } private void dfs(Graph g, int u, int v) { pre[v] = count++; low[v] = pre[v]; for(int w : g.adj(v)) { if(pre[w] == -1) { dfs(g, v, w); low[v] = Math.min(low[v], low[w]); if(low[w] == pre[w]) { bridges++; } } else if(w != u) { low[v] = Math.min(low[v], pre[w]); } } } }
上述代码的过程有点不太好懂,我们可以以图中的示例为基础来演示一下变化。假设我们从节点0开始遍历,那么刚开始的时候调用的过程是dfs(g, 0, 0):
这个时候我们设置的pre, low数组值如下图:
根据节点的连接,假设节点0的下一个邻接节点是1,那么我们将递归的调用dfs(g, 0, 1):
假设节点1的下一个邻接节点是2,那么有下图:
假设2的下一个邻接节点是3,那么有:
这时候,如果3的下一个邻接节点是0,则相当于碰到了一个之前访问过的元素,也就是构成了环了。那么我们将有如下的变化:
因为之前已经访问过节点0了,所以这里要将节点3的最小步数也就是low[3] 设置为pre[0],也就是0。在这里,节点3的前一个节点是2,而它连接访问的下一个节点是0,所以可以进行这么一个判断。在这一步之后,我们的递归调用就应该要返回了。于是进入一个回溯的阶段。首先回溯的就是方法dfs(g, 2, 3):
在回溯的时候,我们会比较low[2], low[3],同时设置修改low[2] = Math.min(low[2], low[3]);这样,就使得low[2] = 0。这样,我们继续回溯到dfs(g, 1, 2),我们有如下的结果:
而这时候,我们有节点4还没有访问,于是又有方法dfs(g, 1, 4) :
对于节点4来说,它没有其他的相邻节点除了它的前一个节点1。所以当dfs(g, 1, 4)返回的时候,pre[4] == low[4],那么,1和4节点之间就构成了一个桥。
在这里我们也看到,当一个节点它没有访问到之前节点的时候,它的low节点值是不可能变化的,因此它的low节点和pre节点是一样的。这样也就找到了桥。
总结
关于图中间桥的查找和判断是一个有点难度的问题。它要借鉴图中间环的判断过程,同时也需要通过一种方式将环中间的节点依次给标注出来。这里利用深度优先遍历的递归和回溯过程,通过在回溯的时候将当前节点和它的相邻节点进行调整。这样如果节点步数没有变化则找到了桥边。这种利用的方式比较巧妙,值得反复推敲。
参考材料
http://algs4.cs.princeton.edu/41graph/Bridge.java.html
相关推荐
计算机科学包括其独有的思维方式,而且该思维方式贯穿于计算机相关课程的学习,经过大学计算机基础和计算机程序设计两门课程不到120 学时的学习培养起来的计算思维,对于计算机硬件基础课程的学习略显单薄。...
摘要:讨论了PCI主桥的应用和Wishbone片上总线技术,详细介绍了基于Wishbone总线的PCI Bridge核的功能、内部结构和操作方式。实验证明,在PCI系统中使用PCI Bridge核进行开发设计,电路简洁,使用方便灵活。 ...
交换机可以发送并接收这些BPDU,以确定哪个交换机拥有最低的网桥ID,拥有最低网桥ID的那个交换机成为根网桥(root bridge)。 根网桥好比是小镇上的社区杂货店,每个小镇都需要一家杂货店,而每个市民也需要确定...
4.2 bridge(桥接)—对象结构型 模式 100 4.3 composite(组成)—对象结构型 模式 107 4.4 decorator(装饰)—对象结构型 模式 115 4.5 facade(外观)—对象结构型 模式 121 4.6 flyweight(享元)—...
但并不是每个设备都需要通过一个常规的计算设备来控制。想象一下传统的家用电器,例如电炉、微波炉或面包机。如果您的家用电器由 Android 控制,并且有一个彩色触摸屏,会怎么样?如果电炉上有一个 Android UI,那么...
因此一般讨论网络互连时都是指用交换机和路由器进行互联的网络。本文主要阐述交换机和路由器及其区别。[1] 路由器、交换机 · 交换机(Switch)是一种基于MAC(网卡的硬件地址)识别,能完成封装转发数据包功能的网络...
鼠标放在一个连接上,会显示图片(类似tooltip) 使用microsoft.web.ui.webcontrols的TabStrip与IFame组件,达到页的切换效果 HttpModule 实现 ASP.Net (*.aspx) 中文简繁体的自动转换,不用修改原有的任何代码,直接部署...
呵呵,因为,未必所有的数据库服务器提供商都提供下面的JDBC驱动程序(给JDBC访问提供相应的接口),所以就有了JDBC<->ODBC Bridge。 接着再让我们来看看第二种访问流程: JDBC Driver Mannager->局部JDBC驱动...
3.J2EE 只是适合企业计算应用的框架软件,但是 GoF 的设计模式几乎可以用于任何应用!因此 GoF 的设计模式应该是 J2EE 的重要理论基础之一。 所以说,GoF 的设计模式是 Java 基础知识和 J2EE 框架知识之间一座隐性...
倒啤酒是一种艺术,绝对是品尝体验的一部分,特别是当你需要足够的泡沫完美地排列在玻璃的边缘。由于比利时是啤酒之乡,我们决定为两种比利时啤酒(Duvel和Jupiler)...为了控制电机的速度和方向,H-Bridge连接到电机和
� Android 是款开源的移动计算软件平台,组建了 google 主导的拥有众多产业界巨头的产业联盟,有利于 高效开发、降低成本。 � 由于是源代码开放的产品,对非主导厂商而言,可以避开与主导厂商在核心技术上面的差距...