首页 > 程序开发 > 软件开发 > Java >

算法7-5:连接部件

2014-06-18

同学们一定用过Windows中的画图吧。那么画图中的油漆桶功能是如何实现的呢? 这个问题可以通过DFS深度优先搜索解决。 目标 我们要实现的目标是在常数的时间内判断某两个节点是否连接。 前

同学们一定用过Windows中的画图吧。那么画图中的油漆桶功能是如何实现的呢?


\


这个问题可以通过DFS深度优先搜索解决。


目标


我们要实现的目标是在常数的时间内判断某两个节点是否连接。
<喎"https://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+Cjxicj4KPC9wPgo8cD4Kx7DD5tXCvdrW0L3pydzBy7Kisum8r8vjt6ijrLKisum8r8i3yrW/ydLUveK+9tXiuPbOyszioaPO0sPHvfHM7MC0venJ3MHtzeLSu9bWsOy3qKOsxMe+zcrHREZTye7L0aGjPC9wPgo8cD4KPGJyPgo8L3A+CjxwPgrOqsHLveK+9tXiuPbOyszi16jDxb2owaLSu7j2ttTP86OsttTP87XEwtbAqsjnz8KjujwvcD4KPHA+CjwvcD4KPHByZSBjbGFzcz0="brush:java;">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也是连接的


连接部件的定义:相互连接的顶点最大集合。


问题解决


为了解决上述的问题,首先要对图进行预处理。预处理的目标就是区分图中的连接部件。


区分连接部件的步骤如下:

  1. 将所有的顶点都标记为未访问

  2. 对于每个未访问的顶点,使用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);
                }
            }
        }
    }


    应用


    下图是某高校的人际关系图。如果把人际关系看成一张图,那么这里面就可以很清楚地看到有大大小小的连接部件。


    \


    探测星空图中的星星数量。




相关文章
最新文章
热点推荐