用c语言构造一个无向图,从给定起点开始进行深度优先遍历和广度优先遍历,并输出相应的遍历序列。
时间: 2024-02-15 09:03:59 浏览: 226
无向图建立、深度优先遍历和广度优先遍历实现算法[借鉴].pdf
5星 · 资源好评率100%
好的,下面是一个基于邻接矩阵的无向图深度优先遍历和广度优先遍历的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAXN 10 // 最大节点数
#define MAXM 50 // 最大边数
int graph[MAXN][MAXN]; // 邻接矩阵
bool visited[MAXN]; // 标记节点是否被访问
// 深度优先遍历
void dfs(int node) {
visited[node] = true;
printf("%d ", node);
for (int i = 0; i < MAXN; i++) {
if (graph[node][i] && !visited[i]) {
dfs(i);
}
}
}
// 广度优先遍历
void bfs(int node) {
int queue[MAXN], front = 0, rear = 0;
visited[node] = true;
printf("%d ", node);
queue[rear++] = node;
while (front < rear) {
int cur = queue[front++];
for (int i = 0; i < MAXN; i++) {
if (graph[cur][i] && !visited[i]) {
visited[i] = true;
printf("%d ", i);
queue[rear++] = i;
}
}
}
}
int main() {
int n, m, s; // 节点数、边数、起始节点编号
scanf("%d %d %d", &n, &m, &s);
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
graph[u][v] = graph[v][u] = 1; // 无向图,两个方向都要连接
}
printf("Depth first search:\n");
dfs(s);
printf("\n");
for (int i = 0; i < MAXN; i++) {
visited[i] = false; // 重置访问标记
}
printf("Breadth first search:\n");
bfs(s);
printf("\n");
return 0;
}
```
这段代码中,我们首先定义了一个邻接矩阵来表示无向图,同时使用一个bool数组visited来标记每个节点是否被访问过。
在深度优先遍历和广度优先遍历时,我们通过递归和队列来实现节点的遍历。在遍历时,对于每个节点,我们遍历它的所有邻居节点,如果该邻居节点没有被访问过,就将它加入遍历队列中,并标记为已访问。
最后,我们在主函数中读入节点数、边数和起始节点编号,构造无向图,然后分别进行深度优先遍历和广度优先遍历,并输出遍历序列。
希望这段代码可以对您有所帮助!
阅读全文