C语言 输入无向图连通图的顶点数、顶点信息、边数、顶点对序列及遍历的起始点序号,输出深度优先遍历序列
时间: 2023-08-24 15:07:28 浏览: 66
下面是一个使用邻接表表示无向图,并进行深度优先搜索遍历的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAXN 100
typedef struct Node {
int v; // 与当前结点相邻的结点编号
struct Node *next; // 指向下一个邻接点的指针
} Node;
Node *adj[MAXN]; // 邻接表
bool visited[MAXN]; // 标记结点是否被访问过
int n, m; // 结点数和边数
// 添加一条边到邻接表中
void add_edge(int u, int v) {
Node *p = (Node*)malloc(sizeof(Node));
p->v = v;
p->next = adj[u];
adj[u] = p;
}
// 深度优先搜索遍历
void dfs(int u) {
visited[u] = true;
printf("%d ", u);
for(Node *p=adj[u]; p!=NULL; p=p->next) {
int v = p->v;
if(!visited[v]) { // 如果u和v之间有边,且v未被访问过
dfs(v);
}
}
}
int main() {
scanf("%d", &n);
// 初始化邻接表
for(int i=0; i<n; i++) {
adj[i] = NULL;
}
// 读入边并建立邻接表
scanf("%d", &m);
for(int i=0; i<m; i++) {
int u, v;
scanf("%d %d", &u, &v);
add_edge(u, v);
add_edge(v, u);
}
// 深度优先搜索遍历
int start;
scanf("%d", &start); // 读入遍历的起始点序号
dfs(start);
return 0;
}
```
在这个示例中,我们首先读入结点数n,然后初始化邻接表。接着,根据读入的边信息来建立邻接表。注意,由于是无向图,所以我们需要将每条边的两个端点都加入到对方的邻接表中。最后,我们读入遍历的起始点序号,并从该点开始进行深度优先搜索遍历。在遍历过程中,我们使用一个visited数组来标记结点是否被访问过,并在每次访问结点u时将visited[u]设置为true。最后输出遍历序列即可。
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)