题目
本实验实现邻接表表示下无向图的广度优先遍历。
程序的输入是图的顶点序列和边序列(顶点序列以*为结束标志,边序列以-1,-1为结束标志)。程序的输出为图的邻接表和广度优先遍历序列。例如:
程序输入为:
a
b
c
d
e
f
*
0,1
0,4
1,4
1,5
2,3
2,5
3,5
-1,-1
程序的输出为:
the ALGraph is
a 4 1
b 5 4 0
c 5 3
d 5 2
e 1 0
f 3 2 1
the Breadth-First-Seacrh list:aebfdc
测试输入 | 期待的输出 | 时间限制 | 内存限制 | 额外进程 | |
---|---|---|---|---|---|
测试用例 1 | 以文本方式显示
| 以文本方式显示
| 1秒 | 64M |
C++代码
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct Node {
char data;
int dataNum;
bool visited;
vector<int> edges;
};
vector<Node> nodeList;
void bfs(int startIndex) {
queue<int> nodeQueue;
nodeQueue.push(startIndex);
nodeList[startIndex].visited = true;
while (!nodeQueue.empty()) {
int currentIndex = nodeQueue.front();
nodeQueue.pop();
cout << nodeList[currentIndex].data;
for (int i = nodeList[currentIndex].dataNum-1; i >=0; i--) {
int nextIndex = nodeList[currentIndex].edges[i];
if (!nodeList[nextIndex].visited) {
nodeQueue.push(nextIndex);
nodeList[nextIndex].visited = true;
}
}
}
}
int main() {
char ch;
int numNodes = 0, indexA, indexB;
// 输入节点
while (cin >> ch && ch != '*') {
cin.ignore(); // 跳过换行符
Node node{ ch, 0, false, {} };
nodeList.push_back(node);
numNodes++;
}
// 输入边
while (cin >> indexA >>ch>> indexB && !(indexA == -1 && indexB == -1)) {
nodeList[indexA].edges.push_back(indexB);
nodeList[indexA].dataNum++;
nodeList[indexB].edges.push_back(indexA);
nodeList[indexB].dataNum++;
}
// 输出邻接表
cout << "the ALGraph is\n";
for (int i = 0; i < numNodes; ++i) {
cout << nodeList[i].data;
for (int j = nodeList[i].dataNum-1; j >=0 ; j--) {
cout << " " << nodeList[i].edges[j];
}
cout << endl;
}
// 执行BFS并输出结果
cout << "the Breadth-First-Seacrh list:";
for (int i = 0; i < nodeList.size(); i++)
{
if (!nodeList[i].visited )
{
bfs(i);
}
}
cout << endl;
}