圖的基本介紹

為什么要有圖這種數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)有線性表和樹

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

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

當(dāng)我們需要表示多對(duì)多的關(guān)系時(shí)，這里我們就需要用到圖這種數(shù)據(jù)結(jié)構(gòu)

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

圖的常用概念
1. 頂點(diǎn)（vertex）
2. 邊（edge）
3. 路徑
4. 無向圖（如圖）

5. 有向圖 （如下圖）
6. 帶權(quán)圖

圖的表示方式

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

鄰接矩陣

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

鄰接表

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

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

圖的案例入門
要求：代碼實(shí)現(xiàn)如下圖結(jié)構(gòu)

思路：
保存頂點(diǎn)用ArrayList集合 ，保存頂點(diǎn)之間相鄰關(guān)系的用鄰接矩陣，即二維數(shù)組表示。

public class Graph {// 存放頂點(diǎn)的集合private List<String> vertexList;// 鄰接矩陣，存放頂點(diǎn)關(guān)系private int[][] edges;// 邊的數(shù)目private int numOfEdges;public Graph(int n) {// n表示頂點(diǎn)的個(gè)數(shù)vertexList = new ArrayList<>(n);edges = new int[n][n];numOfEdges = 0;}/*** 添加頂點(diǎn)的方法* @param vertex*/public void addVertex(String vertex) {vertexList.add(vertex);}/*** 獲取頂點(diǎn)個(gè)數(shù)*/public int getVertexNum() {return vertexList.size();}/*** 返回對(duì)于下標(biāo)的頂點(diǎn)* @param i* @return*/public String getVertex(int i) {return vertexList.get(i);}/*** 添加邊* @param v1 表示第幾個(gè)下標(biāo)的頂點(diǎn)的位置* @param v2 表示第二個(gè)頂點(diǎn)的下標(biāo)* @param weight 邊的權(quán)*/public void addEdge(int v1, int v2, int weight) {// 表示下標(biāo)v1和v2頂點(diǎn)的邊edges[v1][v2] = weight;// 表示下標(biāo)v2和v1頂點(diǎn)的邊edges[v2][v1] = weight;numOfEdges++;}/*** 遍歷頂點(diǎn)*/public void listVertex() {for (String s : vertexList) {System.out.print(s + " ");}}/*** 遍歷鄰接矩陣，邊*/public void listEdge() {for (int[] edge : edges) {System.out.println(Arrays.toString(edge));}} }

測(cè)試

public class MyTest {public static void main(String[] args) {Graph graph = new Graph(5);String[] vertexs = {"A", "B", "C", "D", "E"};for (String vertex : vertexs) {// 添加頂點(diǎn)graph.addVertex(vertex);}// 添加邊 A-Bgraph.addEdge(0,1,1);// 添加邊 A-Cgraph.addEdge(0,2,1);// 添加邊 B-Cgraph.addEdge(1,2,1);// 添加邊 B-Dgraph.addEdge(1,3,1);// 添加邊 B-Egraph.addEdge(1,4,1);// 遍歷頂點(diǎn)graph.listVertex();System.out.println();// 遍歷邊graph.listEdge();} }

輸出結(jié)果

A B C D E [0, 1, 1, 0, 0] [1, 0, 1, 1, 1] [1, 1, 0, 0, 0] [0, 1, 0, 0, 0] [0, 1, 0, 0, 0]

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

• 圖的遍歷介紹

  所謂圖的遍歷，即使對(duì)節(jié)點(diǎn)的訪問。一個(gè)圖右很多節(jié)點(diǎn)，如何遍歷這些節(jié)點(diǎn)，我們需要一定的策略，一般有兩種策略：1.深度優(yōu)先遍歷，2.廣度優(yōu)先遍歷

• 圖的深度優(yōu)先遍歷（Depth First Search）

  • 深度優(yōu)先遍歷，從初始訪問結(jié)點(diǎn)出發(fā)，初始訪問結(jié)點(diǎn)可能有多個(gè)鄰接結(jié)點(diǎn)，深度優(yōu)先遍歷的策略就是首先訪問第一個(gè)鄰接結(jié)點(diǎn)，然后再以這個(gè)被訪問的鄰接結(jié)點(diǎn)作為初始結(jié)點(diǎn)，訪問它的第一個(gè)鄰接結(jié)點(diǎn)， 可以這樣理解：每次都在訪問完當(dāng)前結(jié)點(diǎn)后首先訪問當(dāng)前結(jié)點(diǎn)的第一個(gè)鄰接結(jié)點(diǎn)。
  • 我們可以看到，這樣的訪問策略是優(yōu)先往縱向挖掘深入，而不是對(duì)一個(gè)結(jié)點(diǎn)的所有鄰接結(jié)點(diǎn)進(jìn)行橫向訪問。
  • 顯然，深度優(yōu)先搜索是一個(gè)遞歸的過程

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

• 訪問初始節(jié)點(diǎn)V，并標(biāo)記該節(jié)點(diǎn)V為已訪問。
• 查找節(jié)點(diǎn)V的第一個(gè)鄰接節(jié)點(diǎn)W。
• 若W存在，則執(zhí)行步驟4，若W不存在，則回到步驟1，將從V的下一個(gè)連接節(jié)點(diǎn)繼續(xù)
• 若W未被訪問，對(duì)W進(jìn)行深度優(yōu)先遍歷遞歸（即把 W當(dāng)做另一個(gè)V，然后進(jìn)行步驟123）。
• 若W已被訪問，則查找V的W的鄰接節(jié)點(diǎn)的下一個(gè)鄰接節(jié)點(diǎn)，然后轉(zhuǎn)到步驟3。

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

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

• 廣度優(yōu)先遍歷算法步驟
• 訪問初始節(jié)點(diǎn)V，并標(biāo)記節(jié)點(diǎn)V為已訪問。
• 節(jié)點(diǎn)V入隊(duì)列
• 當(dāng)隊(duì)列非空時(shí)，繼續(xù)執(zhí)行，否則算法結(jié)束
• 出隊(duì)列，取得隊(duì)頭結(jié)點(diǎn)u。
• 查找結(jié)點(diǎn)u的第一個(gè)鄰接結(jié)點(diǎn)w。
• 若結(jié)點(diǎn)u的鄰接結(jié)點(diǎn)w不存在，則轉(zhuǎn)到步驟3；否則循環(huán)執(zhí)行以下三個(gè) 步驟
  6.1 若結(jié)點(diǎn)w尚未被訪問，則訪問結(jié)點(diǎn)w并標(biāo)記為已訪問。
  6.2 結(jié)點(diǎn)w入隊(duì)列
  6.3 查找結(jié)點(diǎn)u的繼w鄰接結(jié)點(diǎn)后的下一個(gè)鄰接結(jié)點(diǎn)w，轉(zhuǎn)到步驟6。

深度優(yōu)先遍歷和廣度優(yōu)先遍歷代碼示例

主要方法：深度優(yōu)先（dfs），廣度優(yōu)先（bfs）

public class Graph {// 存放頂點(diǎn)的集合private List<String> vertexList;// 鄰接矩陣，存放頂點(diǎn)關(guān)系private int[][] edges;// 邊的數(shù)目private int numOfEdges;// 是否被訪問private boolean[] isVisited;public Graph(int n) {// n表示頂點(diǎn)的個(gè)數(shù)vertexList = new ArrayList<>(n);edges = new int[n][n];numOfEdges = 0;}/*** 添加頂點(diǎn)的方法* @param vertex*/public void addVertex(String vertex) {vertexList.add(vertex);}/*** 查找下標(biāo)為index頂點(diǎn)的的第一個(gè)鄰接節(jié)點(diǎn)* @param index* @return 返回找到的下標(biāo) ,沒有找到就返回-1*/public int getFirstNeighbor(int index) {for (int i = 0; i < vertexList.size(); i++) {if (edges[index][i] == 1){return i;}}return -1;}/**** @param index 初始頂點(diǎn)下標(biāo)* @param firstNeighbor 初始頂點(diǎn)的第一個(gè)個(gè)鄰接節(jié)點(diǎn)* @return 返回初始節(jié)點(diǎn)的下一個(gè)鄰接節(jié)點(diǎn)的下標(biāo)，沒有就返回-1*/public int getNextNeighbor(int index, int firstNeighbor) {for (int i = firstNeighbor + 1; i < vertexList.size(); i++) {if (edges[index][i] == 1) {return i;}}return -1;}/*** 深度優(yōu)先遍歷* @param isVisited 要訪問的節(jié)點(diǎn)是否被訪問* @param index 要訪問的初始節(jié)點(diǎn)*/private void dfs(boolean[] isVisited, int index) {isVisited = new boolean[vertexList.size()];// 1. 訪問初始節(jié)點(diǎn)，并把該節(jié)點(diǎn)標(biāo)記為已訪問System.out.print(vertexList.get(index) + "->");isVisited[index] = true;//2. 查找節(jié)點(diǎn)index的第一個(gè)鄰接節(jié)點(diǎn)int firstNeighbor = getFirstNeighbor(index);//3. firstNeighbor != -1 說明有鄰接節(jié)點(diǎn)while ( firstNeighbor != -1) {// 判斷這鄰接節(jié)點(diǎn)是否被訪問if (!isVisited[firstNeighbor]) {//4. 沒有被訪問，則進(jìn)行遞歸,把firstNeighbor當(dāng)成初始節(jié)點(diǎn)進(jìn)行遞歸訪問dfs(isVisited, firstNeighbor);}// 5.該鄰接節(jié)點(diǎn)已被訪問，則查找index除了firstNeighbor節(jié)點(diǎn)的下一個(gè)鄰接節(jié)點(diǎn)firstNeighbor = getNextNeighbor(index, firstNeighbor);}}/*** 深度優(yōu)先遍歷*/public void dfs () {for (int i = 0; i < vertexList.size(); i++) {if (!isVisited[i]) {dfs(isVisited, i);}}}/*** 廣度優(yōu)先遍歷* @param isVisited* @param index*/private void bfs(boolean[] isVisited, int index) {isVisited = new boolean[vertexList.size()];// 定義一個(gè)隊(duì)列，來保存訪問過節(jié)點(diǎn)的順序LinkedList<Integer> queue = new LinkedList<>();// 1. 訪問初始節(jié)點(diǎn)，標(biāo)記為已訪問System.out.println(vertexList.get(index) + "->");isVisited[index] = true;// 將訪問過的節(jié)點(diǎn)入隊(duì)列,注意加 到最后一個(gè)，取的時(shí)候是第一個(gè)queue.addLast(index);// 當(dāng)隊(duì)列不為空時(shí)，一直循環(huán)執(zhí)行int v; // 用來存放隊(duì)列里去除的節(jié)點(diǎn)下標(biāo)while (!queue.isEmpty()) {// 取出隊(duì)列的頭節(jié)點(diǎn)v = queue.removeFirst();// 查找節(jié)點(diǎn)v的鄰接節(jié)點(diǎn)int neighbor = getFirstNeighbor(v);// 若鄰接節(jié)點(diǎn)存在while (neighbor != -1) {// 若該節(jié)點(diǎn)未被訪問if (!isVisited[neighbor]) {System.out.print(vertexList.get(neighbor) + "->");// 標(biāo)記為已訪問isVisited[neighbor] = true;// 加入隊(duì)列queue.addLast(neighbor);}// 查找v的繼neighbor的下一個(gè)鄰接節(jié)點(diǎn)neighbor = getNextNeighbor(v, neighbor);}}}public void bfs() {for (int i = 0; i < vertexList.size(); i++) {if (!isVisited[i]) {bfs(isVisited,i);}}}/*** 獲取頂點(diǎn)個(gè)數(shù)*/public int getVertexNum() {return vertexList.size();}/*** 返回對(duì)于下標(biāo)的頂點(diǎn)* @param i* @return*/public String getVertex(int i) {return vertexList.get(i);}/*** 添加邊* @param v1 表示第幾個(gè)下標(biāo)的頂點(diǎn)的位置* @param v2 表示第二個(gè)頂點(diǎn)的下標(biāo)* @param weight 邊的權(quán)*/public void addEdge(int v1, int v2, int weight) {// 表示下標(biāo)v1和v2頂點(diǎn)的邊edges[v1][v2] = weight;// 表示下標(biāo)v2和v1頂點(diǎn)的邊edges[v2][v1] = weight;numOfEdges++;}/*** 遍歷頂點(diǎn)*/public void listVertex() {for (String s : vertexList) {System.out.print(s + " ");}}/*** 遍歷鄰接矩陣，邊*/public void listEdge() {for (int[] edge : edges) {System.out.println(Arrays.toString(edge));}} }

測(cè)試類

public class MyTest {public static void main(String[] args) {Graph graph = new Graph(5);String[] vertexs = {"A", "B", "C", "D", "E"};for (String vertex : vertexs) {// 添加頂點(diǎn)graph.addVertex(vertex);}// 添加邊 A-Bgraph.addEdge(0,1,1);// 添加邊 A-Cgraph.addEdge(0,2,1);// 添加邊 B-Cgraph.addEdge(1,2,1);// 添加邊 B-Dgraph.addEdge(1,3,1);// 添加邊 B-Egraph.addEdge(1,4,1);System.out.println("對(duì)圖進(jìn)行深度優(yōu)先遍歷：");graph.dfs();System.out.println();System.out.println("廣度優(yōu)先遍歷");graph.bfs();} }

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

對(duì)圖進(jìn)行深度優(yōu)先遍歷： A->B->C->D->E-> 廣度優(yōu)先遍歷 A->B->C->D->E->

總結(jié)：注意分析代碼，深度優(yōu)先和廣度優(yōu)先主要區(qū)別在于：

深度優(yōu)先是先從初始節(jié)點(diǎn)開始，尋找到他的下一個(gè)鄰節(jié)點(diǎn)，然后在以這個(gè)鄰接點(diǎn)為初始節(jié)點(diǎn)，繼續(xù)重復(fù)這些操作。

廣度優(yōu)先是從初始節(jié)點(diǎn)開始，尋找他的鄰節(jié)點(diǎn)，然后再繼續(xù)尋找他下一個(gè)鄰節(jié)點(diǎn)，直到把他所有的鄰節(jié)點(diǎn)找到，在換成隊(duì)列另一個(gè)節(jié)點(diǎn)繼續(xù)重復(fù)上面的操作，

總結(jié)

以上是生活随笔為你收集整理的数据结构 - 图 （图的深度优先和广度优先）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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