11.图-有向图

作者：秋刀鱼在做梦 | 2024-07-24 09:44:06

踩

有向图

一、有向图。

二、拓扑排序。

（1）检测有向图中是否有环。

（2）基于深度优先的顶点排序（拓扑排序）。

一、有向图。


package 图的入门.有向图;
 
import 线性表.线性表_队列.Queue;
 
public class Digraph {
    //顶点数目
    private final int V;
    //边的数目
    private int E;
    //邻接表
    private Queue<Integer>[] adj;
 
    public Digraph(int V){
        //初始化顶点数量
        this.V = V;
        //初始化边的数量
        this.E = 0;
        //初始化邻接表
        this.adj = new Queue[V];
        for (int i = 0; i < adj.length; i++) {
            adj[i] = new Queue<>();
        }
    }
 
    //获取顶点数目
    public int V(){
        return V;
    }
 
    //获取边的数目
    public int E(){
        return E;
    }
 
    //向有向图中添加一条边v-》w
    public void addEdge(int v,int w){
        //只需要让顶点w出现在顶点v的邻接表中，因为边是有方向的，最终顶点v的邻接表中存储的相邻顶点的含义是：v-》其他顶点
        adj[v].enqueue(w);
        E++;
    }
 
    //获取由v指出的边所连接的所有顶点
    public Queue<Integer> adj(int v){
        return adj[v];
    }
 
    //获取该图的反向图
    private Digraph reverse(){
        //创建有向图对象
        Digraph r = new Digraph(V);
 
        for (int v = 0; v < V; v++) {//原图中表示的是由顶点v-》w的边
            //获取由该顶点v指出的所有边
            for (Integer w : adj[v]) {
                r.addEdge(w,v);//w->v
            }
        }
        return reverse();
    }
}

二、拓扑排序。

（1）检测有向图中是否有环。


package 图的入门.有向图.图_拓扑排序_检测有向环;
 
import 图的入门.有向图.Digraph;
 
public class DirectedCycle {
    //索引代表顶点，值表示当前顶点是否已经被搜索
    private boolean[] marked;
    //记录图中是否有环
    private boolean hasCycle;
    //索引代表顶点，使用栈的思想，记录当前顶点有没有已经处于正在搜索的有向路径上
    private boolean[] onStack;
 
    //创建一个检测环对象，检测图G中是否有环
    public DirectedCycle(Digraph G){
        //初始化marked数组
        this.marked = new boolean[G.V()];
        //初始化hasCycle
        this.hasCycle = false;
        //初始化onStack数组
        this.onStack = new boolean[G.V()];//基本数据类型都有默认值，这里默认全部为false，引用类型数据默认是null
 
        //找到图中每一个顶点，让每一个顶点作为人口，调用一次dfs进行搜索v
        for (int v = 0; v < G.V(); v++) {
            //判断如果当前结点还没有搜索过(一个连通子图中有一个调用dfs就足够了，但是图不一定就全部相通（连通图），可能有很多连通子图)，则调用dfs进行搜索
            if (!marked[v]){
                dfs(G,v);
            }
        }
    }
 
    //基于深度优先搜索，检测图G中是否有环
    private void dfs(Digraph G,int v){
        //把顶点v表示为已搜索
        marked[v] = true;
        //把当前顶点进栈
        onStack[v] = true;
        //进行深度搜索
        /**
         * 重点注意：这里的增强遍历其实不是拿出就删除了（因为这里是记录结点，然后指向下一个结点，是链表的使用），所以可以一直使用
         * 如果是调用dequeue()方法，那么就会删除
         */
        for (Integer w : G.adj(v)) {
            //如果当前顶点w没有被搜索过，则继续递归调用dfs方法完成深度优先搜索
            if (!marked[w]){
                dfs(G,w);
            }
            //判断当前顶点w是否已经在栈中，如果已经在栈中，证明当前顶点之前处于正在搜索的状态，那么现在又要搜索一次，证明检测到环了
            if (onStack[w]){
                hasCycle = true;
                return;
            }
        }
        //把当前顶点出栈
        onStack[v] = false;
    }
 
    //判断当前有向图G中是否有环
    public boolean hasCycle(){
        return hasCycle;
    }
}

（2）基于深度优先的顶点排序（拓扑排序）。


package 图的入门.有向图.图_拓扑排序_顶点排序;
 
import 图的入门.有向图.Digraph;
import 线性表.线性表_栈.Stack;
 
public class DepthFirstOrder {
    //索引代表顶点，值表示当前顶点是否已经被搜索
    private boolean[] marked;
    //使用栈，存储顶点序列
    private Stack<Integer> reversePost;
 
    //创建一个检测环对象，检测图G中是否有环
    public DepthFirstOrder(Digraph G){
        //初始化marked数组
        this.marked = new boolean[G.V()];
        //初始化reversePost栈
        this.reversePost = new Stack<>();
 
        //遍历图中每一个顶点，让每个顶点作为入口，完成一次深度优先搜索
        for (int v = 0; v < G.V(); v++) {
            if (!marked[v]){
                dfs(G,v);
            }
        }
    }
 
    //基于深度优先搜索，检测图G中是否有环
    private void dfs(Digraph G,int v){
        //标记当前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;
    }
 
}

（3）拓扑排序。


package 图的入门.有向图.图_拓扑排序;
 
import 图的入门.有向图.Digraph;
import 图的入门.有向图.图_拓扑排序_检测有向环.DirectedCycle;
import 图的入门.有向图.图_拓扑排序_顶点排序.DepthFirstOrder;
import 线性表.线性表_栈.Stack;
 
public class TopoLogical {
    //顶点的拓扑排序
    private Stack<Integer> order;
 
    //构造拓扑排序对象
    public TopoLogical(Digraph G){
        /**
         * 虽然下面创建的两个对象都从同一个队列中取出数据
         * 但是使用的是增强for遍历，不会影响队列里面的数据
         */
        //创建一个检测有向环的对象
        DirectedCycle cycle = new DirectedCycle(G);
        //判断G图中有没有环，如果没有环，则进行顶点排序：创建一个顶点排序对象
        if (!cycle.hasCycle()){
            DepthFirstOrder depthFirstOrder = new DepthFirstOrder(G);
            order = depthFirstOrder.reversePost();
        }
    }
 
    //判断G图是否有环
    private boolean isCycle(){
        return order == null;
    }
 
    //获取拓扑排序的所有顶点
    public Stack<Integer> order(){
        return order;
    }
}

测试代码：


package 图的入门.有向图.图_拓扑排序;
 
import 图的入门.有向图.Digraph;
import 线性表.线性表_栈.Stack;
 
public class TopoLogicalTest {
    public static void main(String[] args) {
        //准备有向图
        Digraph digraph = new Digraph(6);
        digraph.addEdge(0,2);
        digraph.addEdge(0,3);
        digraph.addEdge(2,4);
        digraph.addEdge(3,4);
        digraph.addEdge(4,5);
        digraph.addEdge(1,3);
        //通过TopoLogical对象对有向图中的顶点进行排序
        TopoLogical topoLogical = new TopoLogical(digraph);
        //获取顶点的线性序列进行打印
        Stack<Integer> order = topoLogical.order();
        StringBuilder sb = new StringBuilder();
        for (Integer w : order) {
            sb.append(w+"->");
        }
        String str = sb.toString();
        int index = str.lastIndexOf("->");
        str = str.substring(0, index);
        System.out.println(str);
    }
}

三、加权有向图。

（1）加权有向边。


package 图的入门.有向图.加权有向图;
 
public class DirectedEdge {
    private final int v;//起点
    private final int w;//终点
    private final double weight;//当前边的权重
 
    //通过顶点v和w，以及权重weight值构造一个边对象
    public DirectedEdge(int v,int w,double weight){
        this.v = v;
        this.w = w;
        this.weight = weight;
    }
 
    //获取边的权重值
    public double weight(){
        return weight;
    }
 
    //获取有向边的起点
    public int from(){
        return v;
    }
 
    //获取有向边的终点
    public int to(){
        return w;
    }
}

（2）加权有向图。


package 图的入门.有向图.加权有向图;
 
import 线性表.线性表_队列.Queue;
 
public class EdgeWeightedDigraph {
    //顶点总数
    private final int V;
    //边的总数
    private int E;
    //邻接表
    private Queue<DirectedEdge>[] adj;
    
    //创建一个含有V个顶点的空加权有向图
    public EdgeWeightedDigraph(int V){
        //初始化顶点数量
        this.V = V;
        //初始化边的数量
        this.E = 0;
        //初始化邻接表
        this.adj = new Queue[V];
 
        for (int i = 0; i < adj.length; i++) {
            adj[i] = new Queue<>();
        }
    }
    
    //获取图中顶点的数量
    public int V(){
        return V;
    }
    
    //获取图中边的数量
    public int E(){
        return E;
    }
    
    //向加权有向图中添加一条边e
    public void addEdge(DirectedEdge e){
        //边e是有方向的，所以只需要让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 v = 0; v < V; v++) {
            for (DirectedEdge e : adj[v]) {
                allEdges.enqueue(e);
            }
        }
        return allEdges;
    }
    
}

四、最短路径-Dijstra算法。

最小生成树是连接所有的顶点，而最短路径是起点到终点，是一条路径，不需要连接所有顶点，只需要部分顶点。


package 图的入门.有向图.最短路径_Dijstra算法;
 
import 优先队列.IndexMinPrioirityQueue;
import 图的入门.有向图.加权有向图.DirectedEdge;
import 图的入门.有向图.加权有向图.EdgeWeightedDigraph;
import 线性表.线性表_队列.Queue;
 
public class DijstraSP {
    //索引代表顶点，值表示从顶点s到当前顶点的最短路径上的最后一条边
    private DirectedEdge[] edgeTo;
    //索引代表顶点，值从顶点s到当前顶点的最短路径的总权重
    private double[] distTo;
    //存放树中顶点与非树中顶点之间的有向横切边
    private IndexMinPrioirityQueue<Double> pq;
 
    //根据一副加权有向图G和顶点s，创建一个计算顶点s的最短路径树对象
    public DijstraSP(EdgeWeightedDigraph G,int s){
        //初始化edgeTo
        this.edgeTo = new DirectedEdge[G.V()];
        //初始化distTo
        this.distTo = new double[G.V()];
        for (int i = 0; i < distTo.length; i++) {
            distTo[i] = Double.POSITIVE_INFINITY;//double类型的最大值
        }
        //初始化pq
        this.pq = new IndexMinPrioirityQueue<>(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 edge : G.adj(v)) {
            //获取到该边的终点w
            int w = edge.to();
            //通过松弛技术，判断从起点s到顶点w的最短路径是否需要先从顶点s到顶点v，然后再由顶点v到顶点w
            if (distTo[v] + edge.weight() < distTo[w]){//这一步已经将已存在最短路径中的顶点排除了，进不来
                distTo[w] = distTo[v] + edge.weight();
                edgeTo[w] = edge;
                //判断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 edgeTo[v] != null;
        //也可以这样
//        return distTo[v] < Double.POSITIVE_INFINITY;
    }
 
    //查询从起点s到顶点v的最短路径中所有的边
    public Queue<DirectedEdge> pathTo(int v){
        //判断从顶点s到顶点v是否可达，如果不可达，直接返回null
        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 图的入门.有向图.最短路径_Dijstra算法;
 
import 图的入门.有向图.加权有向图.DirectedEdge;
import 图的入门.有向图.加权有向图.EdgeWeightedDigraph;
import 线性表.线性表_队列.Queue;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class DijstraSPTest {
    public static void main(String[] args) throws IOException {
        //创建一副加权有向图
        BufferedReader br = new BufferedReader(new InputStreamReader(DijstraSPTest.class.getClassLoader().getResourceAsStream("min_route_test.txt")));
        int total = Integer.parseInt(br.readLine());
        EdgeWeightedDigraph G = new EdgeWeightedDigraph(total);
        int edgeNubers = Integer.parseInt(br.readLine());
        for (int i = 0; i < edgeNubers; i++) {
            String line = br.readLine();
            String[] str = line.split(" ");
            int v = Integer.parseInt(str[0]);
            int w = Integer.parseInt(str[1]);
            double weight = Double.parseDouble(str[2]);
            //创建加权有向边
            DirectedEdge edge = new DirectedEdge(v, w, weight);
            G.addEdge(edge);
        }
        //创建DijstraSP对象，查找最短路径树
        DijstraSP dijstraSP = new DijstraSP(G, 0);
        //查找最短路径,0->6的最短路径
        Queue<DirectedEdge> edges = dijstraSP.pathTo(6);
        //遍历打印
        for (DirectedEdge edge : edges) {
            System.out.println(edge.from()+"->"+edge.to()+" :: "+edge.weight());
        }
    }
}

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/秋刀鱼在做梦/article/detail/873949