內(nèi)容來自尚硅谷Java數(shù)據(jù)結(jié)構(gòu)與java算法（Java數(shù)據(jù)結(jié)構(gòu)與算法）_嗶哩嗶哩_bilibili

寫在前面:本文內(nèi)容大致和原視頻內(nèi)老師的筆記內(nèi)容相同，會偶爾插入自己的注釋和理解，盡量會完成作業(yè)

13.1基本介紹

13.1.1為什么要有圖

1)????? 前面我們學(xué)了線性表和樹

2)????? 線性表局限于一個直接前驅(qū)和一個直接后繼的關(guān)系

3)????? 樹也只能有一個直接前驅(qū)也就是父節(jié)點(diǎn)

4)????? 當(dāng)我們需要表示多對多的關(guān)系時，這里我們就用到了圖

13.1.2圖的舉例說明

圖是一種數(shù)據(jù)結(jié)構(gòu)，其中結(jié)點(diǎn)可以具有零個或多個相鄰元素。兩個結(jié)點(diǎn)之間的連接稱為邊。結(jié)點(diǎn)也可以稱為項點(diǎn)。如圖:

13.1.3圖的常用概念

1)????? 頂點(diǎn)(vertex)

2)????? 邊(edge)

3)????? 路徑

4)????? 無向圖(右圖)

5)????? 有向圖(右圖)

6)????? 帶權(quán)圖

13.2圖的表示方式

圖的表示方式有兩種:二維數(shù)組表示（鄰接矩陣);鏈表表示（鄰接表)。

13.2.1鄰接矩陣

鄰接矩陣是表示圖形中頂點(diǎn)之間相鄰關(guān)系的矩陣，對于n個頂點(diǎn)的圖而言，矩陣是的row和col表示的是1..n個點(diǎn)。

13.2.2鄰接表

1)????? 鄰接矩陣需要為每個頂點(diǎn)都分配n個邊的空間，其實有很多邊都是不存在,會造成空間的一定損失.

2)????? 鄰接表的實現(xiàn)只關(guān)心存在的邊，不關(guān)心不存在的邊。因此沒有空間浪費(fèi)，鄰接表由數(shù)組+鏈表組成

13.3圖的快速入門案例

1)????? 要求：代碼實現(xiàn)如下結(jié)構(gòu)

2)????? 思路分析 (1)存儲頂點(diǎn)String用ArrayList (2)保存矩陣 int[][] edges

3)????? 代碼實現(xiàn)

13.4圖的深度優(yōu)先遍歷介紹

13.4.1圖遍歷介紹

所謂圖的遍歷，即是對結(jié)點(diǎn)的訪問。一個圖有那么多個結(jié)點(diǎn)，如何遍歷這些結(jié)點(diǎn)，需要特定策略，一般有兩種訪問策略:(1深度優(yōu)先遍歷(2)廣度優(yōu)先遍歷

13.4.2深度優(yōu)先遍歷基本思想

?

圖的深度優(yōu)先搜索(Depth First Search)。

1)????? 深度優(yōu)先遍歷，從初始訪問結(jié)點(diǎn)出發(fā)，初始訪問結(jié)點(diǎn)可能有多個鄰接結(jié)點(diǎn)，深度優(yōu)先遍歷的策略就是首先訪問第一個鄰接結(jié)點(diǎn)，然后再以這個被訪問的鄰接結(jié)點(diǎn)作為初始結(jié)點(diǎn)，訪問它的第一個鄰接結(jié)點(diǎn)，可以這樣理解:每次都在訪問完當(dāng)前結(jié)點(diǎn)后首先訪問當(dāng)前結(jié)點(diǎn)的第一個鄰接結(jié)點(diǎn)。

2)????? 我們可以看到，這樣的訪問策略是優(yōu)先往縱向挖掘深入，而不是對一個結(jié)點(diǎn)的所有鄰接結(jié)點(diǎn)進(jìn)行橫向訪問。

3)????? 顯然，深度優(yōu)先搜索是一個遞歸的過程

?

深度優(yōu)先遍歷算法步驟

1)????? 訪問初始結(jié)點(diǎn)v，并標(biāo)記結(jié)點(diǎn)v為已訪問。

2)????? 查找結(jié)點(diǎn)v的第一個鄰接結(jié)點(diǎn)w。

3)????? 若w存在，則繼續(xù)執(zhí)行4，如果w不存在，則回到第1步，將從v的下一個結(jié)點(diǎn)繼續(xù)。

4)????? 若w未被訪問，對w進(jìn)行深度優(yōu)先遍歷遞歸（即把w當(dāng)做另一個v，然后進(jìn)行步驟123）。

5)????? 查找結(jié)點(diǎn)v的w鄰接結(jié)點(diǎn)的下一個鄰接結(jié)點(diǎn)，轉(zhuǎn)到步驟3。

看一個具體的案例：

深度優(yōu)先算法代碼實現(xiàn)

13.5圖的廣度優(yōu)先遍歷

13.5.1廣度優(yōu)先遍歷基本思想

1)????? 圖的廣度優(yōu)先搜索(Broad First Search) .

2)????? 類似于一個分層搜索的過程，廣度優(yōu)先遍歷需要使用一個隊列以保持訪問過的結(jié)點(diǎn)的順序，以便按這個順序來訪問這些結(jié)點(diǎn)的鄰接結(jié)點(diǎn)

13.5.2廣度優(yōu)先遍歷算法步驟

1.????? 訪問初始結(jié)點(diǎn)v并標(biāo)記結(jié)點(diǎn)v為己訪問。

2.????? 結(jié)點(diǎn)v入隊列

3.????? 當(dāng)隊列非空時，繼續(xù)執(zhí)行，否則算法結(jié)束。

4.????? 出隊列，取得隊頭結(jié)點(diǎn)u。

5.????? 查找結(jié)點(diǎn)u的第一個鄰接結(jié)點(diǎn)w。

6.????? 若結(jié)點(diǎn)u的鄰接結(jié)點(diǎn)w不存在，則轉(zhuǎn)到步驟3;否則循環(huán)執(zhí)行以下三個步驟:

6.1 若結(jié)點(diǎn)w尚未被訪問，則訪問結(jié)點(diǎn)w并標(biāo)記為已訪問。

6.2 結(jié)點(diǎn)w入隊列

6.3 查找結(jié)點(diǎn)u的繼w鄰接結(jié)點(diǎn)后的下一個鄰接結(jié)點(diǎn)w，轉(zhuǎn)到步驟6。

13.5.3廣度優(yōu)先算法的圖示

13.6廣度優(yōu)先算法的代碼實現(xiàn)

13.7圖的代碼匯總

13.8圖的深度優(yōu)先VS廣度優(yōu)先

代碼在上面有寫