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

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