4.2 有向图

4.2.1介绍

在有向图中,边是单向的.实际上组合性的结构对算法有深远影响,使得有向图和无向图之间的处理大有不同.
顶点出度: 由该顶点指出边的总数.
顶点入度:指向该顶点的边的总数.
一条有向边的第一个顶点叫头,第二个顶点称为尾.(v → w)
一幅有向图的顶点可能存在4种关系:
1.没有边相连接
2.存在v → w
3.存在w → v
4.存在 双向 v ↔ w

4.2.2有向图的数据类型Digraph

package algorithm.algorithmbook.graph;
/**
 * description: 有向图的数据接口
 *
 * @author leon
 * @date 18-2-23.
 */
public interface IDigraph {
    /**
     * @return 顶点数
     */
    int V();
    /**
     * @return 边数
     */
    int E();
    /**
     * 添加 v-> w 的边
     *
     * @param v 起点
     * @param w 终点
     */
    void addEage(int v, int w);
    /**
     * 由v指出所连接的所有顶点
     *
     * @param v 顶点
     * @return 可迭代的顶点列表
     */
    Iterable<Integer> adj(int v);
    /**
     * 这个方法有时很有用,返回的是图的一个副本,但将其中所有的边的方向反向.
     * 因为可以找出"指向"每个顶点的边,而adj()为指出每个顶点的边.
     * @return 该图的反向图
     */
    IDigraph reverse();
    /**
     *
     * @return 字符串描述
     */
    String toString();
}

package algorithm.algorithmbook.graph;
import java.io.DataInputStream;
import algorithm.algorithmbook.graph.IDigraph;
/**
 * description:有向图
 *
 * @author leon
 * @date 18-2-23.
 */
public class Digraph implements IDigraph {
    //顶点数
    private final int v;
    //边数
    private int e;
    //邻接表
    private Bag<Integer>[] adj;
    public Digraph(int v) {
        this.v = v;
        this.e = 0;
        adj = (Bag<Integer>[]) new Bag[v];
        for (int i = 0; i < v; i++) {
            adj[i] = new Bag<Integer>();
        }
    }
    public Digraph(DataInputStream input) {
        v = 0;
    }
    @Override
    public int V() {
        return v;
    }
    @Override
    public int E() {
        return e;
    }
    @Override
    public void addEage(int v, int w) {
        //因为这里是有向图,所以只需要连接 v->w 的边
        adj[v].add(w);
        e++;
    }
    @Override
    public Iterable<Integer> adj(int v) {
        return adj[v];
    }
    @Override
    public IDigraph reverse() {
        Digraph revDigraph = new Digraph(v);
        for (int i = 0; i < v; i++) {
            for (int to : revDigraph.adj(i)) {
                addEage(to, v);
            }
        }
        return revDigraph;
    }
}

4.2.3 有向图的可到达性.

单点可到达性:给定起点s ,是否有到指定顶点v的有向路径.算法和DeepFirstSearch类似.
多点可到达性:给定一个有向图和顶点集合,回答”是否存在一条从集合中任意的顶点到达给定顶点v的有向路径?”等类似问题.

4.2.3-1 标记-清除 的垃圾回收器

多点可到达性的重要实际应用在与 内存管理系统中.对于java 内存,在一个有向图中,对象表示一个顶点,引用表示一条边.这个模型很好的解决了java内存中.定期的进行对有向图的多点可到达性检测,发现有不可到达的顶点进行回收的处理.

4.2.3-2 有向图的寻路

DepthFirstPaths和breadthFirstPaths同样适合有向图.
单点有向图 给定一个有向图和起始顶点:回答”从s到给定目的的顶点v是否存在一条有向路径,如果有找出来”
单点最短有向路径.”从s到给定目的地v是否存在一条路径,如果存在找出其中最短的一条(所含的边最少)”

4.2.4 环和有向无环图

从原则上说,一副有向图可能包含多个有向环,但是实际上我们一般重点关注一小部分,或只想知道他们是否存在.

image.png

4.2.4.1 调度问题

优先级限制条件是调度问题的核心,他指明了哪些任务必须在哪些任务之前完成. 这时候采用有向图的方法来求解调度的顺序就是很不错的.例如下图

image.png
优先级限制下的调度问题: 解决这个问题可以用有向图来模型来表示.等价于 拓扑排序 image.png

拓扑排序: 给定一个有向图,将所有的顶点排序,使得所有的边都是从排在前面的边指向排在后面的边.例如下面下边示意图:

image.png

拓扑排序的典型应用:

应用	顶点	边
任务调度	任务	优先级限制
课程安排	课程	先导课程限制
继承	java类	Extends 关系
符号链接	文件名	链接

4.2.4.2 有向图中的环

在某些特定的有向图依赖关系中是不允许出现环结构的.例如java 类依赖关系.
有向环检测: 如果有环,在所有顶点中按照顺序寻找,返回自己的顶点.即找到了一个有向环.
一幅有向图的环的个数有可能是图大小的指数级别,所以一般情况下只需要找到一个有向环即可判断,而不需要找出所有的环.因此有向无环图就表现的尤为突出.

定义：

有向无环图[DAG （Directed acyclic graph）]就是一副不含环的有向图.

检测是否是有向无环图.采用深度优先搜索.维护一个递归调用栈来记录当前在遍历的有向路径,一旦我们找到了一条边v→ w ,并且w已经存在当前递归栈中,则表示找到了一个有向环,同时如果找不到这样一条边,则说明图是有向无环图.

package algorithm.algorithmbook.graph;
import java.util.Stack;
/**
 * description:寻找有向环
 *
 * @author leon
 * @date 18-2-26.
 */
public class DirectCycle {
    private int[] edgeTo;
    private boolean[] marked;
    //用于存放环的所有顶点,如果存在环
    private Stack<Integer> cycles;
    //递归调用的栈上的所有顶点
    private boolean[] onStack;
    public DirectCycle(Digraph digraph) {
        onStack = new boolean[digraph.V()];
        marked = new boolean[digraph.V()];
        edgeTo = new int[digraph.V()];
        for (int v = 0; v < digraph.V(); v++) {
            if (!marked[v]) {
                dfs(digraph, v);
            }
        }
    }
    private void dfs(Digraph digraph, int v) {
        onStack[v] = true;
        marked[v] = true;
        for (int w : digraph.adj(v)) {
            //特别的处理环的,如果已经找到了环则跳出循环
            if (this.hashCycle()) {
                return;
            }
            //进行深度优先遍历
            if (!marked[w]) {
                edgeTo[w] = v;
                dfs(digraph, w);
            }
            //如果已经marked了,说明已经查找过顶点,也就是出现了环
            else if (onStack[w]) {
                cycles = new Stack<>();
                for (int x = v; x != w; x = edgeTo[x]) {
                    cycles.push(x);
                }
                cycles.push(w);
                cycles.push(v);
            }
            onStack[v] = false;
        }
    }
    public boolean hashCycle() {
        return !cycles.empty();
    }
    public Iterable<Integer> cycle() {
        return cycles;
    }
}

4.2.3.4 顶点的深度优先次序和拓扑排序

命题E:

只有有向无环图才能进行拓扑排序.

实际上我们已经见过一种拓扑排序的算法,只需要添加一行代码就可以由标准的深度优先搜索完成这项任务!引入一种搜索排序,”有向图中基于深度优先的顶点搜索排序”.他的思想是深度优先搜索只会访问所有的顶点一次.遍历这个数据结构实际上能访问图中的所有顶点,而遍历的顺序取决与这个数据结构是递归前还是之后进行保存.一般情况人们关注3中情况:

1.前序遍历 (pre) :在递归前将顶点加入队列

2.后续遍历(post):在递归后将顶点加入队列

3.逆后续(reversePost): 把后续遍历的顺序反转采用栈保存,刚好可以反过来).在递归后将顶点加入栈.

待排序的有向图 image.png

执行深度优先搜索的 3中排序过程:

image.png

package algorithm.algorithmbook.graph;
import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Stack;
/**
 * description:有向图深度优先排序的几种方式
 * <p>
 * 这里根据在递归前,后 进行顶点保存的顺序分成前序,后序,逆后序
 * 1.前序遍历 (pre) :在递归前将顶点加入队列
 * 2.后续遍历(post):在递归后将顶点加入队列
 * 3.逆后续(reversePost): 把后续遍历的顺序反转采用栈保存,刚好可以反过来).在递归后将顶点加入栈.
 *
 * @author leon
 * @date 18-2-27.
 */
public class DirectDeepFirstOrder {
    private boolean[] marked;
    private Queue<Integer> preQ;
    private Queue<Integer> postQ;
    private Stack<Integer> reversePost;
    public DirectDeepFirstOrder(Digraph g) {
        marked = new boolean[g.V()];
        preQ = new ArrayDeque<>();
        postQ = new ArrayDeque<>();
        reversePost = new Stack<>();
        for (int v = 0; v < g.V(); v++) {
            if (!marked[v]) {
                dfs(g, v);
            }
        }
    }
    /**
     * 深度优先遍历递归
     *
     * @param g 图
     * @param v 需要递归的顶点
     */
    private void dfs(Digraph g, int v) {
        preQ.offer(v);
        marked[v] = true;
        for (int w : g.adj(v)) {
            if (!marked[w]) {
                dfs(g, w);
            }
        }
        postQ.offer(v);
        reversePost.push(v);
    }
    /**
     * 前序
     *
     * @return 排序列表
     */
    public Iterable<Integer> pre() {
        return preQ;
    }
    /**
     * 后序
     *
     * @return 排序列表
     */
    public Iterable<Integer> post() {
        return postQ;
    }
    /**
     * 逆后序
     *
     * @return 排序列表
     */
    public Iterable<Integer> reversePost() {
        return reversePost;
    }
}

命题:

一副有向无环图的的拓扑排序即所有顶点的逆后序排序

证明:

对于任意边v→ w,在调用dfs(v)时以下三种情况之一会满足:
1.dfs(w)已经调用过并且已经返回了(w已经被标记了)
2.dfs(w)还没有调用,此时会继续接下来调用dfs(w),并且在 dfs(v)之前调用,并且标记.
3.dfs(w)已经调用并且没有返回.证明的关键在于,需要证明这种情况在有向无环图中是不可能出现的,则可以确定v→ w 的dfs(x) 是有顺序的.因为 如果 dfs(w)已经调用,但是没有返回,则说明有边w→ v存在,然而本身有v→ w ,这样就形成了一个环.与有向无环图有矛盾,故情况3是不存在的.
综上所述:任意一条边的dfs(w) 都会在dfs(v)之前标记,也就是说 在排名靠后w的dfs(w) 比排名靠前v的dfs(v)先标记,把标记列表倒序就得到排名靠前的v→ w的顶点.

package algorithm.algorithmbook.graph;
/**
 * description:拓扑排序
 *
 * @author leon
 * @date 18-2-26.
 */
public class Topological {
    private Iterable<Integer> orderList;
    public Topological(Digraph digraph) {
        DirectCycle directCycle = new DirectCycle(digraph);
        if (!directCycle.hashCycle()) {
            DirectDeepFirstOrder directDeepFirstOrder = new DirectDeepFirstOrder(digraph);
            orderList = directDeepFirstOrder.reversePost();
        }
    }
    /**
     * 是否是有向无环图
     *
     * @return
     */
    public boolean isDAG() {
        return orderList != null;
    }
    /**
     * 拓扑排序
     *
     * @return
     */
    Iterable<Integer> order() {
        return orderList;
    }
    /**
     * test
     *
     * @param args
     */
    public static void main(String[] args) {
        String fileName = args[0];
        String sepatetor = args[1];
        SymbolDirectGraph symbolGraph = new SymbolDirectGraph(fileName, sepatetor);
        Topological topological = new Topological(symbolGraph.graph());
        if (!topological.isDAG()) {
            return;
        }
        for (int v : topological.orderList) {
            //通过索引表来获取图中对应的 名字
            System.out.println(symbolGraph.name(v));
        }
    }
}

命题G:

使用深度优先搜索对无向图进行拓扑排序的所需时间与V+E成正比.

证明:

由代码可知,拓扑排序需要进行两次,1.进行是否有环判断,2 进行逆后序排序. 每次操作都访问了顶点和边,即是V+E 的倍数关系.

4.2.5 有向图中的强连通性

定义:

如果有向图中 w和v 双向可到达即存在v到w的有向路径,也存在w到v的有向路径,称为强连通.如果一副有向图总任意两点之间都是强连通,则称这幅有向图也是强连通的.

两个顶点是强连通.当且仅当他们都是同在一个有向环中.

强连通分量特点:

• 自反性:任意顶点v 和自己都是强连通的.
• 对称性: v和w 是强连通,那么w和v也是强连通
• 传递性: v和w 是强连通,w和x 是强连通.那么v 和x 是强连通.

强连通性将所有顶点分成一些平等的部分,每个部分是由所组成强连通的顶点最大子集组成.把这些最大子集称为强连通分量.包含V个顶点的有向图包含 1-V个强连通分量;一个强连通图只有一个强连通分量(也就是整个图);而一个无环图则包含V个强连通分量(每个顶点都是自己的强连通分量,所以强连通分量就是每个顶点).因为强连通是针对顶点而不是边,所以会出现有些边连接的两个顶点出现在同一个强连通分量中,而有些边连接的两个顶点则出现在不同的强连通分量中.

image.png

4.2.5.2 应用举例

在理解有向图的结构时,强连通性是一个重要的特点.他突出了相互关联的几组顶点(强连通分量).例如强连通分量能够帮组教科书的作者决定那些话题应该归为一类,帮助程序员组织程序的模块;表示哪些食物链中的物种应该在一个生态圈中.
强连通分量API

SCC(digraph G)	构造函数
Boolean stronglyConnetied(int v,int w)	V ,w 是否是强连通
Int count()	强连通分量数
Int id(int v)	V属于哪个强连通分量(0 ~ count-1)

kosaraju算法:

1.在给定有向图G,使用DeepFirstOrder计算他的反向图G^R的逆后序排序.

2.在G图中进行标准的深度优先搜索,但是需要按照刚才计算出的顺序访问所有未标记过的顶点(而非标准的顺序访问).

3.在构造函数中,所有同一个递归dfs()调用中访问到的顶点都在同一个强连通分量中,将他们按照CC的方式识别出来.

强连通性: 回答”给定的两点是强连通的吗? 这幅图中含有多少个强连通分量 ?”

因为 Kosaraju 方法借助了有向图求反向图,然后再计算 逆序排序.

能不能用和 无向图相同的效率解决有向图图的强连通问题.Tarjan提出了一个解决方案.而且这个简单的解决方案令人惊讶.