首页 > 代码库 > 算法7-5:连接部件
算法7-5:连接部件
同学们一定用过Windows中的绘图吧。那么绘图中的油漆桶功能是怎样实现的呢?
这个问题能够通过DFS深度优先搜索解决。
目标
我们要实现的目标是在常数的时间内推断某两个节点是否连接。
前面章节中介绍了并查集算法,并查集确实能够解决问题。我们今天来介绍第二种办法,那就是DFS深搜。
为了解决问题专门建立一个对象,对象的轮廓例如以下:
public class ConnectedComponnent { public ConnectedComponnent(Graph G) { } // 推断两个顶点是否连接 public boolean connected(int v, int w) { } // 连接部件的个数 public int count() { } // 顶点所在的连接部件的编号 public int id(int v) { } }
数学定义
推断两个顶点是否连接在离散数学中是等价关系,它具有:
反射性:v和v是连接的
对称性:假设v和w是连接的,那么w和v也是连接的
传递性:假设v和w是连接的,w和z是连接的,那么v和z也是连接的
连接部件的定义:相互连接的顶点最大集合。
问题解决
为了解决上述的问题,首先要对图进行预处理。预处理的目标就是区分图中的连接部件。
区分连接部件的过程例如以下:
将全部的顶点都标记为未訪问
对于每一个未訪问的顶点,使用DFS标记部件编号
代码
public class ConnectedComponnent { private boolean[] visited; private int[] id; private int count; public ConnectedComponnent(Graph G) { visited = new boolean[G.V()]; id = new int[G.V()]; cc(G); } // 推断两个顶点是否连接 public boolean connected(int v, int w) { return id[v] == id[w]; } // 连接部件的个数 public int count() { return count; } // 顶点所在的连接部件的编号 public int id(int v) { return id[v]; } private void cc(Graph G) { for (int i = 0; i < G.V(); i++) { if (!visited[i]) { dfs(G, i); count++; // 注意:这句话不能放在if之外。不然count总是等于顶点数量 } } } private void dfs(Graph G, int v) { visited[v] = true; id[v] = count; for (int w : G.adj(v)) { if(!visited[w]) { dfs(G, w); } } } }
应用
下图是某高校的人际关系图。假设把人际关系看成一张图,那么这里面就能够非常清楚地看到有大大小小的连接部件。
探測星空图中的星星数量。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。