【數據結構與算法——TypeScript】

圖結構(Graph)

認識圖結構以及特性

什么是圖?

• 在計算機程序設計中，圖結構 也是一種非常常見的數據結構。
  • 但是，圖論其實是一個非常大的話題
• 認識一下關于圖的一些內容
  • 圖的抽象數據類型
  • 一些算法實現。
• 什么是圖?
  • 圖結構是一種與樹結構有些相似的數據結構。
  • 圖論是數學的一個分支，并且，在數學的概念上，樹是圖的一種。
  • 它以圖為研究對象，研究 頂點 和 邊 組成的圖形的數學理論和方法。
  • 主要研究的目的是事物之間的關系，頂點代表事物，邊代表兩個事物間的關系
• 我們知道樹可以用來模擬很多現實的數據結構
  • 比如： 家譜/公司組織架構等等
• 那么圖長什么樣子?
• 或者什么樣的數據使用圖來模擬更合適呢?

圖的現實案例

• 人與人之間的關系網。
  • 甚至科學家們在觀察人與人之間的關系網時，還發現了六度空間理論。
• 六度空間理論
  • 理論上認為世界上任何兩個互相不認識的兩人。
  • 只需要很少的中間人就可以建立起聯系。
  • 并非一定要經過6步，只是需要很少的步驟。
• 地鐵圖

• 村莊之間的關系網

再次 什么是圖？

• ???🔥 那么，什么是圖呢?
  • 我們會發現，上面的節點(其實圖中叫頂點Vertex)之間的關系，是不能使用樹來表示
  • 使用任何的樹結構都不可以模擬。
  • 這個時候，我們就可以使用圖來模擬它們。
• ???🔥 圖通常有什么特點呢?
  • 💚 一組頂點：通常用 V (Vertex) 表示頂點的集合
  • 💚 一組邊：通常用 E (Edge) 表示邊的集合
    • ? 邊是頂點和頂點之間的連線
    • ? 邊可以是有向的，也可以是無向的。
    • ? 比如A — B，通常表示無向。 A --> B，通常表示有向

歐拉和七拉問題解法

歷史故事

• 8世紀著名古典數學問題之一。

  • 在哥尼斯堡的一個公園里，有七座橋將普雷格爾河中兩個島及島與河岸連接起來(如圖)。

    

  • 有人提出問題： 一個人怎樣才能不重復、不遺漏地一次走完七座橋，最后回到出發點。

• 1735年，有幾名大學生寫信給當時正在俄羅斯的彼得斯堡科學院任職的瑞典天才數學家歐拉，請他幫忙解決這一問題。
  • 歐拉在親自觀察了哥倫斯堡的七橋后，認真思考走法，但是始終沒有成功，于是他懷疑七橋問題是不是無解的。
  • 1736年29歲的歐拉向 彼得斯堡 科學院遞交了《哥尼斯堡的七座橋》的論文，在解答問題的同時，開創了數學的一個新的分支——圖論與幾何拓撲，也由此展開了數學史上的新歷程。

歐拉解答

• 他不僅解決了該問題，并且給出了 連通圖 可以一筆畫的充要條件是：
  • 奇點的數目不是0個就是2 個
  • 連到一點的邊的數目如果是奇數條，就稱為奇點
  • 如果是偶數條就稱為偶點
  • 要想一筆畫成，必須中間點均是偶點
  • 也就是有來路必有另一條去路，奇點只可能在兩端，因此任何圖能一筆畫成，奇點要么沒有,要么在兩端
• 個人思考：
  • 歐拉在思考這個問題的時候，并不是針對某一個特性的問題去考慮，而是將島和橋抽象成了點和線。
  • 抽象是數學的本質，而編程我們也一再強調抽象的重要性。
  • 匯編語言是對機器語言的抽象，高級語言是對匯編語言的抽象。
  • 操作系統是對硬件的抽象，應用程序在操作系統的基礎上構建。

圖結構的常見術語

關于術語的概述

• 我們在學習樹的時候，樹有很多的相關術語。

• 了解這些術語有助于我們更好的理解樹結構。

• 我們也來學習一下圖相關的術語。

  • 但是圖的術語其實非常多，如果你找一本專門講圖的各個方面的書籍，會發現 只是術語 就可以 占據滿滿的一個章節。
  • 這里，我們先介紹幾個比較常見的術語。

• 我們先來看一個抽象出來的圖
  ? 用數字更容易我們從整體來觀察整個圖結構。
  

術語

1. 頂點：

   • 頂點剛才我們已經介紹過了，表示圖中的一個節點。
   • 比如地鐵站中某個站/多個村莊中的某個村莊/互聯網中的某臺主機/人際關系中的人。

2. 邊：

   • 邊剛才我們也介紹過了，表示頂點和頂點之間的連線。
   • 比如地鐵站中兩個站點之間的直接連線，就是一個邊。
   • ?? 注意： 這里的邊不要叫做路徑，路徑有其他的概念，待會兒我們會介紹到。
   • 之前的圖中： 0 - 1有一條邊，1 - 2有一條邊，0 - 2沒有邊。

3. 相鄰頂點：

   • 由一條邊連接在一起的頂點稱為相鄰頂點。
   • 比如0 - 1是相鄰的，0 - 3是相鄰的。 0 - 2是不相鄰的。

4. 度：

   • 一個頂點的度是相鄰頂點的數量。
   • 比如0頂點和其他兩個頂點相連，0頂點的度是2
   • 比如1頂點和其他四個頂點相連，1頂點的度是4

5. 路徑：

   • 路徑是頂點v1，v2…，vn的一個連續序列，比如上圖中0 1 5 9就是一條路徑。
   • 簡單路徑： 簡單路徑要求不包含重復的頂點。 比如 0 1 5 9 是一條簡單路徑。
   • 回路： 第一個頂點和最后一個頂點相同的路徑稱為回路。 比如 0 1 5 6 3 0

6. 無向圖：

   • 上面的圖就是一張無向圖，因為所有的邊都沒有方向。
   • 比如 0 - 1之間有變，那么說明這條邊可以保證 0 -> 1，也可以保證 1 -> 0。

7. 有向圖：

   • 有向圖表示的圖中的邊是有方向的。
   • 比如 0 -> 1，不能保證一定可以 1 -> 0，要根據方
     向來定。

8. 無權圖：

   • 我們上面的圖就是一張無權圖(邊沒有攜帶權重)
   • 我們上面的圖中的邊是沒有任何意義的
   • 不能說 0 - 1的邊，比4 - 9的邊更遠或者用的時間更長。

9. 帶權圖：

   • 帶權圖表示邊有一定的權重。
   • 這里的權重可以是任意你希望表示的數據：
     ? 比如距離或者花費的時間或者票價。

圖的表示

• 怎么在程序中表示圖呢?
  • 我們知道一個圖包含很多頂點，另外包含頂點和頂點之間的連線(邊)
  • 這兩個都是非常重要的圖信息，因此都需要在程序中體現出來。
• 頂點的表示相對簡單，我們先討論頂點的表示。
  • 上面的頂點，我們抽象成了1 2 3 4，也可以抽象成A B C D。
  • 在后面的案例中，我們使用A B C D。
  • 那么這些A B C D我們可以使用一個數組來存儲起來(存儲所有的頂點)
  • 當然，A，B，C，D也可以表示其他含義的數據(比如村莊的名字).
• 那么邊怎么表示呢?
  • 因為邊是兩個頂點之間的關系，所以表示起來會稍微麻煩一些。
  • 下面，我們具體討論一下變常見的表示方式。

鄰接矩陣和鄰接表

鄰接矩陣

• 一種比較常見的表示圖的方式： 鄰接矩陣。
  • 鄰接矩陣讓每個節點和一個整數項關聯，該整數作為數組的下標值。
  • 我們用一個二維數組來表示頂點之間的連接。
  • 二維數組 [0][2] -> A -> C
• 畫圖演示：

• 圖片解析：
  • 在二維數組中，0表示沒有連線，1表示有連線。
  • 通過二維數組，我們可以很快的找到一個頂點和哪些頂點有連線。(比如A頂點，只需要遍歷第一行即可)
  • 另外，A - A，B - B(也就是頂點到自己的連線)，通常使用0表示。
• 鄰接矩陣的問題：
  • 鄰接矩陣還有一個比較嚴重的問題，就是如果圖是一個稀疏圖
  • 那么矩陣中將存在大量的0，這意味著我們浪費了計算機存儲空間來表示根本不存在的邊。

鄰接表

• 另外一種常用的表示圖的方式： 鄰接表。

  • 鄰接表由圖中每個頂點以及和頂點相鄰的頂點列表組成。
  • 這個列表有很多種方式來存儲： **數組/鏈表/字典(哈希表)**都可以。

• 畫圖演示
  

• 圖片解析：

  • 其實圖片比較容易理解。
  • 比如我們要表示和A頂點有關聯的頂點(邊)，A和B/C/D有邊，
  • 那么我們可以通過A找到對應的數組/鏈表/字典，再取出其中的內容就可以啦。

• 鄰接表的問題：

  • 鄰接表計算"出度"是比較簡單的(出度： 指向別人的數量，入度： 指向自己的數量)
  • 鄰接表如果需要計算有向圖的"入度"，那么是一件非常麻煩的事情。
  • 它必須構造一個**“逆鄰接表”，才能有效的計算“入度”。但是開發中“入度”**相對用的比較少。

創建圖類

• 先創建Graph類
• 👩🏻?💻 代碼解析
  • 創建Graph的構造函數，這個我們在封裝其他數據結構的時候已經非常熟悉了。
• 定義了兩個屬性：
  ? vertexes： 用于存儲所有的頂點，我們說過使用一個數組來保存。
  ? adjList： adj是adjoin的縮寫，鄰接的意思。 adjList用于存儲所有的邊，我們這里采用鄰接表的形式。
• 之后，我們來定義一些方法以及實現一些算法就是一個完整的圖類了。

    class Graph<T> {// 頂點vertexes: T[] = [];// 鄰接表adjList: Map<T, T[]> = new Map();}

添加方法

• 現在我們來增加一些添加方法。
  • 添加頂點： 可以向圖中添加一些頂點。
  • 添加邊： 可以指定頂點和頂點之間的邊。
• 添加頂點
  • 👩🏻?💻 代碼解析：
    • 我們將添加的頂點放入到數組中。
    • 另外，我們給該頂點創建一個數組[]，該數組用于存儲頂點連接的所有的邊.(回顧鄰接表的實現方式)
• 添加邊
  • 👩🏻?💻 代碼解析：
    • 添加邊需要傳入兩個頂點，因為邊是兩個頂點之間的邊，邊不可能單獨存在。
    • 根據頂點v取出對應的數組，將w加入到它的數組中。
    • 根據頂點w取出對應的數組，將v加入到它的數組中。
    • 因為我們這里實現的是無向圖，所以邊是可以雙向的。

  // 添加頂點addVertex(vertex: T) {//   將頂點添加到頂點數組中保存this.vertexes.push(vertex);//   創建一個鄰接表的數組this.adjList.set(vertex, []);}addEdge(v1: T, v2: T) {this.adjList.get(v1)?.push(v2);this.adjList.get(v2)?.push(v1);}

printEdges方法

• 為了能夠正確的顯示圖的結果，我們來實現一下Graph的printEdges方法

• 測試代碼:

    const graph = new Graph();graph.addVertex('A');graph.addVertex('B');graph.addVertex('C');graph.addVertex('D');graph.addVertex('E');graph.addVertex('F');graph.addVertex('G');graph.addVertex('H');graph.addVertex('I');graph.addEdge('A', 'B');graph.addEdge('A', 'C');graph.addEdge('A', 'D');graph.addEdge('C', 'D');graph.addEdge('C', 'G');graph.addEdge('D', 'G');graph.addEdge('D', 'H');graph.addEdge('B', 'E');graph.addEdge('B', 'F');graph.addEdge('E', 'I');graph.printEdges();

  • 運行結果：
    [外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-fK63qbI7-1692005552724)(/Volumes/web/數據結構與算法（ts）/截圖/截屏2023-08-14 15.37.06.png “運行結果”)]
    

圖的遍歷

圖的遍歷思想

圖的遍歷思想和樹的遍歷思想是一樣的。
圖的遍歷意味著需要將圖中每個頂點訪問一遍，并且不能有重復的訪問

• 有兩種算法可以對圖進行遍歷
  • 廣度優先搜索(Breadth-First Search，簡稱BFS)
  • 深度優先搜索(Depth-First Search，簡稱DFS)
• 兩種遍歷算法，都需要明確指定第一個被訪問的頂點。
  • 它們的遍歷過程分別是怎么樣呢?
  • 我們以一個迷宮中關燈為例。
  • 現在需要你進入迷宮，將迷宮中的燈一個個關掉，你會怎么關呢?

遍歷的思想

• 兩種算法的思想：
  • BFS： 基于隊列，入隊列的頂點先被探索。
  • DFS： 基于棧或使用遞歸，通過將頂點存入棧中，頂點是沿著路徑被探索的，存在新的相鄰頂點就去訪問。
• 為了記錄頂點是否被訪問過，我們使用三種顏色來反應它們的狀態
  • 白色： 表示該頂點還沒有被訪問。
  • 灰色： 表示該頂點被訪問過，但并未被探索過。
  • 黑色： 表示該頂點被訪問過且被完全探索過。
• 或者我們也可以使用Set來存儲被訪問過的節點。

廣度優先搜索

• 廣度優先搜索算法的思路 💡：

  • 廣度優先算法會從指定的第一個頂點開始遍歷圖，先訪問其所有的相鄰點，就像一次訪問圖的一層。
  • 換句話說，就是先寬后深的訪問頂點

• 圖解BFS
  [外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳(img-mNFb1uIZ-1692005552726)(/Volumes/web/數據結構與算法（ts）/畫圖/圖/廣度優先搜索.png “廣度優先搜索”)]
  

  ? 廣度優先搜索的實現：
  ? 創建一個隊列Q。

• 代碼 💻 ：

  // 廣度優先bfs() {// 1. 判斷是否有頂點if (this.vertexes.length === 0) return;// 2. 創建隊列結構來訪問每個頂點const queue: T[] = [];queue.push(this.vertexes[0]);// 3. 創建Set，來記錄一個頂點是否被訪問過const visited = new Set();visited.add(this.vertexes[0]);// 4. 遍歷隊列中每一個頂點while (queue.length) {//  4.1 訪問隊列中第一個頂點const vertex = queue.shift()!;console.log(vertex);//  4.2 取出相鄰的頂點const neighbors = this.adjList.get(vertex);if (!neighbors) continue;for (const neighbor of neighbors) {if (!visited.has(neighbor)) {visited.add(neighbor);queue.push(neighbor);}}}}

• 運行結果：

深度優先搜索

• 深度優先搜索的思路：

  • 深度優先搜索算法將會從第一個指定的頂點開始遍歷圖，沿著路徑知道這條路徑最后被訪問了。
  • 接著原路回退并探索下一條路徑。

• 深度優先搜索

  • 深度優先搜索算法的實現：
    • 廣度優先搜索算法我們使用的是隊列，這里可以使用棧完成，也可以使用遞歸。

• 圖DFS

  

• 代碼 💻 ：

  // 深度優先dfs() {// 1. 判斷有沒有頂點，沒有直接返回if (this.vertexes.length === 0) return;// 2.創建棧結構const stack: T[] = [];stack.push(this.vertexes[0]);// 3. 創建Set結構const visited = new Set();visited.add(this.vertexes[0]);// 4. 從第一個頂點開始訪問while (stack.length) {const vertex = stack.pop()!;console.log(vertex);// 取出相鄰的頂點const neighbors = this.adjList.get(vertex);if (!neighbors) continue;for (let i = neighbors.length - 1; i >= 0; i--) {const nei = neighbors[i];if (!visited.has(nei)) {visited.add(nei);stack.push(nei);}}}}

• 運行結果：

圖結構的常見建模

• 對交通流量建模
  • 頂點可以表示街道的十字路口，邊可以表示街道。
  • 加權的邊可以表示限速或者車道的數量或者街道的距離。
  • 建模人員可以用這個系統來判定最佳路線以及最可能堵車的街道。
• 對飛機航線建模
  • 航空公司可以用圖來為其飛行系統建模。
  • 將每個機場看成頂點，將經過兩個頂點的每條航線看作一條邊。
  • 加權的邊可以表示從一個機場到另一個機場的航班成本，或兩個機場間的距離。
  • 建模人員可以利用這個系統有效的判斷從一個城市到另一個城市的最小航行成本。