Java數(shù)據(jù)結(jié)構(gòu)之圖的基礎(chǔ)概念和數(shù)據(jù)模型詳解
圖的實(shí)際應(yīng)用
在現(xiàn)實(shí)生活中,有許多應(yīng)用場(chǎng)景會(huì)包含很多點(diǎn)以及點(diǎn)點(diǎn)之間的連接,而這些應(yīng)用場(chǎng)景我們都可以用即將要學(xué)習(xí)的圖這種數(shù)據(jù)結(jié)構(gòu)去解決。
地圖:
我們生活中經(jīng)常使用的地圖,基本上是由城市以及連接城市的道路組成,如果我們把城市看做是一個(gè)一個(gè)的點(diǎn),把道路看做是一條一條的連接,那么地圖就是我們將要學(xué)習(xí)的圖這種數(shù)據(jù)結(jié)構(gòu)。
圖的定義及分類(lèi)
定義: 圖是由一組頂點(diǎn)和一組能夠?qū)蓚€(gè)頂點(diǎn)相連的邊組成的。
特殊的圖:
- 自環(huán):即一條連接一個(gè)頂點(diǎn)和其自身的邊;
- 平行邊:連接同一對(duì)頂點(diǎn)的兩條邊;
圖的分類(lèi):
按照連接兩個(gè)頂點(diǎn)的邊的不同,可以把圖分為以下兩種:
無(wú)向圖:邊僅僅連接兩個(gè)頂點(diǎn),沒(méi)有其他含義;
有向圖:邊不僅連接兩個(gè)頂點(diǎn),并且具有方向;
圖的相關(guān)術(shù)語(yǔ)
相鄰頂點(diǎn):
當(dāng)兩個(gè)頂點(diǎn)通過(guò)一條邊相連時(shí),我們稱(chēng)這兩個(gè)頂點(diǎn)是相鄰的,并且稱(chēng)這條邊依附于這兩個(gè)頂點(diǎn)。
度:
某個(gè)頂點(diǎn)的度就是依附于該頂點(diǎn)的邊的個(gè)數(shù)
子圖:
是一幅圖的所有邊的子集(包含這些邊依附的頂點(diǎn))組成的圖;
路徑:
是由邊順序連接的一系列的頂點(diǎn)組成
環(huán):
是一條至少含有一條邊且終點(diǎn)和起點(diǎn)相同的路徑
連通圖:
如果圖中任意一個(gè)頂點(diǎn)都存在一條路徑到達(dá)另外一個(gè)頂點(diǎn),那么這幅圖就稱(chēng)之為連通圖
連通子圖:
一個(gè)非連通圖由若干連通的部分組成,每一個(gè)連通的部分都可以稱(chēng)為該圖的連通子圖
圖的存儲(chǔ)結(jié)構(gòu)
要表示一幅圖,只需要表示清楚以下兩部分內(nèi)容即可:
- 圖中所有的頂點(diǎn);
- 所有連接頂點(diǎn)的邊;
常見(jiàn)的圖的存儲(chǔ)結(jié)構(gòu)有兩種:鄰接矩陣和鄰接表。
鄰接矩陣
- 使用一個(gè)V*V的二維數(shù)組int[V][V] adj,把索引的值看做是頂點(diǎn);
- 如果頂點(diǎn)v和頂點(diǎn)w相連,我們只需要將adj[v][w]和adj[w][v]的值設(shè)置為1,否則設(shè)置為0即可。
很明顯,鄰接矩陣這種存儲(chǔ)方式的空間復(fù)雜度是V^2的,如果我們處理的問(wèn)題規(guī)模比較大的話(huà),內(nèi)存空間極有可能不夠用。
鄰接表
1.使用一個(gè)大小為V的數(shù)組 Queue[V] adj,把索引看做是頂點(diǎn);
2.每個(gè)索引處adj[v]存儲(chǔ)了一個(gè)隊(duì)列,該隊(duì)列中存儲(chǔ)的是所有與該頂點(diǎn)相鄰的其他頂點(diǎn)。
很明顯,鄰接表的空間并不是是線性級(jí)別的,所以后面我們一直采用鄰接表這種存儲(chǔ)形式來(lái)表示圖。
圖的實(shí)現(xiàn)
下面通過(guò)代碼實(shí)現(xiàn)一個(gè)無(wú)向圖。
圖的API設(shè)計(jì)
類(lèi)名 | Graph |
---|---|
成員變量 | 1.private final int V: 記錄頂點(diǎn)數(shù)量2.private int E: 記錄邊數(shù)量3.private Queue[] adj: 鄰接表 |
構(gòu)造方法 | Graph(int V):創(chuàng)建一個(gè)包含V個(gè)頂點(diǎn)但不包含邊的圖 |
成員方法 | 1.public int V():獲取圖中頂點(diǎn)的數(shù)量2.public int E():獲取圖中邊的數(shù)量3.public void addEdge(int v,int w):向圖中添加一條邊 v-w4.public Queue adj(int v):獲取和頂點(diǎn)v相鄰的所有頂點(diǎn) |
代碼實(shí)現(xiàn)
/** * 無(wú)向圖的表示 * * @author alvin * @date 2022/10/30 * @since 1.0 **/ public class Graph { //頂點(diǎn)數(shù)目 private final int V; //邊的數(shù)目 private int E; //鄰接表,隊(duì)列的形式 private Queue<Integer>[] adj; public Graph(int V) { // 初始化頂點(diǎn)數(shù)量 this.V = V; //初始化邊的數(shù)量 this.E = 0; //初始化鄰接表 this.adj = new Queue[V]; //初始化鄰接表中的空隊(duì)列 for (int i = 0; i < adj.length; i++) { adj[i] = new ArrayDeque<>(); } } public void addEdge(int v, int w) { //把w添加到v的鏈表中,這樣頂點(diǎn)v就多了一個(gè)相鄰點(diǎn)w adj[v].add(w); //把v添加到w的鏈表中,這樣頂點(diǎn)w就多了一個(gè)相鄰點(diǎn)v adj[w].add(v); //邊的數(shù)目自增1 E++; } //獲取頂點(diǎn)數(shù)目 public int V() { return V; } //獲取邊的數(shù)目 public int E(){ return E; } //獲取和頂點(diǎn)v相鄰的所有頂點(diǎn) public Queue<Integer> adj(int v) { return adj[v]; } }
數(shù)組adj的索引表示頂點(diǎn)。
到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)之圖的基礎(chǔ)概念和數(shù)據(jù)模型詳解的文章就介紹到這了,更多相關(guān)Java數(shù)據(jù)結(jié)構(gòu) 圖內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
關(guān)于MybatisPlus配置雙數(shù)據(jù)庫(kù)驅(qū)動(dòng)連接數(shù)據(jù)庫(kù)問(wèn)題
這篇文章主要介紹了MybatisPlus配置雙數(shù)據(jù)庫(kù)驅(qū)動(dòng)連接數(shù)據(jù)庫(kù)的具體實(shí)現(xiàn),具體的業(yè)務(wù)邏輯,在service層的類(lèi)或者方法上面添加@DataSource注解來(lái)指定該業(yè)務(wù)需要用到的數(shù)據(jù)源,需要的朋友可以參考下2022-01-01一個(gè)通用的Java分頁(yè)基類(lèi)代碼詳解
這篇文章主要介紹了一個(gè)通用的Java分頁(yè)基類(lèi)代碼詳解,具有一定借鑒價(jià)值,需要的朋友可以參考下。2017-12-12java數(shù)據(jù)結(jié)構(gòu)之棧的詳解
這篇文章主要為大家詳細(xì)介紹了Java數(shù)據(jù)結(jié)構(gòu)的棧的應(yīng)用,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能給你帶來(lái)幫助2021-08-08解決redisTemplate向redis中插入String類(lèi)型數(shù)據(jù)時(shí)出現(xiàn)亂碼問(wèn)題
這篇文章主要介紹了解決redisTemplate向redis中插入String類(lèi)型數(shù)據(jù)時(shí)出現(xiàn)亂碼問(wèn)題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2023-12-12Java實(shí)現(xiàn)簡(jiǎn)單的萬(wàn)年歷
這篇文章主要為大家詳細(xì)介紹了Java實(shí)現(xiàn)簡(jiǎn)單的萬(wàn)年歷,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-04-04springIOC的使用流程及spring中使用類(lèi)型轉(zhuǎn)換器的方式
Spring IOC是Spring框架的核心原理之一,它是一種軟件設(shè)計(jì)模式,用于管理應(yīng)用程序中的對(duì)象依賴(lài)關(guān)系,這篇文章主要介紹了springIOC的使用流程以及spring中如何使用類(lèi)型轉(zhuǎn)換器,需要的朋友可以參考下2023-06-06詳解Java設(shè)計(jì)模式編程中命令模式的項(xiàng)目結(jié)構(gòu)實(shí)現(xiàn)
這篇文章主要介紹了Java設(shè)計(jì)模式編程中命令模式的項(xiàng)目結(jié)構(gòu)實(shí)現(xiàn),命令模式將請(qǐng)求與執(zhí)行分離,可以多個(gè)命令接口的實(shí)現(xiàn)類(lèi),隱藏真實(shí)的被調(diào)用方,需要的朋友可以參考下2016-04-04SpringBoot動(dòng)態(tài)修改yml配置文件的方法詳解
這篇文章主要為大家詳細(xì)介紹了SpringBoot動(dòng)態(tài)修改yml配置文件的方法,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來(lái)幫助2022-03-03