14.3. 图遍历¶
14.3.1. 图遍历¶
许多图应用需要基于图的拓扑结构，按某种特定顺序访问图的顶点。这被称为图的 遍历，在概念上类似于 树遍历。回想一下，树遍历以某种指定的顺序（如前序、中序或后序）恰好访问每个节点一次。存在多种树遍历，因为各种应用需要按特定顺序访问节点。例如，要按升序打印 BST 的节点需要中序遍历而不是其他遍历。标准的图遍历顺序也存在。每种都适用于解决某些问题。例如，人工智能编程中的许多问题都使用图建模。问题领域可能由大量状态组成，各状态对之间有连接。解决这类问题需要通过仅通过连接在状态之间移动，从指定的起始状态到达指定的目标状态。通常，起始和目标状态不直接连接。要解决此问题，必须以某种有组织的方式搜索图的顶点。
图遍历算法通常从起始顶点开始，尝试从那里访问其余顶点。图遍历必须处理许多棘手的情况。首先，可能无法从起始顶点到达所有顶点。这发生在图不连通时。其次，图可能包含环，我们必须确保环不会导致算法进入无限循环。
图遍历算法可以通过在适当时将顶点标记为 VISITED 来解决这两个问题。在算法开始时，没有顶点被标记为 VISITED 。当顶点在遍历期间首次被访问时设置其标志。如果在遍历期间遇到已标志的顶点，则不第二次访问它。这可以防止程序在遇到环时进入无限循环。
遍历算法完成后，我们可以通过检查它们是否已设置 VISITED 标志来检查所有顶点是否已被处理。如果并非所有顶点都已标志，我们可以从未访问的顶点继续遍历。请注意，无论图是有向还是无向的，此过程都有效。要确保访问所有顶点，可以在图 \(\mathbf{G}\) 上如下调用 graphTraverse ：
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 可以使用接下来描述的图遍历之一来实现。
14.3.1.1. 深度优先搜索¶
我们有组织图遍历的第一种方法叫做 深度优先搜索 （DFS）。每当在搜索期间访问顶点 \(v\) 时， DFS 将递归访问 \(v\) 的所有未访问邻居。等价地，DFS 将从 \(v\) 出去的所有边添加到栈中。下一个要访问的顶点通过弹出栈并沿该边移动来确定。效果是沿图中的一个分支到其结论，然后回退并沿另一个分支，依此类推。 DFS 过程可用于定义 深度优先搜索树。此树由遍历期间跟随到任何新（未访问）顶点的边组成，不包括通向已访问顶点的边。 DFS 可以应用于有向图或无向图。
此可视化展示了一个图以及对其进行 DFS 的结果，产生深度优先搜索树。
以下是 DFS 算法的实现。
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 的练习。
14.3.2. 广度优先搜索¶
我们的第二种图遍历算法叫做 广度优先搜索 （BFS）。 BFS 在访问更远的顶点之前，先检查与起始顶点相连的所有顶点。 BFS 的实现类似于 DFS，但用队列替换了递归栈。请注意，如果图是一棵树且起始顶点在根处， BFS 等价于从上到下逐层访问顶点。
此可视化展示了一个图以及对其进行 BFS 的结果，产生广度优先搜索树。
以下是 BFS 的实现。
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 的练习。
