c++编程当输入无向图的相邻点连接情况时,生成邻接表并由邻接表生成深度和广度优先序列
时间: 2023-11-22 08:52:27 浏览: 33
生成邻接表的代码可以如下实现:
```cpp
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int MAXN = 1000; // 最大点数
vector<int> G[MAXN]; // 邻接表存图
void add_edge(int u, int v) {
G[u].push_back(v);
G[v].push_back(u); // 无向图需要加两次
}
int main() {
int n, m; // n: 点数, m: 边数
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
add_edge(u, v);
}
// 输出邻接表
for (int u = 1; u <= n; ++u) {
cout << u << ": ";
for (int i = 0; i < G[u].size(); ++i) {
cout << G[u][i] << " ";
}
cout << endl;
}
return 0;
}
```
生成深度优先序列的代码可以如下实现:
```cpp
#include <iostream>
#include <vector>
#include <stack>
#include <cstring>
using namespace std;
const int MAXN = 1000; // 最大点数
vector<int> G[MAXN]; // 邻接表存图
bool vis[MAXN]; // 标记数组
void add_edge(int u, int v) {
G[u].push_back(v);
G[v].push_back(u); // 无向图需要加两次
}
void dfs(int u) {
cout << u << " ";
vis[u] = true;
for (int i = 0; i < G[u].size(); ++i) {
int v = G[u][i];
if (!vis[v]) {
dfs(v);
}
}
}
int main() {
int n, m; // n: 点数, m: 边数
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
add_edge(u, v);
}
// 从每个未被访问的点开始进行深度优先遍历
memset(vis, false, sizeof(vis));
for (int u = 1; u <= n; ++u) {
if (!vis[u]) {
dfs(u);
}
}
cout << endl;
return 0;
}
```
生成广度优先序列的代码可以如下实现:
```cpp
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
const int MAXN = 1000; // 最大点数
vector<int> G[MAXN]; // 邻接表存图
bool vis[MAXN]; // 标记数组
void add_edge(int u, int v) {
G[u].push_back(v);
G[v].push_back(u); // 无向图需要加两次
}
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]) {
q.push(v);
vis[v] = true;
}
}
}
}
int main() {
int n, m; // n: 点数, m: 边数
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
add_edge(u, v);
}
// 从每个未被访问的点开始进行广度优先遍历
memset(vis, false, sizeof(vis));
for (int u = 1; u <= n; ++u) {
if (!vis[u]) {
bfs(u);
}
}
cout << endl;
return 0;
}
```