图的深度优先遍历类似于二叉树

发布时间：2023-05-20

一、概述

图是计算机科学中的一类非常重要的数据结构，用于描述物体间的关系。在图中，节点（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);
                  }
              }
          }
      }
  }
}

六、总结

对于图的深度优先遍历类似于二叉树的前序遍历，我们需要遍历每个节点，并标记哪些节点已经被遍历过。在实现遍历时，我们需要考虑如何回溯到原来的节点，以及使用栈来替代递归实现深度优先遍历。 图的深度优先遍历类似于二叉树的前序遍历，但需要注意的是，图的遍历涉及到多个路径，因此需要更加小心地考虑回溯的问题。

推荐文章