文章目錄
-
- 一、圖的概述
-
- 1.1 什麼是圖
- 1.2 圖對比線性表和樹
- 1.3 圖的常見概念
- 二、圖的存儲方式
-
- 2.1 鄰接矩陣
- 2.2 鄰接表
- 三、圖的周遊
-
- 3.1 圖的深度優先周遊
-
- 3.1.1 什麼是深度優先周遊
- 3.1.2 深度優先周遊的步驟
- 3.1.3 深度優先周遊代碼實作
- 3.2 圖的廣度優先周遊
-
- 3.2.1 什麼是廣度優先周遊
- 3.2.2 廣度優先周遊的步驟
- 3.2.3 廣度優先周遊代碼實作
一、圖的概述
1.1 什麼是圖
圖（graph）是一種資料結構，它是由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G（V，E）。其中 G 表示一個圖，V 是圖 G 中頂點的集合，E 是圖 G 中邊的集合。
從圖的定義中我們可以注意到它的一個特點：圖中資料元素被稱為頂點（Vertex）。而線上性表中的資料元素叫元素，樹形結構中的資料元素叫做節點。
1.2 圖對比線性表和樹
前面學習過線性表和樹，現在又學到了圖。為什麼有這麼多的資料結構呢？它們各自有什麼不可替代的特點呢？
線上性表中，資料元素之間是串起來的，僅有線性關系，每個資料元素隻有一個直接前驅和一個直接後繼，可以了解為一對一。在樹形結構中，資料元素之間有着明顯的層次關系，并且每一層上的資料元素可能和下一層中的多個元素相關，但是隻能和上一層中一個元素相關，可以了解為一對多。
圖示一種較線性表和樹更加複雜的資料結構。在圖形結構中，節點之間的關系可以是任意的，圖中任意兩個資料元素之間都可能相關，可以了解為多對多。
1.3 圖的常見概念
在圖中有比較多的概念需要掌握，下面用一個表格來展示圖形結構的常見概念。
| 常見概念 | 概念解釋 |
|---|---|
| 頂點 | 資料元素 |
| 邊 | 兩個頂點之間的連線 |
| 路徑 | 從頂點 A 到頂點 B 要經過的邊（路徑可以有多條） |
| 鄰接點 | 相鄰的頂點（如 A 和 B 通過一條邊直接相連，則 B 是 A 的鄰接點，A 是 B 的鄰接點） |
| 無向圖 | 所有的邊都沒有方向 |
| 有向圖 | 所有的邊都有方向（如 A->B，表示隻能從 A 到 B，無法從 B 到 A） |
| 帶權圖 | 所有的邊都帶有權值 |
| 連通圖 | 任意兩個頂點都是連通的 |
二、圖的存儲方式
圖的存儲方式有兩種：二維數組表示（鄰接矩陣）、連結清單表示（鄰接表）。
2.1 鄰接矩陣
圖的鄰接矩陣 （Adjacency Matrix） 存儲方式是用兩個數組來表示圖，其中一個一維數組用來存儲頂點資訊，一個二維數組（稱為鄰接矩陣）存儲圖中的邊的資訊。
鄰接矩陣的行和列都是代表着圖的第幾個頂點。
如上所示圖左是一個無向圖，右邊是該無向圖的鄰接矩陣：頂點 0 和頂點 1 之間存在一條邊，是以
arr[0][1]
和
arr[1][0]
都為 1（僅适用于無向圖）；頂點 0 和頂點 5 之間沒有直接相連的邊，是以
arr[0][5]
和
arr[5][0]
都是 0。
【案例示範】
代碼實作如下圖結構，要求使用鄰接矩陣。
public class No1_Graph {
public static void main(String[] args) {
String[] str = {"A", "B", "C", "D", "E"};
// 建立一個圖對象
Graph graph = new Graph(str.length);
// 添加頂點
for (String vertex : str){
graph.addVertex(vertex);
}
// 設定頂點之間的邊
graph.setEdges(0, 1, 1); // A<->B
graph.setEdges(1, 2, 1); // B<->C
graph.setEdges(1, 3, 1); // B<->D
graph.setEdges(1, 4, 1); // B<->E;
graph.setEdges(0, 2, 1); // A<->C;
}
}
/**
* 圖
*/
class Graph{
private ArrayList<String> vertexList; // 存儲頂點的集合
private int[][] edges; // 圖對應的鄰接矩陣
private int numOfEdges; // 頂點之間邊的個數
// 圖的初始化
public Graph(int n){
this.vertexList = new ArrayList<>();
this.edges = new int[n][n];
this.numOfEdges = 0;
this.isVisited = new boolean[n];
}
// 添加頂點到圖中
public void addVertex(String vertex){
vertexList.add(vertex);
}
/**
* 設定兩個頂點之間的邊
* @param n 第一個頂點的索引
* @param m 第二個頂點的索引
* @param weight 邊的權重
* @return void
*/
public void setEdges(int n, int m, int weight){
edges[n][m] = weight;
edges[m][n] = weight;
numOfEdges++;
}
// 列印鄰接矩陣
public void printGraph(){
for (int[] edge : edges){
System.out.println(Arrays.toString(edge));
}
}
}
代碼運作結果如下：
2.2 鄰接表
圖的鄰接表（Adjacency List）存儲方式是用數組和連結清單來表示圖，其中一個一維數組用來存儲頂點，頂點數組中的每個資料元素還需要存儲指向該頂點第一個鄰接點的指針，每個頂點的所有鄰接點構成一個線性表。
鄰接矩陣需要為每個頂點都配置設定 n 個邊的空間，其實有很多邊都是不存在，會造成空間的一定損失。鄰接表的實作隻關心存在的邊，不關心不存在的邊，是以沒有空間浪費。
如下圖所示就是一個無向圖的鄰接表結構。
如圖右所示，是無向圖的鄰接表：如标号為 0 的頂點的鄰接點為 1、2、3、4；标号為 2 的訂單的鄰接點為 0、5。
頂點數組中的資料元素由兩部分組成，一部分是資料域存儲頂點的資訊，另一部分是指針域，指向該頂點的第一個鄰接點。連結清單節點同樣由兩部分組成，一部分是鄰接點域，用于存儲與頂點相鄰的點在圖中的位置，另一部分是指針域，指向下一條邊（如果邊還有權值，還需要一個資料域用于存儲權值，共三部分）。
三、圖的周遊
從圖中某一個頂點出發周遊圖中其餘頂點，且使每一個頂點僅被通路一次，這個過程就叫做圖的周遊。一個圖有多個頂點，如何周遊這些頂點，需要特定政策，一般有兩種通路政策：深度優先周遊、廣度優先周遊。
3.1 圖的深度優先周遊
3.1.1 什麼是深度優先周遊
深度優先周遊（Depth First Search），也稱深度優先搜尋，簡稱為 DFS。
深度優先周遊的思想說起來可能比較抽象，下面舉個例子說一下。
古時候有個功夫平平的劍客，一直想找到武林秘籍來提升自己的功夫。也算他命好，在行走江湖的路上他認識了一位神秘的老者，老者看他心系武林，就把守護了一生的秘密告訴他：在黃山、華山、泰山、峨眉山中的其中一座山裡藏着失傳已經的降龍十八掌，但是具體在哪座山需要他自己去找。
一聽說這個，劍客可就不困了。但是冷靜下來之後，這個劍客有點懵逼了，這幾座山這麼大，離得還這麼遠，該怎麼去尋找武林秘籍呢？
經過一夜的輾轉反側，劍客最終确定了行動思路：先去黃山，不放過黃山的任何一個角落，把黃山的所有山洞、所有的小溪、所有的山路、所有的樹木甚至是動物都找個遍，簡單來說就是翻個底朝天，然後再去下一座山，再翻個底朝天，直到找到為止。
這就是深度優先周遊的思想，簡單來說就是優先向縱深挖掘，它類似于樹的先序周遊的過程。
3.1.2 深度優先周遊的步驟
假設初始狀态是圖中所有頂點未曾被通路，則深度優先搜尋可從圖中某個頂點 v 出發，通路此頂點，然後依次從 v 的未被通路的鄰接點出發深度優先周遊圖，直至圖中所有和 v 有路徑相通的頂點都被通路到；若此時圖中尚有頂點未被通路，則另選圖中一個未曾被通路的頂點作起始點，重複上述過程，直至圖中所有頂點都被通路到為止。
以下面一個無向圖為例，講解其深度優先周遊過程。
假設從頂點 v1 出發，在通路完 v1 之後，選擇鄰接點 v2，因為 v2 未被通路，則從 v2 出發進行搜尋。依次類推，接着從 v4、v7 出發進行搜尋。在通路了 v7 之後，由于 v7 的鄰接點都已經被通路，則搜尋退回到 v4。由于同樣的理由搜尋繼續回到 v2，直至 v1。此時由于 v1 的另一個鄰接點未被通路，則搜尋又從 v1 到 v3，再繼續進行下去。由此，得到的頂點通路序列為：
v 1 → v 2 → v 4 → v 7 → v 3 → v 5 → v 6 v1→v2→v4→v7→v3→v5→v6 v1→v2→v4→v7→v3→v5→v6
顯然，這是一個遞歸加回溯的過程。為了在周遊過程中便于區分頂點是否已被通路，需附設通路标志數組
isVisited[0.. n-1]
，其初始值為
false
，一旦某個頂點被通路，則其相應的分量置為
true
。
3.1.3 深度優先周遊代碼實作
boolean[] isVisited = new boolean[vertexList.size]; // 标志數組
/**
* 從頂點 v 開始深度優先搜尋 (DFS)
* @param v 頂點
*/
public void dfs(int v){
isVisited[v] = true; // 設定目前頂點狀态為已通路
System.out.print(vertexList.get(v) + "->"); // 列印目前頂點
for (int i=0; i<vertexList.size(); i++){ // 周遊頂點
if (edges[v][i]==1 && !isVisited[i]){ // 如果某個頂點和目前頂點有直連的邊且該頂點未被通路過
dfs(i); // 遞歸深度優先周遊這個頂點
}
}
}
/**
* 對圖深度優先搜尋
*/
public void dfsTraverse(){
/* 有可能是非連通圖，出現頂點獨立現象，是以有可能要以每個頂點為起點都來一次深度優先搜尋 */
for (int i=0; i<vertexList.size(); i++){
if (!isVisited[i]){ // 如果頂點未被通路過，則從它開始 dfs。對于連通圖，隻會執行一次。
dfs(i);
}
}
}
3.2 圖的廣度優先周遊
3.2.1 什麼是廣度優先周遊
廣度優先周遊（Breadth First Search），又稱為廣度優先搜尋，簡稱 BFS。
還是以劍客找武林秘籍為例。劍客在趕往黃山的路上一想到要把整座山都翻個遍，瞬間頭皮就麻了，他覺得武林秘籍總不至于會藏在山上的某個小石頭下面吧，一定是藏在某個有靈氣的地方。于是他改變了政策：先到每座山上大概瞅一眼，看看山的山勢、靈氣是不是像有武林秘籍的地方，如果都沒有，再依次到各個山的山洞、小溪中找一找，如果沒找到，再依次到各個山的小石頭下翻一翻…，直到找到為止。
這就是廣度優先周遊的思想，它類似于樹的按層次周遊的過程。
3.2.2 廣度優先周遊的步驟
假設從圖中頂點 v 出發，在 通路了 v 之後依次通路 v 的各個未曾通路過的鄰接點，然後分别從這些鄰接點出發依次通路它們的鄰接點，并使 “先被通路的頂點的鄰接點” 先于 “後被通路的頂點的鄰接點” 被通路，直至圖中所有已被通路的頂點的鄰接點都被通路到。若此時圖中尚有頂點未被通路，則另選圖中一個未曾被通路的頂點作起始點，重複上述過程，直至圖中所有頂點都被通路到為止。
還是以下面一個無向圖為例，講解廣度優先周遊過程。
首先通路 v1 和 v1 的鄰接點 v2 和 v3，然後依次通路 v2 的鄰接點 v4 和 v7 以及 v3 的鄰接點 v5 和 v6。由于這些頂點的鄰接點均已被通路，并且圖中所有的頂點都被通路，由此完成了圖的周遊。最終得到的頂點通路序列為：
v 1 → v 2 → v 3 → v 4 → v 7 → v 5 → v 6 v1→v2→v3→v4→v7→v5→v6 v1→v2→v3→v4→v7→v5→v6
和深度優先周遊類似，廣度優先周遊在周遊的過程中也需要一個通路标志數組。并且，為了順次通路路徑長度為 2、3 … 的頂點，需要附設隊列以存儲已被通路的路徑長度為 1、2 … 的頂點。
3.2.3 廣度優先周遊代碼實作
/**
* 從頂點 v 開始廣度優先周遊 (BFS)
* @param v 頂點
*/
public void bfs(int v){
LinkedList<Integer> queue = new LinkedList<>(); // 隊列，用于存放已被通路的頂點
isVisited[v] = true; // 設定狀态為已通路
System.out.print(vertexList.get(v) + "->"); // 列印頂點
queue.addLast(v); // 添加目前頂點到隊列中
while (!queue.isEmpty()){ // 如果目前隊列不為空
v = queue.removeFirst(); // 隊頭元素出隊列，接下來将以這個出隊列的元素為起點通路鄰接點
for (int i=0; i<vertexList.size(); i++){
if (edges[v][i] == 1 && !isVisited[i]){ // 判斷其它頂點與目前頂點是否有邊且是否通路過
isVisited[i] = true; // 标記符合條件的頂點狀态為已通路
System.out.print(vertexList.get(i) + "->"); // 列印頂點
queue.addLast(i); // 将此頂點入隊列
}
}
}
}
/**
* 廣度優先周遊圖
*/
public void bfsTraverse(){
/* 可能是非連通圖，出現頂點獨立現象，是以有可能每個頂點都要廣度優先搜尋 */
for (int i=0; i<vertexList.size(); i++){
if (!isVisited[i]){ // 如果頂點未被通路過，則對該頂點廣度優先搜尋，對于連通圖隻會執行一次
bfs(i);
}
}
}