本文共 3150 字，大约阅读时间需要 10 分钟。

图的遍历是图算法中核心的操作之一，它在解决连通性问题、拓扑排序以及关键路径分析等领域发挥着重要作用。然而，图的复杂性决定了遍历过程中需要应对多种挑战。

深度优先遍历（Depth-First Search，DFS）

深度优先遍历是一种通过递归访问所有可能路径来遍历图的方法。其核心策略是在访问当前节点后，优先选择当前节点的第一个邻接点进行深入访问。这种方式确保了在访问过程中尽可能深入当前路径，从而尽可能多地探索节点之间的关系。

具体而言，深度优先遍历可以按照以下步骤进行：

这种方法的优点在于能够深入探索节点之间的关系，适用于检测图的连通性或进行拓扑排序等任务。然而，其缺点也显而易见：如果图中存在环路，深度优先遍历可能会陷入无限循环，需要额外的机制（如访问标记）来避免重复访问节点。

广度优先遍历（Breadth-First Search，BFS）

广度优先遍历则是一种“层序”遍历方法，它类似于树的宽度优先搜索。这种方法使用队列来管理待访问的节点，每次从队列中取出当前节点，访问其所有未被访问的邻接点，并将这些邻接点加入队列中。

广度优先遍历的具体步骤如下：

广度优先遍历的优点在于能够逐层访问节点，确保先访问距离起始点较近的节点。这一特性使其特别适合用于图的最短路径计算等任务。其缺点是相较于深度优先遍历，可能需要较大的内存空间来存储队列中的节点。

深度优先遍历与广度优先遍历的对比

• 深度优先遍历：更注重路径的深度，适合探索节点之间的深层关系。
• 广度优先遍历：更注重层次的宽度，适合逐层扩展节点，确保所有节点按层次访问。

实现代码示例

以下是深度优先遍历和广度优先遍历的代码实现示例：

深度优先遍历代码

#include 
   
    
#include 
    
     
#include 
     
      
using namespace std;
const int maxn = 100;
int a[maxn][maxn] = {0};
bool ju[maxn][maxn] = {false};
int n, m;
void dfs(int x, int y) {
    if (ju[x][y]) return;
    ju[x][y] = true;
    cout << x << "," << y << " ";
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (ju[i][j]) continue;
            if (a[i][j] == 1) {
                dfs(i, j);
            }
        }
    }
}
int main() {
    scanf("%d %d", &n, &m);
    ju[n][m] = true;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            ju[i][j] = false;
        }
    }
    dfs(0, 0);
    return 0;
}
     
    
   

广度优先遍历代码

#include 
   
    
#include 
    
     
#include 
     
      
#include 
      
       
using namespace std;
const int maxn = 100;
int a[maxn][maxn] = {0};
bool ju[maxn][maxn] = {false};
int n, m;
struct node {
    int x, y;
    node(int x_, int y_) : x(x_), y(y_) {}
};
bool judge(int xx, int yy) {
    if (xx < 0 || xx >= n || yy < 0 || yy >= m) return false;
    if (ju[xx][yy] || a[xx][yy] == 0) return false;
    return true;
}
void bfs(int xx, int yy) {
    node no = {xx, yy};
    ju[xx][yy] = true;
    queue
       
         q;
    q.push(no);
    while (!q.empty()) {
        node current = q.front();
        q.pop();
        for (int i = 0; i < 4; ++i) {
            int nx = current.x + dx[i];
            int ny = current.y + dy[i];
            if (judge(nx, ny)) {
                ju[nx][ny] = true;
                node next = {nx, ny};
                q.push(next);
            }
        }
    }
}
int main() {
    scanf("%d %d", &n, &m);
    fill(ju[0], ju[0] + maxn * maxn, false);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (!ju[i][j] && a[i][j] == 1) {
                bfs(i, j);
                ans++;
            }
        }
    }
    cout << ans << endl;
    return 0;
}
       
      
     
    
   

例题解答

给定一个n×m的二进制矩阵，矩阵中的元素为0或1。相邻节点包括上下左右四个方向。若矩阵中有若干个1，它们构成一个“块”，则块的个数是多少？

解答步骤：

示例矩阵：

0 0 1 0 0
0 0 0 0 0
0 0 0 0 1
1 1 1 0 0
1 1 0 0 0

解答：块的个数为4。

转载地址：http://ellm.baihongyu.com/