算法第四版 第四章 无向图

作者 柚爸

算法第一遍看真的是只能面上过过, 难度还是挺高的, 不过至少原理懂了一些. 前边的排序和散列表除了红黑树删除那部分之外, 其他的倒也能懂, 问题不大.

图算法之前接触的很少, 现在来试着了解一下吧.

  1. 顶点与边
  2. 图的常用API
  3. 图的数据结构
  4. 搜索图的API
  5. 深度优先搜索 – 连通性问题
  6. 深度优先搜索 – 路径搜索
  7. 广度优先搜索 – 路径搜索
  8. 深度优先搜索 – 连通分量

顶点与边

一个无向图, 就是一组顶点与边组成的图. 一般指代顶点用0-V-1来指代有V个顶点的图. 依据之前的数据结构, 有了符号表之后, 可以建立起任意的映射.

对于一个边来说, 可以用两个一组的顶点来表示一个边, 比如 v-w 表示v和w之间的边, 这个边与 w-v 是同一条边.

将图画出来可能会有助于理解, 但不要被画出来的图形所误导, 图的形状有很多种, 这里讨论的是无序图, 所以结构其实有很多种.

图里有两种特殊情况, 一种是一个边连接一个点和其自身, 这个叫做自环; 另外一种是两个点有多个边相连, 叫做平行边. 算法这本书还算入门, 不会讨论这两种情况.

知道了顶点和边之后, 还有一系列术语需要掌握:

  1. 相邻, 指两个顶点有边相连, 称这两个顶点是相邻的
  2. 依附, 一条边依附于其连接的两个顶点
  3. 度数, 指一个依附于一个顶点的边的数量
  4. 子图, 指一个图所有边的子集加上依附的顶点构成的图
  5. 路径, 由边顺序连接的一系列顶点
  6. 简单路径, 没有重复顶点的路径
  7. , 至少含有一条边且起点和重终点相同的路径
  8. 简单环, 除了起点=终点之外, 没有任何重复的顶点和边
  9. 长度, 路径或者环包含的边的数量
  10. 连通, 两个顶点之间存在一条路径, 可以使用 u-v-w-x 之类来表示
  11. 连通图, 任意一个顶点都存在路径到达其他所有顶点, 就是连通图. 一个非连通图由若干连通的部分组成, 这些连通的部分都是非连通图的极大连通子图
  12. 无环图, 不包含环的图. 树就是一种无环连通图, 互不相连的树组成的集合叫做森林. 一个连通图可以找到一个对应的生成树(也是这个连通图的子图), 这个生成树包含这个连通图的所有顶点, 但是没有环. 这种生成树不只一种, 其集合叫做生成树森林.
  13. 密度, 已经连接的顶点对, 占所有可能连接的顶点对总数的百分比. 百分比低的叫做稀疏图, 百分比高的叫做稠密图.
  14. 二分图, 每两个相连的顶点, 都属于不同类型的集合. 像一个三角形的环, 就无法成为一个二分图.

如何判断一个有V个结点的图G是一个树的方法已经研究的很成熟了, 有如下五个条件, 满足其中一个就是树:

  1. G有V-1条边且没有环
  2. G有V-1条边且连通
  3. G是连通的, 删掉任意一条边, 都不再连通
  4. G是无环图, 但添加任意一条边都会产生一条环
  5. G中任意一对顶点之间仅存在一条简单路径

这个几个东西都被数学证明了, 不过脑子里想一下, 还是挺直观的.

这一上来就一堆术语, 看来这图算法真的不太简单啊.

图的常用API

用哪种数据结构来表示图, 这是一个关键问题. 为此先来看一下一般图操作的API:

public class Graph
                     Graph(int V)            //创建含有V个顶点但不含有边的图
                     Graph(In in)            //从in读入图数据
                 int V()                     //获取顶点数
                 int E()                     //获取边数
                void addEdge(int v, int w)   //为v和w添加一个边
Iterable<Integer> adj(int v)              //返回和V相邻的所有顶点
              String toString()              //将图打印为字符串

然后是依据这些API的一些方法:

  1. 计算顶点v的度数: 遍历adj,返回其中的顶点数
  2. 计算所有顶点的最大度数, 遍历各个顶点的度数然后返回其中的max值
  3. 计算顶点的平均度数, 直接用总边数除以总顶点数, 也就是使用E()/V()即可
  4. 计算自环的个数, 遍历所有顶点, 找到每个顶点的adj()返回结果中与自己相等的顶点, 然后除以2, 因为是按照顶点来的, 所以每条边会被计算两次
  5. toString 的实现, 可以打印每个顶点, 然后打印这个顶点有连接的顶点.

图的数据结构

图的数据结构, 这里算法很直接明了的给出了答案, 可以使用邻接表数组, 即使用一个数组, 将顶点号当做数组索引, 数组的每一个元素也是一个数据结构, 其中存放着与这个顶点相连接的顶点.

数组中的每一个元素具体使用什么数据结构, 有很多选择, 算法书上使用了第一章里的背包, 是一个用链表实现的背包.

这里要注意的是如果要添加 v-w 边, 要把w添加到v的邻接表中, 再把v添加到w的邻接表中, 每条边会出现两次.

而且还支持平行边和自环, 也就是说邻接表中的元素可能出现重复. 算法这里为了简单, 不会去检测平行边和自环. 使用这种邻接表的数据结构, 唯一有些有趣的地方就是同样的图, 不同的构造顺序会导致实际的邻接表中的顺序有所改变.

来看一个如此实现的Graph数据结构:

public class Graph {
    //V是顶点数量
    private final int V;
    //E是边数
    private int E;
    //邻接表数组adj
    private Bag<Integer>[] adj;

    //构造函数, 传入顶点数量, 会初始化长度为V的数组, 并且为每个顶点(索引号)创建一个新的邻接表
    public Graph(int V) {
        if (V < 0) throw new IllegalArgumentException("Number of vertices must be nonnegative");
        this.V = V;
        this.E = 0;
        adj = (Bag<Integer>[]) new Bag[V];
        for (int v = 0; v < V; v++) {
            adj[v] = new Bag<Integer>();
        }
    }

    public int V() {
        return V;
    }

    public int E() {
        return E;
    }

    //核心函数之一: 添加边
    public void addEdge(int v, int w) {
        //两条边各添加一次
        adj[v].add(w);
        adj[w].add(v);
        E++;
    }

    //返回顶点V的相连的点
    public Iterable<Integer> adj(int v) {
        validateVertex(v);
        return adj[v];
    }
}

在这个的基础上还可以进行一些改进, 比如使用集合替代Bag, 这样就指明了不允许出现平行边, 删除顶点和添加顶点, 删除一条边之类. 这很可能就不能使用Bag数组, 而需要使用符号表来替代数组.

搜索图的API

关于图的算法, 常见的是已知一幅图, 需要来获取图的性质, 算法里给出了几个常见的处理API:

public class Search
            Search(Graph G, int s)  //根据图G和顶点s, 构造一个图G中基于顶点s的对象
    boolean marked(int v)           //检测v和s是否连通
        int count()                 //与S连通的顶点总数

每次用一个图和一个顶点创建一个Search对象, 就可以调用marked算法来检测连通性. 下边就是要根据不同的算法, 创建不同类别的Search对象, 和实现其中的 marked 方法.

在第一章里边的连通性算法, 其实就是解决这个问题的一个途径, 要做的就是从图里取出所有的连接点, 然后将其放入连通分量中, 之后通过连通分量来判断是否连通.

不过这里需要学习一个专用的图算法, 深度优先搜索, 而且是后边图算法的基础.

深度优先搜索 – 连通性问题

深度优先搜索的意思是:

  1. 将一个顶点标记为已经访问
  2. 递归的访问它的所有没有被标记过的邻居顶点

这种方法会使用一个布尔数组, 用其中的索引号对应顶点号, 记录所有与给定顶点相连的所有顶点. 如果图是连通的, 所有的顶点最终都会被标记到.

深度优先搜索的每一条边会被查找两次, 第二次的时候会发现该条边已经被搜索过. 所以实际搜索轨迹是总边数的一倍.

深度优先的代码如下:

public class DepthFirstSearch {
    //布尔数组
    private boolean[] marked;
    //记录所有和s连通的顶点的数量
    private int count;

    //使用G和S创建一个深度优先搜索对象
    public DepthFirstSearch(Graph G, int s) {
        marked = new boolean[G.V()];
        dfs(G, s);
    }

    //核心方法, 递归搜索
    private void dfs(Graph G, int v) {
        //每次进入一个新的递归, 就说明新找到一个和s连通的顶点, 所以count++
        count++;
        //将新找到的顶点标记为true
        marked[v] = true;
        //在新的顶点的邻接表里遍历所有的顶点, 继续递归调用这个方法, 直到所有的顶点都已经被标记
        for (int w : G.adj(v)) {
            if (!marked[w]) {
                dfs(G, w);
            }
        }
    }

    //由于在构造对象的时候就使用了dfs, 所以可以直接使用这个方法, 寻找v对应的索引就可以发现是否与s连通了.
    public boolean marked(int v) {
        return marked[v];
    }

}

使用深度优先搜索, 也可以解决一开始的问题, 就是两个点是否连通, 只需要在运行结束之后, 检查布尔数组对应索引的两个值是不是都是true即可. 但是相比连通性算法, 深度优先搜索还可以给出连通算法无法给出的答案, 就是这条路径具体是什么.

路径搜索

路径搜索有点像之前的利用数组索引进行构造一个相连的树的方法.

在之前的深度优先算法里, 每次第一次访问一个连通的边的时候, 就按照对应的索引, 把另一个端点放入到数组的对应的索引里, 比如是从0开始搜索, 遇到2的时候, 就在数组2的位置放入0, 之后2去搜索到第一个3的时候, 在数组3的位置放入2, 这样一直到搜索到想要的节点, 然后反过来用数组不断取数当成索引就可以找到路径.

这算法还真是给力, 要是不从第一章看过来, 就不会立刻理解这个算法, 用数组做成树还真是有意思.

改进的可以返回路径的代码如下, 注意红色的部分:

public class DepthFirstPaths {
    private boolean[] marked;    // marked[v] = is there an s-v path?
    private int count;

    //起点
    private final int s;

    //用数组表示的树
    private int[] edgeTo;

    public DepthFirstPaths(Graph G, int s) {
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        this.s = s;
        dfs(G, s);
    }

    private void dfs(Graph G, int v) {
        count++;
        marked[v] = true;
        for (int w : G.adj(v)) {
            if (!marked[w]) {
                //w索引的值是v, 对于第一次递归来说, v就是s, 这样就一层一层通过数组可以追查到s
                edgeTo[w] = v;
                dfs(G, w);
            }
        }
    }

    public boolean marked(int v) {
        return marked[v];
    }

    public int count() {
        return count;
    }

    public boolean hasPathTo(int v) {
        return marked[v];
    }

    //其实有了前边的数组, 从v开始不断循环v = edgeTo[v]就可以找到路径
    //这里是弄了一个方法专门保存了路径的栈
    public Iterable<Integer> pathTo(int v) {
        //如果没有路径, 就结束
        if (!hasPathTo(v)) {
            return null;
        }
        Stack<Integer> path = new Stack<>();
        //用循环不断跟着找下去, 直到i=s为止
        for (int i = v; i != s; i = edgeTo[i]) {
            path.push(i);
        }
        //循环结束的时候, 所有的除了s之外的路径都被压入栈中, 最后压一个s的值进去
        path.push(s);
        return path;
    }
}

为了要显示路径, 所以要保存一下s的值, 不能像原来的构造器一样直接把s交给dfs进行搜索. 核心的变化就是在dfs第一次找到的时候, 设置数组中与当前顶点值相同的索引值w对应的值, 为上一级节点的值(也就是作为参数的v), 这个技巧和连通算法时候其实一样的.

但是想一想这个递归就可以看出来, 假如连通的话, 肯定会有一条路径能够连通, 但是递归的顺序会影响找到这条路径的方式, 所以找到的路径可能会不同, 也可能不是最短的.

深度优先搜索无法解决这个问题, 因为顾名思义, 这个东西一定是搜索到最深, 不行了, 再从其他的分支返回, 所有的方向都是一搜到底的. 所以就要使用广度优先算法了.

广度优先搜索 – 路径搜索

从深度优先搜索的代码可以看出, 其一路遇到没找过的节点就继续递归, 算法348页的图很好的说明了这点, 会一路找到最深然后逐层返回, 再寻找分支.

广度优先搜索是另外一种方法, 即先搜索最近的一批节点, 再搜索下一批相邻的节点. 其与深度优先搜索不同点就是进入递归之前的处理, 并不是直接进入递归, 而是挨个处理完最近的一批之后再递归, 即递归的顺序与深度优先是不同的.

转换成代码, 实际就是使用一个队列, 将一个节点临近的所有节点都压入队列, 然后处理队列中的点, 不断循环直到队列里没有空, 即无法再向其中添加内容, 也就意味着遍历了所有的点.

写成代码如下:

public class BreadthFirstPaths {
    //依然有一个用来记录所有顶点被标记过的数组
    private boolean[] marked;
    //使用树结构记录路径的数组
    private int[] edgeTo;
    //作为起点的顶点
    private final int s;

    //构造器
    public BreadthFirstPaths(Graph G, int s) {
        marked = new boolean[G.V()];
        edgeTo = new int[G.V()];
        //这次是执行bfs广度优先搜索啦, 算法就在这个方法里
        bfs(G, s);
        assert check(G, s);
    }

    //广度优先搜索算法
    private void bfs(Graph G, int s) {
        //先创建一个新的队列
        Queue<Integer> q = new Queue<Integer>();
        //先将起点标记为true
        marked[s] = true;
        //然后把s放入到队列里, 即最先处理的就是s顶点
        q.enqueue(s);

        //只要队列不为空
        while (!q.isEmpty()) {
            //从队列里弹出最前边的顶点
            int v = q.dequeue();
            //对这个顶点的所有相邻顶点, 如果第一次处理, 就扔到队列里
            for (int w : G.adj(v)) {
                //检测如果已经标记, 不做处理
                if (!marked[w]) {
                    //如果未标记, 像深度优先那样使用edgeTo数组作为树来标记
                    edgeTo[w] = v;
                    //标记自己已经被遍历过
                    marked[w] = true;
                    //将自己放入到队列里
                    q.enqueue(w);
                }
            }
        }
    }

}

其他函数都可以省略, 和之前的深度优先的类似. 这里关键是广度优先不再一直递归到底, 而是始终优先处理最相邻的元素. 在处理完之后, 就得到了edgeTo这个树结构的表示, 其中只要去按照某个索引寻找, 找回S的路径都是最短的.

深度优先搜索 – 连通分量

一幅图可能不是完全连通的, 也可能是完全连通的. 依靠深度优先搜索, 可以获得一个图的连通分量个数, 以及可以判断哪些点是连通的.

这个算法的原理很简单, 无论深度还是广度优先搜索, 都可以遍历完一个连通的图的所有顶点. 所以对于所有的顶点, 都可以执行一次深度优先搜索.

在针对第一个顶点进行深度优先搜索之后, 与其相连的所有顶点都应该被标记了, 只不过不标记true和false了, 可以给予一个数字当做连通分量号. 再对下一个顶点进行搜索的时候, 如果发现顶点已经被标记, 说明这个顶点和之前搜索过的顶点是连通的, 就可以直接跳过, 直到找到下一个没有标记过的顶点, 这就代表一个新的连通分量, 对其搜索完之后, 赋予一个不同的连通分量号.

遍历完所有的顶点之后, 根据标记数就可以知道有几组分量, 而且此时marked数组也变成了第一章的连通分量数组, 检测两个点是否连通, 可以通过索引查找值是否相同来快速确定.

所以这个算法写起来其实挺简单:

public class CC {
    //依然是顶点标记数组
    private boolean[] marked;
    //连通分量数组
    private int[] id;
    //连通分量号
    private int count;

    //构造器中
    public CC(Graph G) {
        marked = new boolean[G.V()];
        //获取总的顶点数量的数组
        id = new int[G.V()];
        //遍历所有顶点, 如果v没有被标记过, 就进行标记
        for (int v = 0; v < G.V(); v++) {
            if (!marked[v]) {
                //在一次DFS中, 给所有连通的顶点设置的count相同, 下一次则是一个新的count
                dfs(G, v);
                count++;
            }
        }
    }

    //dfs和之前的搜索没有什么本质的不同, 只是加上了将id数组对应的索引设置为count的功能
    private void dfs(Graph G, int v) {
        marked[v] = true;
        id[v] = count;
        for (int w : G.adj(v)) {
            if (!marked[w]) {
                dfs(G, w);
            }
        }
    }

    //方便的通过id数组检测是否连通的方法
    public boolean connected(int v, int w) {
        return id(v) == id(w);
    }
}

算法内部维护了两个数组, 一个marked数组依然用于存放是否标记过, 一个id数组是连通分量数组, marked数组辅助DFS生成id数组.

可见这个方法和第一章的连通分量方法异曲同工之妙.

后边深度优先的几个应用回头再来看吧, 感觉还没有搞清楚是怎么一回事, 对于这些数据结构的应用场景, 很多时候心里还没底.