用C++设计一个无向图的邻接矩阵类,输出无向图从顶点0出发的深度优先遍历和广度优先遍历的结果。要求:无向图中顶点数在10个以内。
时间: 2025-01-05 14:40:52 浏览: 7
在C++中,我们可以创建一个邻接矩阵类来表示无向图,然后使用深度优先搜索(DFS)和广度优先搜索(BFS)算法来遍历图。这里是一个简单的示例:
```cpp
#include <iostream>
#include <vector>
class Graph {
private:
int V; // 顶点数
std::vector<std::vector<int>> adj; // 邻接矩阵
public:
Graph(int vertices) : V(vertices), adj(V, std::vector<int>(V, 0)) {}
void addEdge(int src, int dest) {
adj[src][dest] = 1;
adj[dest][src] = 1; // 由于图是无向的,添加双向边
}
// 深度优先搜索
void DFS(int v, bool visited[]) {
visited[v] = true;
std::cout << v << " ";
for (int i = 0; i < V; ++i)
if (adj[v][i] && !visited[i])
DFS(i, visited);
}
// 广度优先搜索
void BFS(int v) {
bool visited[V] = {false};
std::queue<int> q;
q.push(v);
while (!q.empty()) {
v = q.front();
q.pop();
visited[v] = true;
std::cout << v << " ";
for (int i = 0; i < V; ++i)
if (adj[v][i] && !visited[i])
q.push(i);
}
}
// 从顶点0开始遍历
void traverse() {
std::cout << "Depth First Search (starting from vertex 0): ";
DFS(0, new bool[V]);
std::cout << "\n";
std::cout << "Breadth First Search (starting from vertex 0): ";
BFS(0);
}
};
int main() {
int vertices = 5; // 假设只有5个顶点
Graph g(vertices);
// 添加边...
g.traverse();
return 0;
}
```
在这个例子中,我们首先创建了一个`Graph`类,它包含顶点数`V`和一个邻接矩阵`adj`。`addEdge`方法用于添加边,`DFS`和`BFS`分别实现了深度优先和广度优先遍历。`traverse`函数结合了这两个功能,从顶点0开始进行遍历。
注意,这个程序仅作为演示,实际应用中你需要处理用户输入或已知的顶点和边,同时对于顶点数在10个以内的需求,邻接矩阵会更为合适。运行此代码后,它将输出从顶点0出发的DFS和BFS结果。
阅读全文