Java數(shù)據(jù)結(jié)構(gòu)之加權(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ū)和日期格式問題,需要的朋友可以參考下2022-12-12Java中excel表數(shù)據(jù)的批量導(dǎo)入方法
這篇文章主要為大家詳細介紹了Java中excel表數(shù)據(jù)的批量導(dǎo)入方法,文中示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下2018-05-05Java連接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-11springboot實現(xiàn)執(zhí)行sql語句打印到控制臺
這篇文章主要介紹了springboot實現(xiàn)執(zhí)行sql語句打印到控制臺的操作,具有很好的參考價值,希望對大家有所幫助。如有錯誤或未考慮完全的地方,望不吝賜教2021-06-06SpringBoot熔斷機制之CircuitBreaker詳解
這篇文章主要介紹了SpringBoot熔斷機制之CircuitBreaker詳解,SpringBoot的熔斷機制在微服務(wù)架構(gòu)中扮演著重要角色,其中CircuitBreaker是其核心機制之一,用于防止服務(wù)的異常狀態(tài)影響到整個系統(tǒng)的運作,需要的朋友可以參考下2023-10-10