有向图根无向图的最大区别在于有向图是具有方向的，所以在实现上也会有很大的不同。

4.16.1、有向图定义和相关术语

• 定义：有向图是一幅具有方向性的图，是由一个顶点和一组有方向的边组成的，每条方向的边都连着一对有序的顶点。
• 出度：由某个顶点指出的边的个数被称为该顶点的出度；
• 入度：指向某个顶点的边的个数称为该顶点的入度；
• 有向路径：由一系列顶点组成，对于其中的每个顶点都存在一条有向边，从它指向序列的下一个顶点；
• 有向环：一条至少含有一条边，且起点和终点相同的有向路径；

一幅有向图中两个顶点v和w可能存在的关系：

• 没有边相连
• 存在从v到w的边v->w
• 存在从w到v的边w->v
• 既存在w到v的边，也存在v到w的边，即双向连接

4.16.2、有向图图的API设计和实现

API设计

在api中设计了一个反向图，因为有向图的实现中，用adj方法获取出来的是由当前顶点v指向的其他顶点，如果能得到其反向图，就可以很容易得到指向v的其他顶点。

实现类

package cn.test.algorithm.datastruct;

public class Digraph {
    //顶点的数量
    private final int V;

    //边的条数
    private int E;

    //邻接表
    private Queue<Integer>[] adj;

    public Digraph(int N) {
        this.V = N;
        this.E = 0;
        this.adj = new Queue[N];

        for (int i = 0; i < adj.length; i++) {
            adj[i] = new Queue<Integer>();
        }

    }

    //获取顶点的数量
    public int V() {
        return V;
    }

    //获取边的数量
    public int E() {
        return E;
    }

    //向图中添加一条边v-w
    public void addEdge(int v, int w) {
        //有向图中边是没有方向的，所以如果添加边，那么v中有指向w的边，w中有指向v的边
        adj[v].enqueue(w);//v顶点有指向w的边

        E++;//边的数量加1
    }

    //获取和顶点v相邻的所有顶点
    public Queue<Integer> adj(int v) {
        return adj[v];
    }

    private Digraph reverse() {
        //创建有向图对象
        Digraph digraph = new Digraph(V);

        for (int v = 0; v < V; v++) {
            //获取v顶点指出的所有边
            for (Integer w : adj[v]) {
                digraph.addEdge(w, v);
            }
        }

        return digraph;
    }
}

4.16.3、拓扑排序

给定一幅有向图，将所有的顶点进行排序，使得所有的有向边均从排在前面的元素指向排在后面的元素，此时就可以明确的表示出每个顶点的优先级。如下图：

4.16.3.1、检测有向图中的环

如果我们要使用拓扑排序解决优先级问题，首先要保证图中没有环的存在。

4.16.3.2、检测有向图中的环API设计和实现

实现类

package cn.test.algorithm.datastruct;

public class DirectedCycle {
    //索引表示顶点，值表示当前顶点是否已经被搜索
    private boolean[] marked;

    //记录图中是否有环
    private boolean hasCycle;

    //所以代表顶点，使用栈的思想，记录当前顶点有没有已经处于正在搜索的有向路径上
    private boolean[] onStack;

    //构造
    public DirectedCycle(Digraph G) {
        //初始化
        marked = new boolean[G.V()];

        hasCycle = false;

        onStack = new boolean[G.V()];

        //找到图中每一个顶点，让每一个顶点作为入口，调用一次dfs进行搜索
        for (int v = 0; v < G.V(); v++) {
            //如果当前顶点没有搜索过就需要调用dfs搜索
            if (!marked[v]) {
                dsf(G, v);
            }
        }
    }

    //进行搜索
    private void dsf(Digraph G, int v) {
        //表示v已经被搜索
        marked[v] = true;

        //当前顶点进栈
        onStack[v] = true;

        //进行深度搜索
        for (Integer w : G.adj(v)) {
            //如果没有被搜索就继续搜索
            if (!marked[w]) {
                dsf(G, w);
            }

            //判断当前顶点是否在栈用，如果在栈中，说明当前顶点处于正在搜索的状态
            if (onStack[w]) {
                hasCycle = true;
                return;
            }

        }

        //把当前顶点出栈
        onStack[v] = false;
    }

    //判断当前有向图G中是否有环
    public boolean hasCycle() {
        return hasCycle;
    }
}

4.16.3.3、基于深度优先的顶点排序API设计和实现

实现类

package cn.test.algorithm.datastruct;

public class DepthFirstOrder {
    //索引代表顶点，值表示当前顶点是的已经被搜索
    private boolean[] marked;

    //使用栈，存储顶点的序列
    private Stack<Integer> reversePost;

    public DepthFirstOrder(Digraph G) {
        //初始化
        marked = new boolean[G.V()];
        reversePost = new Stack<>();
        //遍历
        for (int v = 0; v < G.V(); v++) {
            if (!marked[v]) {
                dfs(G, v);
            }
        }
    }

    //进行搜索
    private void dfs(Digraph G, int v) {
        //标记顶点搜索过
        marked[v] = true;

        //通过循环深度搜索顶点v
        for (Integer w : G.adj(v)) {
            if (!marked[w]) {
                dfs(G, w);
            }
        }

        //让顶点v进栈
        reversePost.push(v);
    }

    //获取顶点线性序列
    public Stack<Integer> reversePost() {
        return reversePost;
    }
}

4.16.3.4、拓扑排序实现

前面我们已经实现了有向图的环的检测和顶点排序，那么要实现拓扑排序就很简单了，基于一幅图，先检测有没有环，如果没有环，就调用排序即可。

实现类

package cn.test.algorithm.datastruct;

public class TopoLogical {

    //顶点的拓扑排序
    private Stack<Integer> order;

    //构造对象
    public TopoLogical(Digraph G) {
        //创建一个有向环的对象
        DirectedCycle directedCycle = new DirectedCycle(G);
        //没有环才进行排序
        if (!directedCycle.hasCycle()) {
            DepthFirstOrder depthFirstOrder = new DepthFirstOrder(G);
            order = depthFirstOrder.reversePost();
        }

    }

    //是否有环
    public boolean isCycle() {
        return order == null;
    }

    //获取排序的顶点
    public Stack<Integer> order() {
        return order;
    }
}

测试类

package cn.test.algorithm.test;

import cn.test.algorithm.datastruct.Digraph;
import cn.test.algorithm.datastruct.TopoLogical;

public class TopoLogicalTest {
    public static void main(String[] args) {

        //创建有向图
        Digraph G = new Digraph(6);

        G.addEdge(0, 2);
        G.addEdge(0, 3);

        G.addEdge(1, 3);

        G.addEdge(2, 4);
        G.addEdge(3, 4);

        G.addEdge(4, 5);

        TopoLogical topoLogical = new TopoLogical(G);

        System.out.println("该图是否有环：" + topoLogical.isCycle());


        if (!topoLogical.isCycle()) {
            StringBuilder str = new StringBuilder();
            for (Integer v : topoLogical.order()) {
                str.append(v+"->");
            }
            String s = str.toString();
            int index = s.lastIndexOf("->");
            System.out.println("排序如下："+s.substring(0,index));
        }

    }
}

测试结果

该图是否有环：false
排序如下：1->0->3->2->4->5

4.16.4、加权有向图

4.16.4.1、加权有向图边API设计和实现

API设计

实现类

package cn.test.algorithm.datastruct;

public class DirectedEdge {
    private final int v;//起点
    private final int w;//终点
    private final double weight;//权重

    public DirectedEdge(int v, int w, double weight) {
        this.v = v;
        this.w = w;
        this.weight = weight;
    }

    public double weight() {
        return this.weight;
    }

    public int from() {
        return this.v;
    }

    public int to() {
        return this.w;
    }
}

4.16.4.2、加权有向图API设计和实现

API设计

实现类

package cn.test.algorithm.datastruct;

public class EdgeWeightedDigraph {
    private final int V;//记录顶点

    private int E;//边的数量

    private Queue<DirectedEdge>[] adj;//邻接表

    public EdgeWeightedDigraph(int V) {
        this.V = V;
        this.E = 0;

        this.adj = new Queue[V];
        for (int i = 0; i < this.adj.length; i++) {
            adj[i] = new Queue<DirectedEdge>();
        }
    }


    public int V() {
        return V;
    }

    public int E() {
        return E;
    }

    //添加边
    public void addEdge(DirectedEdge e) {
        int v = e.from();
        adj[v].enqueue(e);

        E++;
    }

    //获取顶点v指出的所有边
    public Queue<DirectedEdge> adj(int v) {
        return adj[v];
    }

    //获取加权有向图中的所有边
    public Queue<DirectedEdge> edges() {
        Queue<DirectedEdge> allEdges = new Queue<>();
        for (int i = 0; i < V; i++) {
            for (DirectedEdge e : adj(i)) {
                allEdges.enqueue(e);
            }
        }
        return allEdges;
    }

}

4.16.5、最短路径

上面我们已经介绍了加权有向图，那么在我们的实际生活中会出现要从A地到B地的最短路径情况。

4.16.5.1、定义及其性质

定义：在一幅加权有向图中，从顶点s到顶点t的最短路径是所有从顶点s到顶点t的路径中总权重最小的那条路径。

性质:

• 路径具有方向性
• 权重不一定等价于距离。权重可以是距离、时间、话费等内容，权重最小指的是成本最低
• 值考虑连通图，非连通图会出现一个顶点到另一个顶点没有路径的情况
• 最短路径不一定是唯一的

最短路径树:给定一幅加权有向图和一个顶点s，以s为起点的一棵最短路径树是图的一幅子图，它包含顶点s以及从s可到达的所有顶点。这棵树有向根结点为s，树的每条路径都是有向图中的一条最短路径。

4.16.5.2、最短路径API设计

计算最短路径的经典算法是dijstra算法，为了实现它，需要先实现如下API

4.16.5.3、松弛技术

松弛这种简单的原理刚好可以用来计算最短路径树。

在我们的API中，需要用两个成员变量edgeTo和distTo，分别存储边和权重。一开始给定的一幅图G和顶点s，我们只知道图的边以及这些边的权重，其他的一无所知，此时初始化顶点s到顶点s的最短路径的总权重distTo[s]=0;顶点s到其他顶点的总权重默认为无穷大，随着算法的执行，不断的使用松弛技术处理图的边和顶点，并按一定的条件更新edgeTo和distTo中的数据，最终可以得到最短路径树。

边的松弛:

放松边v-w意味着检查从s到w的最短路径是否先从s到v，然后再从v到w？

如果是，则v-w这条边需要加入到最短路径树中，更新edgeTo和distTo中国的内容：edget[w]=表示v-w这条边的DirectedEdge对象，distTo[w]=dist[v]+v->w这条边的权重。如果不是，则忽略v->w的这条边.

顶点松弛：

顶点松弛是基于边松弛完成的，只需要把某个顶点指出的所有边松弛，那么该顶点就松弛完毕。例如要松弛顶点v，只需要遍历v的邻接表，把每一条边都松弛，那么顶点v就松弛了。

如果把起点设置为0，那么找出起点0到顶点6的最短路径0->2->7->3->6的过程如下：

4.16.5.4、dijstra算法实现和测试

实现类

package cn.test.algorithm.datastruct;

public class DijkstraSP {

    //索引表示顶点，值表示从顶点s到当前顶点的最短路径上的最后一条边
    private DirectedEdge[] edgeTo;

    //索引表示顶点，值从顶点s到当前顶点的最短路径的总权重
    private double[] distTo;

    //存放树中顶点与非树中顶点之间的有效横切边
    private IndexMinPriorityQueue<Double> pq;

    //根据一幅加权有向图G和顶点s，创建一个计算顶点为s的最短路径树对象
    public DijkstraSP(EdgeWeightedDigraph G, int s) {
        //初始edgeTo
        this.edgeTo = new DirectedEdge[G.V()];
        //初始distTo
        this.distTo = new double[G.V()];
        for (int i = 0; i < this.distTo.length; i++) {
            this.distTo[i] = Double.POSITIVE_INFINITY;
        }
        //初始pq
        this.pq = new IndexMinPriorityQueue<Double>(G.V());

        //找到图G中找到顶点s的最近路径树
        //默认让顶点s进入到最短路径树中
        distTo[s] = 0.0;

        pq.insert(s, 0.0);

        //遍历pq
        while (!pq.isEmpty()) {
            relax(G, pq.delMin());
        }
    }

    //松弛图G中的顶点v
    private void relax(EdgeWeightedDigraph G, int v) {
        for (DirectedEdge e : G.adj(v)) {
            //获取边的终点w
            int w = e.to();
            //通过松弛技术，判断从起点s到顶点w的最短路径是否需要先从顶点s到顶点w，然后再由顶点v到顶点w
            if (distTo(v) + e.weight() < distTo(w)) {
                distTo[w] = distTo[v] + e.weight();
                edgeTo[w] = e;

                //判断pq中是否已经存在顶点w，如果存在更新权重，如果不存在则直接添加
                if (pq.contains(w)) {
                    pq.changeItem(w, distTo(w));
                } else {
                    pq.insert(w, distTo(w));
                }
            }
        }
    }

    //从顶点s到顶点v的最短路径的总权重
    public double distTo(int v) {
        return distTo[v];
    }

    //判断从顶点s到顶点v是否可达
    public boolean hasPathTo(int v) {
        return distTo[v] < Double.POSITIVE_INFINITY;
    }

    //查询从起点s到顶点v的最短路径中的所有边
    public Queue<DirectedEdge> pathTo(int v) {
        //先判断是否可达
        if (!hasPathTo(v)) {
            return null;
        }

        Queue<DirectedEdge> allEdges = new Queue<>();
        while (true) {
            DirectedEdge e = edgeTo[v];
            if (e == null) {
                break;
            }
            allEdges.enqueue(e);
            v = e.from();
        }
        return allEdges;
    }
}

测试类

package cn.test.algorithm.test;

import cn.test.algorithm.datastruct.DijkstraSP;
import cn.test.algorithm.datastruct.DirectedEdge;
import cn.test.algorithm.datastruct.EdgeWeightedDigraph;
import cn.test.algorithm.datastruct.Queue;

public class DijkstraSPTest {
    public static void main(String[] args) {
        //创建一幅加权有向图
        EdgeWeightedDigraph G = new EdgeWeightedDigraph(8);

        G.addEdge(new DirectedEdge(4, 5, 0.35));
        G.addEdge(new DirectedEdge(5, 4, 0.35));
        G.addEdge(new DirectedEdge(4, 7, 0.37));
        G.addEdge(new DirectedEdge(5, 7, 0.28));
        G.addEdge(new DirectedEdge(7, 5, 0.28));
        G.addEdge(new DirectedEdge(5, 1, 0.32));
        G.addEdge(new DirectedEdge(0, 4, 0.38));
        G.addEdge(new DirectedEdge(0, 2, 0.26));
        G.addEdge(new DirectedEdge(7, 3, 0.39));
        G.addEdge(new DirectedEdge(1, 3, 0.29));
        G.addEdge(new DirectedEdge(2, 7, 0.34));
        G.addEdge(new DirectedEdge(6, 2, 0.40));
        G.addEdge(new DirectedEdge(3, 6, 0.52));
        G.addEdge(new DirectedEdge(6, 0, 0.58));
        G.addEdge(new DirectedEdge(6, 4, 0.93));
        //创建DijkstraSP，查找最短路径
        DijkstraSP dijkstraSP = new DijkstraSP(G, 0);

        boolean b = dijkstraSP.hasPathTo(6);
        System.out.println("顶点0到顶点6是否可达：" + b);
        if (b) {
            System.out.println("顶点0到顶点6的总权重：" + dijkstraSP.distTo(6));
            Queue<DirectedEdge> directedEdges = dijkstraSP.pathTo(6);
            System.out.println("顶点0到顶点6的路径为：");
            for (DirectedEdge directedEdge : directedEdges) {
                System.out.println(directedEdge.from() + " " + directedEdge.to() + " " + directedEdge.weight());
            }

        }

    }
}

测试结果

顶点0到顶点6是否可达：true
顶点0到顶点6的总权重：1.5100000000000002
顶点0到顶点6的路径为：
3 6 0.52
7 3 0.39
2 7 0.34
0 2 0.26