圖的深度優先遍歷類似於二叉樹

一、概述

圖是計算機科學中的一類非常重要的數據結構，用於描述物體間的關係。在圖中，節點（vertex）代表物體，邊（edge）則代表物體間的關係。通過遍歷圖，我們可以對圖中的節點進行訪問，同時也可以找出圖中節點之間的關係。

深度優先遍歷是圖遍歷中重要的一種方法，它類似於二叉樹的前序遍歷，按照深度優先的方式訪問圖中的節點。具體而言，深度優先遍歷會首先訪問某個節點，接着訪問該節點的鄰居節點，並進一步訪問鄰居的鄰居……直到訪問到所有相關的節點。

本文主要介紹如何實現圖的深度優先遍歷，以及為什麼它類似於二叉樹。

二、圖的深度優先遍歷

在實現圖的深度優先遍歷時，我們需要考慮如何遍歷每個節點，並標記哪些節點已經被遍歷過。

下面是一個示例圖，展示了深度優先遍歷中的遍歷順序：

     1 - 2 - 3
     |   |   |
     4 - 5 - 6

上圖中，我們從節點1開始遍歷，並首先訪問它的鄰居節點2。接着，我們訪問節點2的鄰居節點3，再訪問節點3的鄰居節點6……直到訪問了所有相關的節點。

下面給出實現圖的深度優先遍歷的代碼示例：

// 圖的鄰接表表示法
class Graph {
    constructor() {
        // 存儲圖的節點
        this.vertices = [];
        // 存儲圖的邊
        this.edges = new Map();
    }
    // 添加節點
    addVertex(v) {
        this.vertices.push(v);
        this.edges.set(v, []);
    }
    // 添加邊
    addEdge(v, w) {
        this.edges.get(v).push(w);
        this.edges.get(w).push(v);
    }
    // 深度優先遍歷
    dfs(startingNode) {
        const visited = new Set();
        this._dfs(startingNode, visited);
    }
    _dfs(vertex, visited) {
        visited.add(vertex);
        console.log(vertex);
        const neighbors = this.edges.get(vertex);
        for (let i = 0; i < neighbors.length; i++) {
            const neighbor = neighbors[i];
            if (!visited.has(neighbor)) {
                this._dfs(neighbor, visited);
            }
        }
    }
}

三、圖的深度優先遍歷類似於二叉樹的前序遍歷

雖然圖和二叉樹是兩種不同的數據結構，但它們之間的遍歷方式非常相似。圖的深度優先遍歷類似於二叉樹的前序遍歷，都是首先訪問本節點，接着訪問左子節點（或者鄰居節點），最後訪問右子節點（或者鄰居節點）。下面是一個對比圖和二叉樹前序遍歷的示意圖：

     圖的深度優先遍歷：           二叉樹的前序遍歷：
         1                           A
        / \                         / \
       2   4                       B   D
      / \   \                     / \   \
     3   5   6                   C   E   F
                                / \     / \
                               G   H   I   J

從上面的示意圖中可以看出，圖的深度優先遍歷和二叉樹的前序遍曆本質上是相同的遍歷方式。唯一的區別在於，圖沒有一個指定的根節點，而是從任一節點開始遍歷。

下面給出實現圖的深度優先遍歷類似於二叉樹前序遍歷的代碼示例：

class Graph {
    // ...
    // 深度優先遍歷類似於二叉樹前序遍歷
    dfs(node) {
        const visited = new Set();
        this._dfs(node, visited);
    }
    _dfs(node, visited) {
        visited.add(node);
        console.log(node);
        const neighbors = this.edges.get(node);
        for (const neighbor of neighbors) {
            if (!visited.has(neighbor)) {
                this._dfs(neighbor, visited);
            }
        }
    }
}

四、圖的深度優先遍歷與回溯

在實現圖的深度優先遍歷時，我們需要考慮如何在訪問之後回到原來的節點。相比於二叉樹的遍歷，圖的遍歷涉及到多個路徑，因此需要更加小心地考慮回溯的問題。

在深度優先遍歷過程中，我們使用遞歸函數來遍歷每個節點。如果我們走到一個死路，即當前節點沒有相鄰節點可訪問，那麼我們需要回到之前的節點（回溯），查找還有沒有相鄰節點可訪問。如果回到原來的節點後，還有未訪問的相鄰節點，那麼我們將繼續訪問，直到訪問完所有相關的節點。

下面給出實現遍歷時的回溯代碼示例：

class Graph {
    // ...
    // 深度優先遍歷
    dfs(startingNode) {
        const visited = new Set();
        this._dfs(startingNode, visited);
    }
    _dfs(node, visited) {
        visited.add(node);
        console.log(node);
        const neighbors = this.edges.get(node);
        for (const neighbor of neighbors) {
            if (!visited.has(neighbor)) {
                this._dfs(neighbor, visited);
            }
        }
    }
}

五、圖的深度優先遍歷與棧

在上面的示例代碼中，我們使用遞歸實現圖的深度優先遍歷。但遞歸調用可能會導致棧溢出的問題，特別是在遍歷大型圖時，很容易出現棧溢出錯誤。因此，我們可以使用棧（stack）來實現深度優先遍歷，而不是使用遞歸函數。

在使用棧實現深度優先遍歷時，我們需要考慮如何在遍歷完一個節點之後，回溯到它的前一個節點，並繼續遍歷。因此，我們需要維護一個棧，保存已經訪問過的節點。同時，我們還需要維護一個表，記錄每個節點是否已經被訪問過。

下面給出使用棧實現遍歷的代碼示例：

class Graph {
    // ...
  iter_dfs(startingNode) {
      const visited = new Set();
      const stack = [];
      stack.push(startingNode);
      while (stack.length !== 0) {
          const node = stack.pop();
          if (!visited.has(node)) {
              visited.add(node);
              console.log(node);
              const neighbors = this.edges.get(node);
              for (const neighbor of neighbors) {
                  if (!visited.has(neighbor)) {
                      stack.push(neighbor);
                  }
              }
          }
      }
  }
}

六、總結

對於圖的深度優先遍歷類似於二叉樹的前序遍歷，我們需要遍歷每個節點，並標記哪些節點已經被遍歷過。在實現遍歷時，我們需要考慮如何回溯到原來的節點，以及使用棧來替代遞歸實現深度優先遍歷。

圖的深度優先遍歷類似於二叉樹的前序遍歷，但需要注意的是，圖的遍歷涉及到多個路徑，因此需要更加小心地考慮回溯的問題。