HI技术分享-数据结构与算法

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

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

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

图片alt

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

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

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

API设计

类名	Digraph
构造方法	Digraph(int V)：创建一个包含V个顶点但不包含边的有向图
成员变量	private final int V：记录顶点的数量 private int E：记录边的数量 private Queue\[] adj：邻接表
成员方法	public int V()：获取图中的顶点数量 public int E()：获取图中边的数量 public void addEdge(int v,int w)：向图中添加一条边v->w public Queue\ adj(int v)：获取和顶点v相连的所有顶点 private Digraph reverse()：该图的反向图

在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、拓扑排序

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

图片alt

4.16.3.1、检测有向图中的环

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

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

类名	DirectedCycle
构造方法	DirectedCycle((Digraph G)：创建一个检测环的对象，检测图G中是否有环
成员变量	private boolean[] marked：索引表示顶点，值表示当前顶点是否已经被搜索 private boolean hasCycle：记录图中是否有环 pirvate boolean[] onStack：索引表示顶点，使用栈的思想，记录当前顶点有没有已经处于正在搜索的有向路径上
成员方法	pirvate void dfs(Digraph G,int v)：基于深度优先搜索，检测图G中是否有环 public boolean hasCycle()：判断图中是有环

实现类

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设计和实现

类名	DepthFirstOrder
构造方法	DepthFirstOrder(Digraph G)：创建一个顶点排序对象，生成顶点线性序列
成员变量	private boolean[] marked：索引表示顶点，值表示当前顶点是否已经被搜索 private Stack\ reverPost：使用栈，存储顶点序列
成员方法	private void dfs(Digraph G,int v)：基于深度优先搜索，生成顶点线性序列 public Stack\ reversePost()：获取顶点线性序列

实现类

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、拓扑排序实现

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

类名	TopoLogical
构造方法	TopoLogical(Digraph G)：构造拓扑排序对象
成员变量	private Stack\ order：顶点的拓扑排序
成员方法	public boolean isCycle()：判断图G是否有环 public Stack\ order()：获取拓扑排序的所有顶点

实现类

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设计

类名	DirectedEdge
构造方法	DirectedEdge(int v,int w,double weight)：通过顶点v和w，以及权重weight值构造一个边对象
成员变量	private final int v：起点 private final int w：终点 private final double weight：当前边的权重
成员方法	public double weight()：获取边的权重值 public int from()：获取有向边的起点 public int to()：获取有向边的终点

实现类

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设计

类名	EdgeWeightedDigraph
构造方法	EdgeWeightedDigraph(int V)：创建一个包含V个顶点的空加权有向图
成员变量	private final int V：顶点数量 print int E：边的条数 private Queue\[] adj：邻接表
成员方法	public int V()：获取图中顶点的数量 public int E()：获取图中边的数量 public void addEdge(DirectedEdge e)：向加权有向图中添加一条边e public Queue\ adj(int v)：获取由顶点v指出的所有边 public Queue\ edges()：获取加权有向图的所有边

实现类

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的路径中总权重最小的那条路径。

图片alt

性质:

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

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

4.16.5.2、最短路径API设计

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

类名	DijkstraSP
构造方法	DijkstraSP(EdgeWeightedDigraph G,int s)：根据一幅加权有向图G和顶点s，创建一个计算顶点为s的最短路径树对象
成员变量	private DirectedEdge[] edgeTo：索引表示顶点，值表示从顶点s到当前顶点的最短路径上的最后一条边 private double[] distTo：索引表示顶点，值从顶点s到当前顶点的最短路径的总权重 private IndexMinPriorityQueue\ pq：存放树中顶点与非树中顶点之间的有效横切边
成员方法	private void relax(EdgeWeightedDigraph G,int v)：松弛图G中的顶点v public double distTo(int v)：从顶点s到顶点v的最短路径的总权重 public boolean hasPathTo(int v)：判断从顶点s到顶点v是否可达 public Queue\ pathTo(int v)：查询从起点s到顶点v的最短路径中的所有边

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的这条边.

图片alt

顶点松弛：

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

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

图片alt

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

4.16、有向图(Digraph)

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

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

4.16.3、拓扑排序

4.16.3.1、检测有向图中的环

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

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

4.16.3.4、拓扑排序实现

4.16.4、加权有向图

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

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

4.16.5、最短路径

4.16.5.1、定义及其性质

4.16.5.2、最短路径API设计

4.16.5.3、松弛技术

4.16.5.4、dijstra算法实现和测试