速度优先遍历策略的基本思想

速度优先遍历策略（BFS）是一种基于队列实现的图遍历算法，它从图的起始节点开始遍历，逐层地向外扩展，直到遍历完所有节点。其基本思想是：先访问当前节点的所有邻居节点，再按照从左到右的顺序依次访问邻居节点的邻居节点，直到遍历完整个图。

BFS算法的过程如下：
1. 将起始节点放入队列中；
2. 从队列中取出第一个节点，访问该节点；
3. 将该节点的所有未访问的邻居节点加入队列中；
4. 重复步骤2和3，直到队列为空。

BFS算法的优点是可以找到从起始节点到目标节点的最短路径，因为它是按照层次遍历的。缺点是空间复杂度较高，需要开辟一个队列来保存节点。

相关问题

深度优先遍历策略的基本思想

深度优先遍历策略的基本思想是从根节点开始，选择一个子节点，沿着这个子节点一直往下走，直到走到底层节点或者走到一个没有未访问过的子节点的节点。然后回溯到上一个节点，继续选择另外一个未访问过的子节点，重复上述步骤，直到遍历完整个树。

具体来说，深度优先遍历策略可以通过递归实现。从根节点开始递归遍历，对于每个节点，先输出该节点的值，再依次遍历该节点的每个子节点，直到所有子节点都被遍历完毕。这样就完成了整个树的深度优先遍历。

深度优先遍历策略的优点是实现简单，空间复杂度较低。但是如果树的深度比较大，可能会导致递归过程中的栈溢出，因此需要考虑优化算法或者使用其他遍历策略。

pta 7-1 图的深度优先遍历

图的深度优先遍历（Depth-First Search, DFS）是一种常用的图遍历方法，其基本思想是从图中某个顶点出发，按照深度优先的策略进行遍历，直到图中所有顶点都被访问为止。

下面是一个基于邻接表存储的图的深度优先遍历的 C++ 实现代码：

const int MAXN = 1005;

vector<int> G[MAXN]; // 存储图的邻接表
bool vis[MAXN];      // 标记每个顶点是否被访问过

void dfs(int u) {
    vis[u] = true; // 标记当前顶点已被访问
    cout << u << " "; // 输出当前访问的顶点编号
    for (int i = 0; i < G[u].size(); ++i) {
        int v = G[u][i];
        if (!vis[v]) { // 如果顶点 v 还未被访问，则继续搜索
            dfs(v);
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m; // 输入图的结点个数和边数
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v; // 输入一条边 (u, v)
        G[u].push_back(v);
        G[v].push_back(u); // 无向图需加入反向边
    }

    // 从结点 1 开始进行深度优先遍历
    dfs(1);

    return 0;
}

其中，`G[u]` 存储与结点 `u` 相邻的结点，`vis[u]` 表示结点 `u` 是否被访问过，`dfs(u)` 表示从结点 `u` 开始进行深度优先遍历。在 `dfs(u)` 中，我们首先将结点 `u` 标记为已访问，然后输出其编号，最后对于 `u` 的每个邻接结点 `v`，如果 `v` 还未被访问，则递归调用 `dfs(v)` 进行继续搜索。