将刚才的那个写成一个完整的代码
时间: 2024-02-15 15:01:39 浏览: 31
好的,下面是一个完整的代码实现,包括邻接矩阵和邻接表的建立,广度优先遍历和深度优先遍历。
```c++
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
const int MAXN = 100; // 最大顶点数
// 邻接矩阵的建立
int G[MAXN][MAXN]; // 邻接矩阵
void buildGraphByMatrix() {
memset(G, 0, sizeof(G)); // 初始化邻接矩阵
int n, m; // n为顶点数,m为边数
cin >> n >> m; // 输入顶点数和边数
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v; // 输入边的两个端点
G[u][v] = G[v][u] = 1; // 表示两个顶点之间有边相连
}
}
// 邻接表的建立
struct Edge {
int to, next;
}; // 边的结构体
Edge edges[MAXN * 2]; // 边的数组
int head[MAXN], cnt; // head数组存储每个顶点对应的链表头,cnt表示边的数量
void addEdge(int u, int v) { // 添加边
edges[cnt].to = v;
edges[cnt].next = head[u];
head[u] = cnt++;
}
void buildGraphByList() {
memset(head, -1, sizeof(head)); // 初始化邻接表
cnt = 0;
int n, m; // n为顶点数,m为边数
cin >> n >> m; // 输入顶点数和边数
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v; // 输入边的两个端点
addEdge(u, v); // 添加边
addEdge(v, u);
}
}
// 广度优先遍历
void bfs(int s, int n) {
queue<int> q; // 定义队列
bool vis[MAXN] = {false}; // 标记数组,用于记录每个顶点是否被访问过
q.push(s); // 将起点加入队列
vis[s] = true; // 标记起点为已访问
while (!q.empty()) {
int u = q.front();
q.pop(); // 取出队首顶点
cout << u << " "; // 输出顶点
for (int v = 1; v <= n; v++) {
if (G[u][v] && !vis[v]) { // 如果顶点v与u相邻且未访问过
q.push(v); // 将v加入队列
vis[v] = true; // 标记v为已访问
}
}
}
}
// 深度优先遍历
void dfs(int u) {
bool vis[MAXN] = {false}; // 标记数组,用于记录每个顶点是否被访问过
vis[u] = true; // 标记顶点u为已访问
cout << u << " "; // 输出顶点
for (int i = head[u]; i != -1; i = edges[i].next) {
int v = edges[i].to;
if (!vis[v]) { // 如果顶点v未访问过
dfs(v); // 继续访问顶点v
}
}
}
int main() {
// 邻接矩阵的建立
buildGraphByMatrix();
// 邻接表的建立
// buildGraphByList();
// 广度优先遍历
int s = 1; // 从顶点1开始遍历
int n; // 顶点数
cin >> n; // 输入顶点数
bfs(s, n);
// 深度优先遍历
// int s = 1; // 从顶点1开始遍历
// dfs(s);
return 0;
}
```
你可以根据需要选择邻接矩阵或邻接表作为图的存储结构,然后调用相应的函数进行广度优先遍历或深度优先遍历。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.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)
![](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)