加权有向图的实现

导读:本篇文章讲解 加权有向图的实现,希望对大家有帮助,欢迎收藏,转发!站点地址:www.bmabk.com

一.概述

之前学习的加权无向图中,边是没有方向的,并且同一条边会同时出现在该边的两个顶点的邻接表中;而在加权有向图中,边只出现在起点的邻接表中!

二.实现

加权有向边:
在这里插入图片描述

//加权有向边
public class DirectedEdge implements Comparable<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 v;
    }

    public int to(){ //返回终点
        return w;
    }

    @Override
    public int compareTo(DirectedEdge o) {
        int r = 0;
        if (this.weight() > o.weight()) {
            r = 1;
        } else if (this.weight() < o.weight()) {
            r = -1;
        } else if (this.weight() == o.weight()) {
            r = 0;
        }
        return r;
    }
}

加权有向图:
在这里插入图片描述

//加权有向图
class EdgeWeightedDigragh{
    private final int V;
    private int E;
    private Queue<DirectedEdge>[] adj;
    //邻接表的索引表示顶点,索引的队列表示由该顶点指出的边!有向图中,该边只出现在起点的邻接表即可。

    public int V(){
        return V;
    }

    public int E(){
        return E;
    }

    //初始化一个含有v个顶点的空加权有向图
    public EdgeWeightedDigragh(int v) {
        this.V = v;
        this.E=0;
        this.adj=new LinkedList[v];
        for(int i=0;i<v;i++){
            adj[i]=new LinkedList<>();
        }
    }

    public void add(DirectedEdge e){
        //边e是有方向的!只需要让e出现在起点的邻接表!
        int v = e.from(); //获取起点v
        adj[v].add(e);  //添加至v的邻接表
        this.E++;
    }

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

    public Queue<DirectedEdge> edges(){ //获取所有的边
        Queue<DirectedEdge> allEdges=new LinkedList<>();
        for(int i=0;i<this.V;i++){ //遍历每一个队列
            for(DirectedEdge k:adj[i]){  //将队列中每个DirectedEdge添加至edges队列
                allEdges.add(k);
            }
        }
        return allEdges;
    }

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

文章由半码博客整理,本文链接:https://www.bmabk.com/index.php/post/89347.html

(0)

相关推荐

半码博客——专业性很强的中文编程技术网站,欢迎收藏到浏览器,订阅我们!