3. 图遍历¶

3.1. 图遍历¶

许多图应用需要按某种特定顺序基于图的拓扑结构访问图的顶点。这被称为图的遍历，在概念上类似于树遍历。回想一下，树遍历以某种指定的顺序（如前序、中序或后序）恰好访问每个节点一次。存在多种树遍历，因为各种应用需要按特定顺序访问节点。例如，要按升序打印 BST 的节点需要中序遍历而不是其他遍历。标准的图遍历顺序也存在。每种都适用于解决某些问题。例如，人工智能编程中的许多问题都使用图建模。问题领域可能由大量状态组成，各状态对之间有连接。解决这类问题需要通过仅通过连接在状态之间移动，从指定的起始状态到达指定的目标状态。通常，起始和目标状态不直接连接。要解决此问题，必须以某种有组织的方式搜索图的顶点。

图遍历算法通常从起始顶点开始，尝试从那里访问其余顶点。图遍历必须处理许多棘手的情况。首先，可能无法从起始顶点到达所有顶点。这发生在图不连通时。其次，图可能包含环，我们必须确保环不会导致算法进入无限循环。

图遍历算法可以通过在适当时将顶点标记为 VISITED 来解决这两个问题。在算法开始时，没有顶点被标记为 VISITED 。当顶点在遍历期间首次被访问时设置其标志。如果在遍历期间遇到已标志的顶点，则不第二次访问它。这可以防止程序在遇到环时进入无限循环。

遍历算法完成后，我们可以通过检查它们是否已设置 VISITED 标志来检查所有顶点是否已被处理。如果并非所有顶点都已标志，我们可以从未访问的顶点继续遍历。请注意，无论图是有向还是无向的，此过程都有效。要确保访问所有顶点，可以在图 \(\mathbf{G}\) 上如下调用 graphTraverse ：

Java
Java (Generic)

static void graphTraverse(Graph G) {
  int v;
  for (v=0; v<G.nodeCount(); v++) {
    G.setValue(v, UNVISITED); // Initialize
  }
  for (v=0; v<G.nodeCount(); v++) {
    if (G.getValue(v) != VISITED) {
      doTraversal(G, v);
    }
  }
}

static void graphTraverse(Graph G) {
  int v;
  for (v=0; v<G.nodeCount(); v++) {
    G.setValue(v, null); // Initialize
  }
  for (v=0; v<G.nodeCount(); v++) {
    if (G.getValue(v) != VISITED) {
      doTraversal(G, v);
    }
  }
}

函数 doTraversal 可以使用接下来描述的图遍历之一来实现。

3.1.1. 深度优先搜索¶

我们有组织图遍历的第一种方法叫做深度优先搜索（DFS）。每当在搜索期间访问顶点 \(v\) 时， DFS 将递归访问 \(v\) 的所有未访问邻居。等价地，DFS 将从 \(v\) 出去的所有边添加到栈中。下一个要访问的顶点通过弹出栈并沿该边移动来确定。效果是沿图中的一个分支到其结论，然后回退并沿另一个分支，依此类推。 DFS 过程可用于定义深度优先搜索树。此树由遍历期间跟随到任何新（未访问）顶点的边组成，不包括通向已访问顶点的边。 DFS 可以应用于有向图或无向图。

此可视化展示了一个图以及对其进行 DFS 的结果，产生深度优先搜索树。

Settings

Saving...

Server Error
Resubmit

以下是 DFS 算法的实现。

Java
Java (Generic)

static void DFS(Graph G, int v) {
  PreVisit(G, v);
  G.setValue(v, VISITED);
  int[] nList = G.neighbors(v);
  for (int i=0; i< nList.length; i++) {
    if (G.getValue(nList[i]) != VISITED) {
      DFS(G, nList[i]);
    }
  }
  PostVisit(G, v);
}

static void DFS(Graph G, int v) {
  PreVisit(G, v);
  G.setValue(v, VISITED);
  int[] nList = G.neighbors(v);
  for (int i=0; i< nList.length; i++) {
    if (G.getValue(nList[i]) != VISITED) {
      DFS(G, nList[i]);
    }
  }
  PostVisit(G, v);
}

此实现包含对函数 PreVisit 和 PostVisit 的调用。这些函数指定在搜索期间应执行什么活动。正如前序树遍历需要在访问子树之前采取行动一样，一些图遍历要求在 DFS 中更靠前的顶点之前处理顶点。或者，一些应用需要在其余顶点处理之后执行活动；因此调用函数 PostVisit 。这是利用访问者设计模式的自然机会。

以下可视化每次启动时显示一个随机图，以便你可以看到不同示例上的行为。它可以在有向图或无向图上显示 DFS。请确保查看每种图类型的示例。

DFS 在有向图中每条边处理一次。在无向图中，DFS 从两个方向处理每条边。每个顶点必须被访问但只访问一次，因此总成本为 \(\Theta(|\mathbf{V}| + |\mathbf{E}|)\)。

以下是让你练习 DFS 的练习。

3.2. 广度优先搜索¶

我们的第二种图遍历算法叫做广度优先搜索（BFS）。 BFS 在访问更远的顶点之前，先检查与起始顶点相连的所有顶点。 BFS 的实现类似于 DFS，但用队列替换了递归栈。请注意，如果图是一棵树且起始顶点在根处， BFS 等价于从上到下逐层访问顶点。

此可视化展示了一个图以及对其进行 BFS 的结果，产生广度优先搜索树。

Settings

Saving...

Server Error
Resubmit

以下是 BFS 的实现。

Java
Java (Generic)

static void BFS(Graph G, int v) {
  LQueue Q = new LQueue(G.nodeCount());
  Q.enqueue(v);
  G.setValue(v, VISITED);
  while (Q.length() > 0) { // Process each vertex on Q
    v = (Integer)Q.dequeue();
    PreVisit(G, v);
    int[] nList = G.neighbors(v);
    for (int i=0; i< nList.length; i++) {
      if (G.getValue(nList[i]) != VISITED) { // Put neighbors on Q
        G.setValue(nList[i], VISITED);
        Q.enqueue(nList[i]);
      }
    }
    PostVisit(G, v);
  }
}

static void BFS(Graph G, int v) {
  LQueue Q = new LQueue(G.nodeCount());
  Q.enqueue(v);
  G.setValue(v, VISITED);
  while (Q.length() > 0) { // Process each vertex on Q
    v = (Integer)Q.dequeue();
    PreVisit(G, v);
    int[] nList = G.neighbors(v);
    for (int i=0; i< nList.length; i++) {
      if (G.getValue(nList[i]) != VISITED) { // Put neighbors on Q
        G.setValue(nList[i], VISITED);
        Q.enqueue(nList[i]);
      }
    }
    PostVisit(G, v);
  }
}

以下可视化每次启动时显示一个随机图，以便你可以看到不同示例上的行为。它可以在有向图或无向图上显示 BFS。请确保查看每种图类型的示例。

以下是让你练习 BFS 的练习。

待处理

type: Exercise: 图遍历总结练习。

OpenDSA 全教程

Chapter 19 Graphs

3. 图遍历¶

3.1. 图遍历¶

3.1.1. 深度优先搜索¶

3.2. 广度优先搜索¶