首页编写一个C++程序,使用邻接矩阵定义图并实现图的广度优先遍历算法,并在主函数中输

编写一个C++程序,使用邻接矩阵定义图并实现图的广度优先遍历算法,并在主函数中输

时间: 2024-12-20 20:16:45 浏览: 70

编写一个C++程序来实现图的广度优先遍历（BFS）通常需要以下几个步骤：首先，我们需要定义一个邻接矩阵来表示图，这是一二维数组，其中`matrix[i][j]`为0或1，分别代表两个顶点之间是否有边连接。 ```cpp #include <iostream> #include <vector> using namespace std; const int MAX_V = 100; // 图的最大顶点数 // 邻接矩阵表示图 vector<vector<int>> adjMatrix(MAX_V, vector<int>(MAX_V, 0)); ``` 接下来，我们可以定义一个BFS辅助函数，接受起点作为参数： ```cpp void bfs(int start) { vector<bool> visited(MAX_V, false); // 记录每个顶点是否被访问过 queue<int> q; // 用于存储待访问的顶点 // 标记起点为已访问，添加到队列中 visited[start] = true; q.push(start); while (!q.empty()) { int curr = q.front(); // 取出队首元素 cout << curr << " "; // 输出当前顶点 // 遍历相邻的顶点，若未访问则标记并添加到队列 for (int i = 0; i < MAX_V; ++i) { if (adjMatrix[curr][i] && !visited[i]) { visited[i] = true; q.push(i); } } q.pop(); // 移除已经访问过的顶点 } } ``` 最后，在`main`函数中，你可以输入图的邻接矩阵，并调用`bfs`函数： ```cpp int main() { // 初始化邻接矩阵，这里仅做示例，实际应用中你需要根据图的实际结构填充 // ... int startNode; // 起点 cout << "请输入起始顶点: "; cin >> startNode; bfs(startNode); return 0; } ``` 运行这个程序时，用户会根据提示输入起始顶点，然后程序会执行BFS并打印遍历路径。记得要处理输入错误和边界情况哦。

阅读全文