C++练习题：进阶算法——广度优先搜索

第一部分：考点与作答区

考点：

搜索算法的概念
广度优先搜索的原理
广度优先搜索的实现

作答区： 编写一个C++程序，完成以下要求：

使用广度优先搜索算法在一个有向图中查找最短路径。
打印查找结果。

请在下方空白处编写代码：

// 在此处编写代码

第二部分：解题思路与答案

解题思路：

首先，了解广度优先搜索的原理。广度优先搜索是一种用于遍历或搜索树或图的算法，它从起始节点开始，沿着树的宽度遍历，先访问起始节点的所有邻居节点，然后再访问这些邻居节点的邻居节点，以此类推。
然后，实现广度优先搜索算法。在实现过程中，可以使用队列来实现广度优先搜索，将起始节点放入队列中，并标记为已访问。然后，从队列中取出一个节点，访问它的所有未访问的邻居节点，并将这些邻居节点放入队列中，同时标记为已访问。重复这个过程，直到队列为空。
最后，打印查找结果。

答案：

#include <iostream>
#include <queue>// 定义图节点
struct GraphNode {int value;std::vector<GraphNode *> neighbors;GraphNode(int x) : value(x) {}
};// 广度优先搜索函数
std::vector<GraphNode *> breadthFirstSearch(GraphNode *start) {std::vector<GraphNode *> result;std::queue<GraphNode *> queue;std::vector<bool> visited(start->neighbors.size(), false);queue.push(start);visited[start->value] = true;while (!queue.empty()) {GraphNode *current = queue.front();queue.pop();result.push_back(current);for (GraphNode *neighbor : current->neighbors) {if (!visited[neighbor->value]) {queue.push(neighbor);visited[neighbor->value] = true;}}}return result;
}int main() {// 创建有向图GraphNode *start = new GraphNode(1);GraphNode *node2 = new GraphNode(2);GraphNode *node3 = new GraphNode(3);GraphNode *node4 = new GraphNode(4);GraphNode *node5 = new GraphNode(5);start->neighbors = {node2, node3};node2->neighbors = {node4};node3->neighbors = {node5};node4->neighbors = {};node5->neighbors = {};// 使用广度优先搜索算法查找最短路径std::vector<GraphNode *> shortestPath = breadthFirstSearch(start);// 打印查找结果for (GraphNode *node : shortestPath) {std::cout << "Node with value " << node->value << " visited." << std::endl;}// 清理图内存delete start;delete node2;delete node3;delete node4;delete node5;return 0;
}

在这段代码中，我们首先包含 <iostream> 头文件，并定义了一个图节点结构体。然后，我们使用广度优先搜索算法在有向图中查找最短路径，并打印查找结果。通过这种方式，我们展示了广度优先搜索算法的实现和基本用法。

第三部分：扩展考点与扩展作答区

扩展考点：

广度优先搜索的应用场景
广度优先搜索的变体

扩展作答区： 在原有程序的基础上，增加以下功能：

使用广度优先搜索算法在一个有向图中查找所有从起始节点到目标节点的路径。
讨论广度优先搜索在网络路由和图的遍历中的应用。