用C++ 完成图的创建(邻接矩阵或邻接表实现)及深度或广度优先遍历;输出顶点信息、邻接矩阵或邻接表、遍历序列
时间: 2024-06-13 15:09:06 浏览: 10
以下是C++实现图的邻接表存储和广度优先遍历的示例代码:
```cpp
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
const int MAXN = 100; // 最大顶点数
vector<int> G[MAXN]; // 邻接表存储图
bool vis[MAXN]; // 标记数组,记录每个顶点是否被访问过
// 添加边
void addEdge(int u, int v) {
G[u].push_back(v);
G[v].push_back(u);
}
// 深度优先遍历
void dfs(int u) {
vis[u] = true;
cout << u << " "; // 输出遍历到的顶点
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (!vis[v]) {
dfs(v);
}
}
}
// 广度优先遍历
void bfs(int u) {
queue<int> q;
q.push(u);
vis[u] = true;
while (!q.empty()) {
int u = q.front();
q.pop();
cout << u << " "; // 输出遍历到的顶点
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
if (!vis[v]) {
vis[v] = true;
q.push(v);
}
}
}
}
int main() {
int n, m;
cin >> n >> m; // 输入顶点数和边数
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v; // 输入边的两个端点
addEdge(u, v); // 添加边
}
// 输出邻接表
for (int u = 1; u <= n; u++) {
cout << u << ": ";
for (int i = 0; i < G[u].size(); i++) {
int v = G[u][i];
cout << v << " ";
}
cout << endl;
}
// 深度优先遍历
cout << "DFS: ";
for (int u = 1; u <= n; u++) {
if (!vis[u]) {
dfs(u);
}
}
cout << endl;
// 广度优先遍历
memset(vis, false, sizeof(vis)); // 重置标记数组
cout << "BFS: ";
for (int u = 1; u <= n; u++) {
if (!vis[u]) {
bfs(u);
}
}
cout << endl;
return 0;
}
```
输入格式为:第一行输入顶点数n和边数m,接下来m行每行输入一条边的两个端点u和v。
输出格式为:首先输出邻接表,然后分别输出深度优先遍历和广度优先遍历的遍历序列。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)