1.简介

图是数据结构中的另一种数据结构，通常用来表示多对多的关系。在 C++ 中，图通常可以通过邻接表或邻接矩阵表示。
例如：

2.深度优先遍历dfs

下面先给出上面图例的深度优先遍历算法代码：

#include <iostream>
#include <vector>
#include <set>

using namespace std;

// 深度优先搜索函数
void depthFirstSearch(const vector<vector<int>>& graph, int node, set<int>& visited) {
    // 输出当前节点
    cout << node << " ";
    visited.insert(node); // 标记当前节点为已访问

    // 遍历所有邻接节点
    for (int neighbor : graph[node]) {
        if (visited.find(neighbor) == visited.end()) {
            depthFirstSearch(graph, neighbor, visited);
        }
    }
}

int main() {
    // 图的邻接表表示
    vector<vector<int>> graph = {
        {3, 1},       // 0 的邻接节点
        {0, 2, 6},    // 1 的邻接节点
        {1, 8},       // 2 的邻接节点
        {0, 6, 5},    // 3 的邻接节点
        {},           // 4 没有邻接节点
        {3, 7},       // 5 的邻接节点
        {3, 1, 8},    // 6 的邻接节点
        {5, 8},       // 7 的邻接节点
        {2, 6, 7}     // 8 的邻接节点
    };

    // 记录访问的节点
    set<int> visited;

    cout << "DFS traversal starting from node 0:" << endl;
    depthFirstSearch(graph, 0, visited);

    return 0;
}

3.广度优先遍历bfs

给出广度优先遍历算法代码：

#include <iostream>
#include <vector>
#include <queue>
#include <set>

using namespace std;

// 广度优先搜索函数
void breadthFirstSearch(const vector<vector<int>>& graph, int start) {
    queue<int> q;        // 队列，用于按层次遍历节点
    set<int> visited;    // 记录已访问的节点

    // 初始化：将起始节点加入队列并标记为已访问
    q.push(start);
    visited.insert(start);

    cout << "BFS traversal starting from node " << start << ":" << endl;

    while (!q.empty()) {
        int current = q.front();
        q.pop();

        // 输出当前节点
        cout << current << " ";

        // 遍历邻接节点
        for (int neighbor : graph[current]) {
            if (visited.find(neighbor) == visited.end()) {
                q.push(neighbor);
                visited.insert(neighbor);
            }
        }
    }
    cout << endl;
}

int main() {
    // 图的邻接表表示
    vector<vector<int>> graph = {
        {3, 1},       // 0 的邻接节点
        {0, 2, 6},    // 1 的邻接节点
        {1, 8},       // 2 的邻接节点
        {0, 6, 5},    // 3 的邻接节点
        {},           // 4 没有邻接节点
        {3, 7},       // 5 的邻接节点
        {3, 1, 8},    // 6 的邻接节点
        {5, 8},       // 7 的邻接节点
        {2, 6, 7}     // 8 的邻接节点
    };

    // 从节点 0 开始广度优先遍历
    breadthFirstSearch(graph, 0);

    return 0;
}

4.具体问题

4.1 岛屿的最大面积

题目链接

岛屿面积计算的核心是：从某个 1 出发，找到所有相邻的 1（上下左右连接），将其视为一个连通分量，统计该连通分量的面积。DFS 可以很好地完成这一需求：一旦找到一个起始点（1），DFS 会递归地深入探索其相邻的每个方向，直到完全探索整个连通分量（即这个岛屿）。在递归返回时，可以累计面积，最终得出整个岛屿的面积。
具体代码：

class Solution {
public:
    // 深度优先搜索函数
    int dfs(vector<vector<int>>& grid, int x, int y) {
        // 检查边界条件和是否已经访问过
        if (x < 0 || x >= grid.size() || y < 0 || y >= grid[0].size() ||
            grid[x][y] == 0) {
            return 0;
        }

        grid[x][y] = 0; // 将当前格子标记为已访问
        int area = 1;   // 当前格子的面积为 1

        // 递归检查四个方向
        area += dfs(grid, x + 1, y); // 下
        area += dfs(grid, x - 1, y); // 上
        area += dfs(grid, x, y + 1); // 右
        area += dfs(grid, x, y - 1); // 左

        return area;
    }

    // 计算最大岛屿面积的函数
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        int maxArea = 0;

        // 遍历整个网格
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == 1) {
                    // 计算当前岛屿的面积
                    int area = dfs(grid, i, j);
                    // 更新最大面积
                    maxArea = max(maxArea, area);
                }
            }
        }

        return maxArea;
    }
};

4.2 岛屿的数量

题目链接

遍历网格中的每个格子，遇到未访问过的 1 时，将其作为一个新的岛屿，启动搜索（DFS 或 BFS）。
搜索过程中，将所有属于同一岛屿的 1 标记为访问过。使用 DFS 或 BFS，从当前 1 出发，递归或迭代访问所有相邻的 1，直到整个岛屿被处理完。每次启动搜索时，岛屿数量 count 增加 1。遍历完网格后，count 即为岛屿的总数。
给出广度优先遍历的代码：

class Solution {
public:
    void bfs(vector<vector<char>>& grid, int x, int y) {
        // 定义方向数组
        vector<pair<int, int>> directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        queue<pair<int, int>> q;
        q.push({x, y});
        grid[x][y] = '0'; // 标记为已访问

        while (!q.empty()) {
            auto [cx, cy] = q.front();
            q.pop();

            // 遍历四个方向
            for (auto [dx, dy] : directions) {
                int nx = cx + dx, ny = cy + dy;
                if (nx >= 0 && nx < grid.size() && ny >= 0 &&
                    ny < grid[0].size() && grid[nx][ny] == '1') {
                    q.push({nx, ny});
                    grid[nx][ny] = '0'; // 标记为已访问
                }
            }
        }
    }

    int numIslands(vector<vector<char>>& grid) {
        int count = 0;

        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[0].size(); ++j) {
                if (grid[i][j] == '1') {
                    bfs(grid, i, j);
                    count++;
                }
            }
        }

        return count;
    }
};

5.总结

接下来用一个表格来对比分析一下：

特性	深度优先遍历（DFS）	广度优先遍历（BFS）
实现方式	使用递归或显式栈	使用队列
遍历顺序	尽可能沿一个分支深入	按层次逐步扩展
应用场景	适合路径搜索、连通性判断	适合最短路径、分层搜索
时间复杂度	O(V+E)	O(V+E)
空间复杂度	O(V)（递归栈）	O(V)（队列）

总结：DFS 更适合问题规模较小或需要深入搜索的场景（如路径搜索、连通分量）。BFS 更适合寻找最短路径或分层问题。根据问题特性我们选择合适的遍历方式，可以提高算法效率和代码清晰度。