前言

本文主要講解 數(shù)據(jù)結(jié)構(gòu)中的圖 結(jié)構(gòu)，包括 深度優(yōu)先搜索（DFS）、廣度優(yōu)先搜索（BFS）、最小生成樹(shù)算法等，希望你們會(huì)喜歡。

---

目錄

---

1. 簡(jiǎn)介

• 數(shù)據(jù)結(jié)構(gòu)的中屬于 圓形結(jié)構(gòu) 的邏輯結(jié)構(gòu)
• 具體介紹如下

---

2. 基礎(chǔ)概念

• 在圖的數(shù)據(jù)結(jié)構(gòu)中，有許多基礎(chǔ)概念，如 邊類型、圖頂點(diǎn) & 邊間的關(guān)系等等
• 具體請(qǐng)看下圖

---

3. 類型

圖的類型分為很多種，具體如下：

3.1 有向圖 & 無(wú)向圖

3.2 連通圖

• 定義
  圖中任意頂點(diǎn)都是連通的圖

• 具體相關(guān)概念
  對(duì)于有向圖 & 無(wú)向圖，連通圖的的具體概念又不同，具體如下

對(duì)于無(wú)向圖：

對(duì)于有向圖：

3.3 其余類型圖

---

4. 存儲(chǔ)結(jié)構(gòu)

圖的存儲(chǔ)結(jié)構(gòu)共有5種，具體請(qǐng)看下圖

---

5. 圖的遍歷

數(shù)據(jù)結(jié)構(gòu)：圖文詳解二叉樹(shù)（遍歷、類型、操作）

5.1 定義

從圖中某1頂點(diǎn)出發(fā)，遍歷圖中其余所有頂點(diǎn) & 使每1個(gè)頂點(diǎn)僅被訪問(wèn)1次

5.2 遍歷方式

深度優(yōu)先遍歷（DFS）、廣度優(yōu)先遍歷（BFS）

5.3 具體介紹

5.3.1 深度優(yōu)先遍歷（ DFS ）

• 簡(jiǎn)介

• 算法示意圖

• 具體實(shí)現(xiàn)：遞歸 & 非遞歸

此處圖的存儲(chǔ)結(jié)構(gòu) = 鄰接矩陣

import java.util.Stack;public class MyGraph {/*** 準(zhǔn)備工作1：設(shè)置變量*/private int vexnum; // 存放圖中頂點(diǎn)數(shù)量private char[] vertices; // 存放結(jié)點(diǎn)數(shù)據(jù)private int [][] arcs; // 存放圖的所有邊private boolean[] visited;// 記錄節(jié)點(diǎn)是否已被遍歷/*** 準(zhǔn)備工作2：初始化圖的頂點(diǎn)數(shù)量、數(shù)據(jù) & 邊*/public MyGraph(int n){vexnum = n;vertices = new char[n];visited = new boolean[n];arcs = new int[n][n];}/*** 圖的深度優(yōu)先遍歷算法實(shí)現(xiàn)：遞歸* 類似 前序遍歷*/public void DFSTraverse(){// 1. 初始化所有頂點(diǎn)的訪問(wèn)標(biāo)記// 即，都是未訪問(wèn)狀態(tài)for (int i = 0; i < vexnum; i++) {visited[i] = false;}// 2. 深度優(yōu)先遍歷頂點(diǎn)（從未被訪問(wèn)的頂點(diǎn)開(kāi)始）for(int i=0;i < vexnum;i++){if(visited[i]==false){// 若是連通圖，只會(huì)執(zhí)行一次traverse(i); // ->>看關(guān)注1}}}/*** 關(guān)注1：鄰接矩陣的深度優(yōu)先搜索遞歸算法* 即，從第i個(gè)頂點(diǎn)開(kāi)始深度優(yōu)先遍歷*/private void traverse(int i){// 1. 標(biāo)記第i個(gè)頂點(diǎn)已遍歷visited[i] = true;// 2. （輸出）訪問(wèn)當(dāng)前遍歷的頂點(diǎn)visit(i);// 3. 遍歷鄰接矩陣中第i個(gè)頂點(diǎn)的所有鄰接頂點(diǎn)for(int j=0;j<vexnum;j++){// a. 若當(dāng)前頂點(diǎn)的鄰接頂點(diǎn)存在 & 未被訪問(wèn)，則遞歸 深度優(yōu)先搜索 算法if(arcs[i][j]==1 && visited[j]==false){// b. 將當(dāng)前頂點(diǎn)的鄰接頂點(diǎn)作為當(dāng)前頂點(diǎn)，遞歸 深度優(yōu)先搜索 算法traverse(j);}}}/*** 輔助算法1：訪問(wèn)頂點(diǎn)值*/public void visit(int i){System.out.print(vertices[i] + " ");}/*** 圖的深度優(yōu)先遍歷算法實(shí)現(xiàn)：非遞歸* 原理：采用 棧實(shí)現(xiàn)*/public void DFSTraverse2(){// 1. 初始化頂點(diǎn)訪問(wèn)標(biāo)記// 全部標(biāo)記為：未訪問(wèn)for (int i = 0; i < vexnum; i++) {visited[i] = false;}// 2. 創(chuàng)建棧Stack<Integer> s = new Stack<Integer>();for(int i=0 ; i<vexnum; i++){// 3. 若該頂點(diǎn)未被訪問(wèn)if(!visited[i]){// 4. 入棧該頂點(diǎn)s.add(i);do{// 出棧int curr = s.pop();// 如果該節(jié)點(diǎn)還沒(méi)有被遍歷，則遍歷該節(jié)點(diǎn)并將子節(jié)點(diǎn)入棧if(visited[curr]==false){// 遍歷并打印visit(curr);visited[curr] = true;// 沒(méi)遍歷的子節(jié)點(diǎn)入棧for(int j=vexnum-1; j>=0 ; j-- ){if(arcs[curr][j]==1 && visited[j]==false){s.add(j);}}}}while(!s.isEmpty());}}}/*** 測(cè)試（遞歸 & 非遞歸）*/public static void main(String[] args) {// 1. 初始化圖的結(jié)構(gòu)（頂點(diǎn)數(shù)量 = 9）MyGraph g = new MyGraph(9);// 2. 設(shè)置頂點(diǎn)數(shù)據(jù)char[] vertices = {'A','B','C','D','E','F','G','H','I'};g.setVertices(vertices);// 3. 設(shè)置邊g.addEdge(0, 1);g.addEdge(0, 5);g.addEdge(1, 0);g.addEdge(1, 2);g.addEdge(1, 6);g.addEdge(1, 8);g.addEdge(2, 1);g.addEdge(2, 3);g.addEdge(2, 8);g.addEdge(3, 2);g.addEdge(3, 4);g.addEdge(3, 6);g.addEdge(3, 7);g.addEdge(3, 8);g.addEdge(4, 3);g.addEdge(4, 5);g.addEdge(4, 7);g.addEdge(5, 0);g.addEdge(5, 4);g.addEdge(5, 6);g.addEdge(6, 1);g.addEdge(6, 3);g.addEdge(6, 5);g.addEdge(6, 7);g.addEdge(7, 3);g.addEdge(7, 4);g.addEdge(7, 6);g.addEdge(8, 1);g.addEdge(8, 2);g.addEdge(8, 3);// 4. 執(zhí)行 圖的深度優(yōu)先遍歷：（遞歸 & 非遞歸）System.out.println("深度優(yōu)先遍歷（遞歸）");g.DFSTraverse();System.out.println("深度優(yōu)先遍歷（非遞歸）");g.DFSTraverse2();}/*** 輔助算法1：添加邊(無(wú)向圖)*/public void addEdge(int i, int j) {// 邊的頭尾不能為同一節(jié)點(diǎn)if (i == j) return;// 將鄰接矩陣的第i行第j列的元素值置為1；arcs[i][j] = 1;// 將鄰接矩陣的第j行第i列的元素值置為1；arcs[j][i] = 1;// 設(shè)置為1代表2頂點(diǎn)之間存在 邊 （設(shè)置相等原因 = 鄰接矩陣 是對(duì)稱的）}/*** 輔助算法2：設(shè)置頂點(diǎn)數(shù)據(jù)*/public void setVertices(char[] vertices) {this.vertices = vertices;} }

• 測(cè)試結(jié)果

深度優(yōu)先遍歷（遞歸） A B C D E F G H I 深度優(yōu)先遍歷（非遞歸） A B C D E F G H I

• 特別注意
  對(duì)于圖的存儲(chǔ)結(jié)構(gòu) = 鄰接表實(shí)現(xiàn)，只需要將 存儲(chǔ)邊 的2維數(shù)組 改成鏈表即可。

• 圖的存儲(chǔ)結(jié)構(gòu) = 鄰接矩陣 / 鄰接表 的性能對(duì)比

5.3.2 廣度優(yōu)先遍歷（BFS）

• 簡(jiǎn)介

• 算法示意圖

• 具體流程

注：G 比 I 先訪問(wèn)的原因 = 用數(shù)組存儲(chǔ)頂點(diǎn)時(shí)，G的下標(biāo) 比 I的下標(biāo)小（按ABCDEFGHI順序存儲(chǔ)）

• 具體實(shí)現(xiàn)

非遞歸：采用隊(duì)列

import java.util.LinkedList; import java.util.Queue; import java.util.Stack;public class MyGraph {/*** 準(zhǔn)備工作1：設(shè)置變量*/private int vexnum; // 存放圖中頂點(diǎn)數(shù)量private char[] vertices; // 存放結(jié)點(diǎn)數(shù)據(jù)private int [][] arcs; // 存放圖的所有邊private boolean[] visited;// 記錄節(jié)點(diǎn)是否已被遍歷/*** 準(zhǔn)備工作2：初始化圖的頂點(diǎn)數(shù)量、數(shù)據(jù) & 邊*/public MyGraph(int n){vexnum = n;vertices = new char[n];visited = new boolean[n];arcs = new int[n][n];}/*** 廣度優(yōu)先搜索 算法實(shí)現(xiàn)* 原理：非遞歸（采用隊(duì)列）*/public void BFS(){// 1. 初始化所有頂點(diǎn)的訪問(wèn)標(biāo)記// 即，設(shè)置為未訪問(wèn)狀態(tài)for (int i = 0; i < vexnum; i++) {visited[i] = false;}// 2. 創(chuàng)建隊(duì)列Queue<Integer> q=new LinkedList<Integer>();// 3. 對(duì)所有頂點(diǎn)做遍歷循環(huán)（從第1個(gè)頂點(diǎn)開(kāi)始）// 若遍歷完畢，則結(jié)束整個(gè)層序遍歷for(int i=0;i < vexnum;i++){// 4. 若當(dāng)前頂點(diǎn)未被訪問(wèn)，就進(jìn)行處理// 若當(dāng)前頂點(diǎn)已被訪問(wèn)，則回到3進(jìn)行判斷if( visited[i]==false ) {// 5. （輸出）訪問(wèn)當(dāng)前頂點(diǎn)visit(i);// 6. 標(biāo)記當(dāng)前頂點(diǎn)已被訪問(wèn)visited[i] = true;// 7. 入隊(duì)當(dāng)前頂點(diǎn)q.add(i);// 8.判斷當(dāng)前隊(duì)列是否為空// 若為空則跳出循環(huán)，回到3進(jìn)行判斷while(!q.isEmpty()) {// 9. 出隊(duì)隊(duì)首元素 & 將出隊(duì)的元素 賦值為 當(dāng)前頂點(diǎn)i = q.poll();// 10. 遍歷當(dāng)前頂點(diǎn)的所有鄰接點(diǎn)// 若遍歷完畢，則回到8判斷for(int j=0; j< vexnum ; j++){// 11. 若當(dāng)前頂點(diǎn)的鄰接頂點(diǎn)存在 & 未被訪問(wèn)，則執(zhí)行處理// 否則回到10判斷if(arcs[i][j]==1 && visited[j]==false){// 12. （輸出）訪問(wèn)當(dāng)前頂點(diǎn)的鄰接頂點(diǎn)visit(j);// 13. 標(biāo)記當(dāng)前頂點(diǎn)的鄰接頂點(diǎn)已被訪問(wèn)visited[j] = true;// 14. 入隊(duì)當(dāng)前頂點(diǎn)的鄰接頂點(diǎn)q.add(j);}}}}}}/*** 輔助算法1：訪問(wèn)該頂點(diǎn)*/public void visit(int i){System.out.print(vertices[i] + " ");}/** * 測(cè)試算法*/public static void main(String[] args) {// 1. 初始化圖的結(jié)構(gòu)（頂點(diǎn)數(shù)量 = 9MyGraph g = new MyGraph(9);// 2. 設(shè)置頂點(diǎn)數(shù)據(jù)char[] vertices = {'A','B','C','D','E','F','G','H','I'};g.setVertices(vertices);// 3. 設(shè)置邊g.addEdge(0, 1);g.addEdge(0, 5);g.addEdge(1, 0);g.addEdge(1, 2);g.addEdge(1, 6);g.addEdge(1, 8);g.addEdge(2, 1);g.addEdge(2, 3);g.addEdge(2, 8);g.addEdge(3, 2);g.addEdge(3, 4);g.addEdge(3, 6);g.addEdge(3, 7);g.addEdge(3, 8);g.addEdge(4, 3);g.addEdge(4, 5);g.addEdge(4, 7);g.addEdge(5, 0);g.addEdge(5, 4);g.addEdge(5, 6);g.addEdge(6, 1);g.addEdge(6, 3);g.addEdge(6, 5);g.addEdge(6, 7);g.addEdge(7, 3);g.addEdge(7, 4);g.addEdge(7, 6);g.addEdge(8, 1);g.addEdge(8, 2);g.addEdge(8, 3);// 4. 執(zhí)行 圖的廣度優(yōu)先遍歷（非遞歸）System.out.print("廣度優(yōu)先遍歷（非遞歸）：");g.BFS();}/*** 輔助算法1：添加邊(無(wú)向圖)*/public void addEdge(int i, int j) {// 邊的頭尾不能為同一節(jié)點(diǎn)if (i == j) return;// 將鄰接矩陣的第i行第j列的元素值置為1；arcs[i][j] = 1;// 將鄰接矩陣的第j行第i列的元素值置為1；arcs[j][i] = 1;// 設(shè)置為1代表2頂點(diǎn)之間存在 邊 （設(shè)置相等原因 = 鄰接矩陣 是對(duì)稱的）}/*** 輔助算法2：設(shè)置頂點(diǎn)數(shù)據(jù)*/public void setVertices(char[] vertices) {this.vertices = vertices;}}

• 執(zhí)行結(jié)果

廣度優(yōu)先遍歷（非遞歸）：A B F C G I E D H

5.4 遍歷方式對(duì)比

---

6. 最小生成樹(shù)

本節(jié)主要講解 圖中的 最小生成樹(shù)

6.1 定義

構(gòu)造 連通網(wǎng)圖 的最小成本生成樹(shù)

網(wǎng)圖：帶有權(quán)值的圖

最小成本：用（n-1）條邊將 含n個(gè)頂點(diǎn)的連通圖 連接起來(lái) & 使得權(quán)值和最小

6.2 尋找最小生成樹(shù)的算法

• 主要包括：（Prim）普利姆算法 & （Kruskal）克魯斯卡爾算法
• 具體介紹如下

6.2.1 （Prim）普利姆算法

• 算法概述

• 算法原理流程示意圖

• 舉例說(shuō)明

6.2.2（Kruskal）克魯斯卡爾算法

• 算法概述

6.3 算法對(duì)比

---

7. 最短路徑

7.1 定義

• 對(duì)于非網(wǎng)圖（無(wú)權(quán)值），最短路徑 = 兩頂點(diǎn)間經(jīng)過(guò)的邊數(shù)最少的路徑
• 對(duì)于網(wǎng)圖（有權(quán)值）：最短路徑 = 兩頂點(diǎn)間經(jīng)過(guò)的邊上權(quán)值和最少的路徑

第1個(gè)頂點(diǎn) = 源點(diǎn)、第2個(gè)頂點(diǎn) = 終點(diǎn)

7.2 需解決的問(wèn)題

從源點(diǎn) -> 其余各頂點(diǎn)的最短路徑

7.3 尋找最短路徑 算法

• 主要包括：迪杰斯特拉算法（Dijkstra）、弗洛伊德算法（Floyd）

• 具體介紹如下

---

8. 總結(jié)

• 本文主要講解了數(shù)據(jù)結(jié)構(gòu)中的圖
• 下面我將繼續(xù)對(duì) 數(shù)據(jù)結(jié)構(gòu)，有興趣可以繼續(xù)關(guān)注Carson_Ho的安卓開(kāi)發(fā)筆記

---

幫頂 / 評(píng)論點(diǎn)贊！因?yàn)槟愕墓膭?lì)是我寫(xiě)作的最大動(dòng)力！

總結(jié)

以上是生活随笔為你收集整理的Carson带你学数据结构：手把手带你了解 ”图“ 所有知识！(含DFS、BFS）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。