學習地址：【數據結構與算法基礎-java版】? ? ? ? ? ? ? ? ??🚀數據結構--Java專欄🚀

• 筆記01【01-09】【概述、數組基本使用】【源碼、課件】
• 筆記02【10-18】【棧、隊列、單鏈表(增刪節點)、循環鏈表、雙向循環鏈表、遞歸(斐波那契、漢諾塔)】
• 筆記03【19-27】【（時間、空間復雜度）；八大排序（冒泡、快速、插入、希爾、選擇、歸并、基數、隊列基數）】
• 筆記04【28-33】【樹結構(二叉樹)概述、創建、遍歷、查找節點、刪除節點】
• 筆記05【34-39】【順序存儲二叉樹概述、二叉樹遍歷、堆排序、線索二叉樹實現及遍歷】
• 筆記06【40-48】【赫夫曼樹、概述、原理分析、代碼實現(數據壓縮、創建編碼表、解碼、壓縮文件、解壓文件)】
• 筆記07【49-54】【二叉排序樹（添加、查找、刪除節點）】
• 筆記08【55-57】【二叉平衡樹(AVL)-概述、單旋轉、雙旋轉】
• 筆記09【58-60】【計算機中數據的存儲原理、2-3樹的插入原理、B樹和B+樹】
• 筆記10【61-63】【哈希表概述、散列函數的設計、散列沖突解決方案】
• 筆記11【64-67】【圖結構概述、圖遍歷原理(BFS\DFS)、圖遍歷代碼實現】

目? ?錄

P64 6.1 圖結構概述

P65 6.2 圖結構代碼實現

P66 6.3 圖的遍歷原理

1、深度優先搜索---DFS（棧）

2、廣度優先搜索---BFS（隊列）

P67 6.4 圖的遍歷代碼實現

1、Vertex.java

2、Graph.java

3、TestGraph.java

4、MyStack.java

---

P64 6.1 圖結構概述

P65 6.2 圖結構代碼實現

鄰接矩陣：用數字標識頂點之間是否連通。

P66 6.3 圖的遍歷原理

1、深度優先搜索---DFS（棧）

從第一個節點（比如：節點A）開始遍歷，找下一個鄰接節點，看其通不通。

A作為出發點，一個點一個點地遍歷。

2、廣度優先搜索---BFS（隊列）

將棧替換為隊列（先進先出）。? ?波紋---一圈圈地搜索。

A進隊列，從A開始往后找，找到B【從隊列頭A（出隊方向）開始找下一個】

A找到C，C入棧

再從A開始往后找，D\E不通，A出隊列，

看B與哪些節點連通->D（C已被訪問）

再從B開始往后找，無未連通節點，B出隊列；

再從C開始往后找，無未連通節點，C出隊列；

再從D開始往后找，無未連通節點，D出隊列；

再從E開始往后找，無未連通節點，E出隊列；

BFS遍歷完畢！

P67 6.4 圖的遍歷代碼實現

1、Vertex.java

package demo14;public class Vertex {// 頂點類private String value;//該節點是否遍歷過-默認值falsepublic boolean visited;public String getValue() {return value;}public void setValue(String value) {this.value = value;}public Vertex(String value) {super();this.value = value;}@Overridepublic String toString() {return value;}}

2、Graph.java

package demo14;import demo2.MyStack;public class Graph {// 圖private Vertex[] vertex;// 頂點數組private int currentSize;public int[][] adjMat;private MyStack stack = new MyStack();private int currentIndex;// 當前遍歷的下標public Graph(int size) {vertex = new Vertex[size];adjMat = new int[size][size];}/*** 向圖中加入一個頂點* * @param v*/public void addVertex(Vertex v) {vertex[currentSize++] = v;}public void addEdge(String v1, String v2) {// 找出兩個頂點的下標int index1 = 0;for (int i = 0; i < vertex.length; i++) {if (vertex[i].getValue().equals(v1)) {index1 = i;break;}}int index2 = 0;for (int i = 0; i < vertex.length; i++) {if (vertex[i].getValue().equals(v2)) {index2 = i;break;}}adjMat[index1][index2] = 1;adjMat[index2][index1] = 1;}/*** 深度優先搜索算法遍歷圖*/public void dfs() {// 把第0個頂點標記為已訪問狀態vertex[0].visited = true;// 把第0個頂點的下標。stack.push(0);// 打印頂點的值System.out.println(vertex[0].getValue());// 遍歷out: while (!stack.isEmpty()) {for (int i = currentIndex + 1; i < vertex.length; i++) {// 如果和下一個遍歷的元素是通的if (adjMat[currentIndex][i] == 1 && vertex[i].visited == false) {// 把下一個元素壓入棧中stack.push(i);vertex[i].visited = true;System.out.println(vertex[i].getValue());continue out;}}// 彈出棧頂元素stack.pop();// 修改當前位置為棧頂元素的位置if (!stack.isEmpty()) {currentIndex = stack.pick();}}}}

3、TestGraph.java

package demo14;import java.util.Arrays;public class TestGraph {public static void main(String[] args) {Vertex v1 = new Vertex("A");Vertex v2 = new Vertex("B");Vertex v3 = new Vertex("C");Vertex v4 = new Vertex("D");Vertex v5 = new Vertex("E");Graph g = new Graph(5);g.addVertex(v1);g.addVertex(v2);g.addVertex(v3);g.addVertex(v4);g.addVertex(v5);// 增加邊g.addEdge("A", "C");g.addEdge("B", "C");g.addEdge("A", "B");g.addEdge("B", "D");g.addEdge("B", "E");for (int[] a : g.adjMat) {System.out.println(Arrays.toString(a));}// 深度優先遍歷g.dfs();}}

4、MyStack.java

package demo2;public class MyStack {// 棧的底層我們使用數組來存儲數據int[] elements;public MyStack() {elements = new int[0];}// 壓入元素public void push(int element) {// 創建一個新的數組int[] newArr = new int[elements.length + 1];// 把原數組中的元素復制到新數組中for (int i = 0; i < elements.length; i++) {newArr[i] = elements[i];}// 把添加的元素放入新數組中newArr[elements.length] = element;// 使用新數組替換舊數組elements = newArr;}// 取出棧頂元素public int pop() {// 棧中沒有元素if (elements.length == 0) {throw new RuntimeException("stack is empty");}// 取出數組的最后一個元素int element = elements[elements.length - 1];// 創建一個新的數組int[] newArr = new int[elements.length - 1];// 原數組中除了最后一個元素的其它元素都放入新的數組中for (int i = 0; i < elements.length - 1; i++) {newArr[i] = elements[i];}// 替換數組elements = newArr;// 返回棧頂元素return element;}// 查看棧頂元素public int pick() {// 棧中沒有元素if (elements.length == 0) {throw new RuntimeException("stack is empty");}return elements[elements.length - 1];}// 判斷棧是否為空public boolean isEmpty() {return elements.length == 0;}}

🚀完結撒花~? ? ? *★,°*:.☆(￣▽￣)/$:*.°★* 。

總結

以上是生活随笔為你收集整理的数据结构Java11【图结构概述、图遍历原理(BFS\DFS)、图遍历代码实现】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。