欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Java數(shù)據(jù)結(jié)構(gòu)之加權(quán)無向圖的設(shè)計實現(xiàn)

 更新時間:2022年11月03日 15:37:39   作者:JAVA旭陽  
加權(quán)無向圖是一種為每條邊關(guān)聯(lián)一個權(quán)重值或是成本的圖模型。這種圖能夠自然地表示許多應(yīng)用。這篇文章主要介紹了加權(quán)無向圖的設(shè)計與實現(xiàn),感興趣的可以了解一下

前言

加權(quán)無向圖是一種為每條邊關(guān)聯(lián)一個權(quán)重值或是成本的圖模型。這種圖能夠自然地表示許多應(yīng)用。在一副航空圖中,邊表示航線,權(quán)值則可以表示距離或是費用。在一副電路圖中,邊表示導(dǎo)線,權(quán)值則可能表示導(dǎo)線的長度即成本,或是信號通過這條先所需的時間。此時我們很容易就能想到,最小成本的問題,例如,從西安飛紐約,怎樣飛才能使時間成本最低或者是金錢成本最低?
在下圖中,從頂點0到頂點4有三條路徑,分別為0-2-3-4,0-2-4,0-5-3-4,那我們?nèi)绻ㄟ^那條路徑到達4頂點最好呢?此時就要考慮,那條路徑的成本最低。

邊的表示

加權(quán)無向圖中的邊我們就不能簡單的使用v-w兩個頂點表示了,而必須要給邊關(guān)聯(lián)一個權(quán)重值,因此我們可以使用對象來描述一條邊。

API設(shè)計

類名Edge implements Comparable
成員變量1.private final int v:頂點一2.private final int w:頂點二3.private final double weight:當(dāng)前邊的權(quán)重
構(gòu)造方法Edge(int v,int w,double weight):通過頂點v和w,以及權(quán)重weight值構(gòu)造一個邊對象
成員方法1.public double weight():獲取邊的權(quán)重值2.public int either():獲取邊上的一個點3.public int other(int vertex)):獲取邊上除了頂點vertex外的另外一個頂點4.public int compareTo(Edge that):比較當(dāng)前邊和參數(shù)that邊的權(quán)重,如果當(dāng)前邊權(quán)重大,返回1,如果一樣大,返回0,如果當(dāng)前權(quán)重小,返回-1

代碼實現(xiàn)

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

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

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

    //獲取邊上的一個點
    public int either() {
        return v;
    }

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

    @Override
    public int compareTo(Edge that) {
        //使用一個遍歷記錄比較的結(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;
    }
}

圖的實現(xiàn)

之前我們已經(jīng)完成了無向圖,在無向圖的基礎(chǔ)上,我們只需要把邊的表示切換成Edge對象即可。

API設(shè)計

類名EdgeWeightedGraph
成員變量1.private final int V: 記錄頂點數(shù)量2.private int E: 記錄邊數(shù)量3.private Queue[] adj: 鄰接表
構(gòu)造方法EdgeWeightedGraph(int V):創(chuàng)建一個含有V個頂點的空加權(quán)無向圖
成員方法1.public int V():獲取圖中頂點的數(shù)量2.public int E():獲取圖中邊的數(shù)量3.public void addEdge(Edge e):向加權(quán)無向圖中添加一條邊e4.public Queue adj(int v):獲取和頂點v關(guān)聯(lián)的所有邊5.public Queue edges():獲取加權(quán)無向圖的所有邊

代碼實現(xiàn)

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

    //創(chuàng)建一個含有V個頂點的空加權(quán)無向圖
    public EdgeWeightedGraph(int V) {
        //初始化頂點數(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<>();
        }

    }

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

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


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

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

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

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

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

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

到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之加權(quán)無向圖的設(shè)計實現(xiàn)的文章就介紹到這了,更多相關(guān)Java加權(quán)無向圖內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • SpringBoot中?Jackson?日期的時區(qū)和日期格式問題解決

    SpringBoot中?Jackson?日期的時區(qū)和日期格式問題解決

    因為最近項目需要國際化,需要能夠支持多種國際化語言,目前需要支持三種(法語、英語、簡體中文),這篇文章主要介紹了SpringBoot中?Jackson?日期的時區(qū)和日期格式問題,需要的朋友可以參考下
    2022-12-12
  • Java中excel表數(shù)據(jù)的批量導(dǎo)入方法

    Java中excel表數(shù)據(jù)的批量導(dǎo)入方法

    這篇文章主要為大家詳細介紹了Java中excel表數(shù)據(jù)的批量導(dǎo)入方法,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2018-05-05
  • IDEA中沒有Mapper.xml模板選項的處理方法

    IDEA中沒有Mapper.xml模板選項的處理方法

    這篇文章主要介紹了IDEA中沒有Mapper.xml模板選項的處理方法,需其實解決方法很簡單,只需要在idea中導(dǎo)入模板即可,本文圖文的形式給大家分享解決方法,需要的朋友可以參考下
    2021-04-04
  • 基于Java實現(xiàn)記事本功能

    基于Java實現(xiàn)記事本功能

    這篇文章主要為大家詳細介紹了基于Java實現(xiàn)記事本功能,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2020-12-12
  • Java連接mysql數(shù)據(jù)庫以及mysql驅(qū)動jar包下載和使用方法

    Java連接mysql數(shù)據(jù)庫以及mysql驅(qū)動jar包下載和使用方法

    這篇文章主要給大家介紹了關(guān)于Java連接mysql數(shù)據(jù)庫以及mysql驅(qū)動jar包下載和使用方法,MySQL是一款常用的關(guān)系型數(shù)據(jù)庫,它的JDBC驅(qū)動程序使得我們可以通過Java程序連接MySQL數(shù)據(jù)庫進行數(shù)據(jù)操作,需要的朋友可以參考下
    2023-11-11
  • 一篇文章帶你入門Java基本概念

    一篇文章帶你入門Java基本概念

    本文主要介紹了Java編程的基本概念基本概念,可以幫助我們更加深刻的所要講解的Java命令,具有很好的參考價值。下面跟著小編一起來看下吧,希望能給你帶來幫助
    2021-08-08
  • SpringCloud Alibaba框架介紹

    SpringCloud Alibaba框架介紹

    spring cloud是一個基于springboot實現(xiàn)的微服務(wù)架構(gòu)開發(fā)工具,目前主流的SpringCloud分為SpringCloud Netflix和阿里云開源的SpringCloud Alibaba兩個系列,本文主要介紹SpringCloud Alibaba框架,感興趣的朋友可以參考一下
    2023-04-04
  • springboot實現(xiàn)執(zhí)行sql語句打印到控制臺

    springboot實現(xiàn)執(zhí)行sql語句打印到控制臺

    這篇文章主要介紹了springboot實現(xiàn)執(zhí)行sql語句打印到控制臺的操作,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2021-06-06
  • FastJSON字段智能匹配踩坑的解決

    FastJSON字段智能匹配踩坑的解決

    這篇文章主要介紹了FastJSON字段智能匹配踩坑的解決方案,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教
    2021-06-06
  • SpringBoot熔斷機制之CircuitBreaker詳解

    SpringBoot熔斷機制之CircuitBreaker詳解

    這篇文章主要介紹了SpringBoot熔斷機制之CircuitBreaker詳解,SpringBoot的熔斷機制在微服務(wù)架構(gòu)中扮演著重要角色,其中CircuitBreaker是其核心機制之一,用于防止服務(wù)的異常狀態(tài)影響到整個系統(tǒng)的運作,需要的朋友可以參考下
    2023-10-10

最新評論