/**
 * 邊
 *
 * @author alvin
 * @date 2022/11/3
 * @since 1.0
 **/
public class Edge implements Comparable<Edge> {
    //頂點(diǎn)一
    private final int v;
    //頂點(diǎn)二
    private final int w;
    //當(dāng)前邊的權(quán)重
    private final double weight;

    //通過頂點(diǎn)v和w，以及權(quán)重weight值構(gòu)造一個(gè)邊對(duì)象
    public Edge(int v, int w, double weight) {
        this.v = v;
        this.w = w;
        this.weight = weight;
    }

    //獲取邊的權(quán)重值
    public double weight() {
        return weight;
    }

    //獲取邊上的一個(gè)點(diǎn)
    public int either() {
        return v;
    }

    //獲取邊上除了頂點(diǎn)vertex外的另外一個(gè)頂點(diǎn)
    public int other(int vertex) {
        if (vertex == v) {
            return w;
        } else {
            return v;
        }
    }

    @Override
    public int compareTo(Edge that) {
        //使用一個(gè)遍歷記錄比較的結(jié)果
        int cmp;

        if (this.weight() > that.weight()) {
            //如果當(dāng)前邊的權(quán)重值大，則讓cmp=1；
            cmp = 1;
        } else if (this.weight() < that.weight()) {
            //如果當(dāng)前邊的權(quán)重值小，則讓cmp=-1；
            cmp = -1;
        } else {
            //如果當(dāng)前邊的權(quán)重值和that邊的權(quán)重值一樣大，則讓cmp=0
            cmp = 0;
        }

        return cmp;
    }
}

/**
 * 加權(quán)無向圖的實(shí)現(xiàn)
 *
 * @author alvin
 * @date 2022/11/3
 * @since 1.0
 **/
public class EdgeWeightedGraph {
    //頂點(diǎn)總數(shù)
    private final int V;
    //邊的總數(shù)
    private int E;
    //鄰接表
    private Queue<Edge>[] adj;

    //創(chuàng)建一個(gè)含有V個(gè)頂點(diǎn)的空加權(quán)無向圖
    public EdgeWeightedGraph(int V) {
        //初始化頂點(diǎn)數(shù)量
        this.V = V;
        //初始化邊的數(shù)量
        this.E = 0;
        //初始化鄰接表
        this.adj = new Queue[V];
        for (int i = 0; i < adj.length; i++) {
            adj[i] = new ArrayDeque<>();
        }

    }

    //獲取圖中頂點(diǎn)的數(shù)量
    public int V() {
        return V;
    }

    //獲取圖中邊的數(shù)量
    public int E() {
        return E;
    }


    //向加權(quán)無向圖中添加一條邊e
    public void addEdge(Edge e) {
        //需要讓邊e同時(shí)出現(xiàn)在e這個(gè)邊的兩個(gè)頂點(diǎn)的鄰接表中
        int v = e.either();
        int w = e.other(v);

        adj[v].add(e);
        adj[w].add(e);

        //邊的數(shù)量+1
        E++;
    }

    //獲取和頂點(diǎn)v關(guān)聯(lián)的所有邊
    public Queue<Edge> adj(int v) {
        return adj[v];
    }

    //獲取加權(quán)無向圖的所有邊
    public Queue<Edge> edges() {
        //創(chuàng)建一個(gè)隊(duì)列對(duì)象，存儲(chǔ)所有的邊
        Queue<Edge> allEdges = new ArrayDeque<>();

        //遍歷圖中的每一個(gè)頂點(diǎn)，找到該頂點(diǎn)的鄰接表，鄰接表中存儲(chǔ)了該頂點(diǎn)關(guān)聯(lián)的每一條邊
        //因?yàn)檫@是無向圖，所以同一條邊同時(shí)出現(xiàn)在了它關(guān)聯(lián)的兩個(gè)頂點(diǎn)的鄰接表中，需要讓一條邊只記錄一次；
        for (int v = 0; v < V; v++) {
            //遍歷v頂點(diǎn)的鄰接表，找到每一條和v關(guān)聯(lián)的邊
            for (Edge e : adj(v)) {
                if (e.other(v) < v) {
                    allEdges.add(e);
                }
            }
        }
        return allEdges;
    }
}