要实现广度优先遍历,可以使用队列来辅助。以下是将深度优先搜索改为广度优先搜索的代码:
#include <iostream>
#include <vector>
#include <map>
#include <queue>
class UndirectedGraph {
private:
int numVertices;
std::vector<std::vector<int>> adjacencyMatrix;
std::map<int, char> vertexNames;
std::vector<bool> visited;
public:
UndirectedGraph(int num) : numVertices(num), adjacencyMatrix(num, std::vector<int>(num, 0)), visited(num, false) {}
void setVertexName(int vertex, char name) {
if (vertex >= 0 && vertex < numVertices) {
vertexNames[vertex] = name;
}
}
void addEdge(int start, int end) {
if (start >= 0 && start < numVertices && end >= 0 && end < numVertices) {
adjacencyMatrix[start][end] = 1;
adjacencyMatrix[end][start] = 1; // Since the graph is undirected
}
}
void printAdjacencyMatrix() {
std::cout << " ";
for (int i = 0; i < numVertices; ++i) {
std::cout << vertexNames[i] << " ";
}
std::cout << std::endl;
for (int i = 0; i < numVertices; ++i) {
std::cout << vertexNames[i] << " ";
for (int j = 0; j < numVertices; ++j) {
std::cout << adjacencyMatrix[i][j] << " ";
}
std::cout << std::endl;
}
}
void BFS(int startVertex) {
visited.assign(numVertices, false); // Reset visited vector
std::queue<int> queue;
visited[startVertex] = true;
std::cout << vertexNames[startVertex] << " ";
queue.push(startVertex);
while (!queue.empty()) {
int currVertex = queue.front();
queue.pop();
for (int i = 0; i < numVertices; ++i) {
if (adjacencyMatrix[currVertex][i] == 1 && !visited[i]) {
visited[i] = true;
std::cout << vertexNames[i] << " ";
queue.push(i);
}
}
}
}
};
int main() {
// 创建一个有向图对象
UndirectedGraph graph(9);
// 设置顶点名称
graph.setVertexName(0, 'A');
graph.setVertexName(1, 'B');
graph.setVertexName(2, 'C');
graph.setVertexName(3, 'D');
graph.setVertexName(4, 'E');
graph.setVertexName(5, 'F');
graph.setVertexName(6, 'G');
graph.setVertexName(7, 'H');
graph.setVertexName(8, 'I');
// 添加边
graph.addEdge(0, 1); // A-B
graph.addEdge(0, 3); // A-D
graph.addEdge(0, 4); // A-E
graph.addEdge(1, 4);//BE
graph.addEdge(1, 2);//BC
graph.addEdge(2, 5);//CF
graph.addEdge(3, 6);//DG
graph.addEdge(4, 6);//EG
graph.addEdge(6, 7);//GH
graph.addEdge(8,6); / / HI
// 打印邻接矩阵
std::cout << "Adjacency Matrix:" << std::endl;
graph.printAdjacencyMatrix();
std::cout << std::endl;
// 从顶点A开始进行广度优先遍历
std::cout << "Breadth First Search starting from vertex A:" << std::endl;
graph.BFS(0);
std::cout << std::endl;
return 0;
}
这段代码将DFS函数改为了BFS函数,并使用队列来辅助进行广度优先搜索。输出结果将会按照广度优先的顺序打印节点名称。
内容由零声教学AI助手提供,问题来源于学员提问