博客

所谓加权无向图，就是给连接两个顶点的边赋一个值。这在日常生活中有非常广泛的应用，例如：查找两地间用时最短的火车票，或者金钱成本最低的飞机票。

1.1 加强无向图边

构造方法

 private int v;
    private int w;
    private double weight;
    //获取边上的权重值
    public double getWeight(){
        return weight;
    }
    //获取边上一个点
    public int either(){
        return v;
    }
    //获取边上的另外一个顶点
    public int other(int vertex){
        if (vertex==v){
            return w;
        }
        else{
            return v;
        }
    }

比较两个加权边的大小

public int compareTo(Edge that) {
        int cmp;
        //如果当前边的权重值大，则cmp=1；
        if(this.getWeight()>that.getWeight()){
            cmp=1;
        } else if(this.getWeight()<that.getWeight()){
           // 如果当前边的权重值小，则cmp=-1；
            cmp=-1;
        }else{
        //如果一样大。则cmp=0
            cmp=0;
        }
        return cmp;
    }

加权边的完整代码

public class Edge implements Comparable<Edge>{
    private int v;
    private int w;
    private double weight;
    //获取边上的权重值
    public double getWeight(){
        return weight;
    }
    //获取边上一个点
    public int either(){
        return v;
    }
    //获取边上的另外一个顶点
    public int other(int vertex){
        if (vertex==v){
            return w;
        }
        else{
            return v;
        }
    }
    @Override
    public int compareTo(Edge that) {
        int cmp;
        //如果当前边的权重值大，则cmp=1；
        if(this.getWeight()>that.getWeight()){
            cmp=1;
        } else if(this.getWeight()<that.getWeight()){
           // 如果当前边的权重值小，则cmp=-1；
            cmp=-1;
        }else{
        //如果一样大。则cmp=0
            cmp=0;
        }
        return cmp;
    }
}

1.2 加权无向图

构造方法

//顶点数目
    private final int V;
    //边的数目
    private int E;
    //邻接表
    private Queue<Edge>[] adj;
    public EdgeWeightedGraph(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<Edge>();
        }
    }

获取图中所有的边

public Queue<Edge> edge(){
        //创建一个队列对象，存储所有的边
        Queue<Edge> alledges = new Queue<>();
        //遍历图中的每一个顶点，找到邻接表，把边放在队列中

        //因为是无向图，每一条边被记录两次，我们需让他只记录一次
        for (int v=0;v<V;v++){
            for (Edge e : adj(v)) {
              if (e.other(v)<v){
                  alledges.enqueue(e);
              }
            }
        }
        return alledges;
    }

加权无向图完整代码

public class EdgeWeightedGraph {
    //顶点数目
    private final int V;
    //边的数目
    private int E;
    //邻接表
    private Queue<Edge>[] adj;
    public EdgeWeightedGraph(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<Edge>();
        }
    }

    //获取顶点数目
    public int getV(){
        return  V;
    }
    //获取边的数目
    public int getE(){
        return E;
    }
    //向图中添加一条边
    public void addEdge(Edge e){
        int v = e.either();
        int w = e.other(v);
        adj[v].enqueue(e);
        adj[w].enqueue(e);
        //边的数量加一
        E++;
    }
    //获取和顶点v相邻的所有边
    public Queue<Edge> adj(int  v){
         return adj[v];
    }
    //获取加权无向图中所有的边
    public Queue<Edge> edge(){
        //创建一个队列对象，存储所有的边
        Queue<Edge> alledges = new Queue<>();
        //遍历图中的每一个顶点，找到邻接表，把边放在队列中

        //因为是无向图，每一条边被记录两次，我们需让他只记录一次
        for (int v=0;v<V;v++){
            for (Edge e : adj(v)) {
              if (e.other(v)<v){
                  alledges.enqueue(e);
              }
            }
        }
        return alledges;
    }
}

b站详细讲解网址：http://yun.itheima.com/course/639.html