pta邻接矩阵的广度优先遍历
时间: 2025-01-10 19:32:57 浏览: 64
### PTA 邻接矩阵广度优先遍历算法实现
对于基于邻接矩阵的广度优先遍历(BFS),该方法适用于表示图结构并执行搜索操作。当采用邻接矩阵来存储图时,每个节点与其他所有节点之间的连接关系通过二维数组中的元素反映出来。
下面展示了一个完整的C++程序用于在给定的图上执行广度优先遍历:
```cpp
#include <iostream>
#include <queue>
using namespace std;
const int MAX_V = 100; // 假设最大顶点数为100
bool visited[MAX_V]; // 记录各顶点是否被访问过
int adjMatrix[MAX_V][MAX_V];
void bfs(int startVertex, int vertexCount) {
queue<int> q;
visited[startVertex] = true;
q.push(startVertex);
while (!q.empty()) {
int currentVertex = q.front();
cout << "Visited: " << currentVertex << endl;
q.pop();
for (int i = 0; i < vertexCount; ++i) { // 对于每一个相邻结点
if (adjMatrix[currentVertex][i] && !visited[i]) {
visited[i] = true;
q.push(i);
}
}
}
}
// 初始化函数,设置初始状态
void initialize() {
fill_n(visited, MAX_V, false); // 将所有的visited初始化为false
memset(adjMatrix, 0, sizeof(adjMatrix)); // 清零邻接矩阵
}
int main() {
int V, E;
cin >> V >> E; // 输入顶点数量和边的数量
initialize(); // 调用初始化函数
for (int i = 0; i < E; ++i) {
int u, v;
cin >> u >> v;
adjMatrix[u][v] = adjMatrix[v][u] = 1; // 设置无向图的双向链接
}
bfs(0, V); // 开始于第一个顶点进行BFS
}
```
此代码片段展示了如何利用队列数据结构来进行广度优先遍历[^1]。需要注意的是,在实际应用中应当考虑更复杂的场景,比如处理有向图或是加权图的情况。
阅读全文