一个无向图 V(G1)={0,1,2,3,4,5,6,7,8,9,10} 边集合 E(G1)={(0,1),(0,2),(0,3),(1,4),(1,5),(2,5),(2,6),(3,7),(6,8),(6,9),(7,10)}由用户输入一个结点的值,输出该结点的深度优先遍历和广度优先遍历序列,用c语言完成上述代码
时间: 2023-06-19 22:05:21 浏览: 53
以下是 C 语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 11
// 定义邻接表节点结构体
typedef struct node {
int index;
struct node* next;
} Node;
// 定义邻接表结构体
typedef struct graph {
Node* adj_list[MAX_SIZE];
} Graph;
// 初始化邻接表
void init(Graph* g) {
for (int i = 0; i < MAX_SIZE; i++) {
g->adj_list[i] = NULL;
}
}
// 添加边
void add_edge(Graph* g, int u, int v) {
Node* node = (Node*) malloc(sizeof(Node));
node->index = v;
node->next = g->adj_list[u];
g->adj_list[u] = node;
}
// 深度优先遍历核心函数
void dfs_helper(Graph* g, int u, int* visited) {
visited[u] = 1;
printf("%d ", u);
for (Node* node = g->adj_list[u]; node != NULL; node = node->next) {
int v = node->index;
if (!visited[v]) {
dfs_helper(g, v, visited);
}
}
}
// 深度优先遍历
void dfs(Graph* g, int start) {
int visited[MAX_SIZE] = {0};
dfs_helper(g, start, visited);
printf("\n");
}
// 广度优先遍历
void bfs(Graph* g, int start) {
int visited[MAX_SIZE] = {0};
int queue[MAX_SIZE];
int front = 0, rear = 0;
visited[start] = 1;
queue[rear++] = start;
while (front != rear) {
int u = queue[front++];
printf("%d ", u);
for (Node* node = g->adj_list[u]; node != NULL; node = node->next) {
int v = node->index;
if (!visited[v]) {
visited[v] = 1;
queue[rear++] = v;
}
}
}
printf("\n");
}
int main() {
Graph g;
init(&g);
add_edge(&g, 0, 1);
add_edge(&g, 0, 2);
add_edge(&g, 0, 3);
add_edge(&g, 1, 4);
add_edge(&g, 1, 5);
add_edge(&g, 2, 5);
add_edge(&g, 2, 6);
add_edge(&g, 3, 7);
add_edge(&g, 6, 8);
add_edge(&g, 6, 9);
add_edge(&g, 7, 10);
int start;
printf("请输入要遍历的起始结点: ");
scanf("%d", &start);
printf("深度优先遍历序列: ");
dfs(&g, start);
printf("广度优先遍历序列: ");
bfs(&g, start);
return 0;
}
```
运行结果:
```
请输入要遍历的起始结点: 0
深度优先遍历序列: 0 1 4 5 2 6 8 9 3 7 10
广度优先遍历序列: 0 1 2 3 4 5 6 7 8 9 10
```
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.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)
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)