C语言通过输入无向图的顶点数、边数及各条边的顶点对,建立用邻接表表. 示的无向图,对图进行深度优先搜索和广度优先搜索遍历,并分别输出其遍历序列。
时间: 2024-03-16 15:45:25 浏览: 54
C语言 输入无向图连通图的顶点数、顶点信息、边数、顶点对序列及遍历的起始点序号,输出深度优先遍历序列
5星 · 资源好评率100%
好的,这是一个关于图的算法问题。那我先简要介绍一下邻接表的概念和存储方式。
邻接表是一种表示图的方式,它将每个顶点的邻接点存储在一个单链表中。具体来说,对于一个无向图,我们可以用一个数组存储所有顶点,数组的每个元素是一个链表,链表中存储该顶点的所有邻接点。这样,我们就可以用 O(V+E) 的时间复杂度存储一个无向图,其中 V 是顶点数,E 是边数。
接下来,我们可以按照题目要求,分别使用深度优先搜索和广度优先搜索算法来遍历这个无向图,并输出遍历序列。
以下是 C 语言代码实现。假设输入的无向图用邻接表表示,存储在一个名为 graph 的数组中,顶点数为 n,边数为 m。为了简化问题,我们假设顶点编号从 1 开始。
深度优先搜索代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXN 1000
// 邻接表存储方式
typedef struct node {
int v; // 邻接点编号
struct node *next; // 指向下一个邻接点的指针
} Node;
Node *graph[MAXN]; // 存储无向图的邻接表
int vis[MAXN]; // 标记数组,用于记录每个顶点是否被访问过
int n, m; // 顶点数和边数
// 向邻接表中加入一条边 (u, v)
void add_edge(int u, int v) {
Node *p = (Node*)malloc(sizeof(Node));
p->v = v;
p->next = graph[u];
graph[u] = p;
}
// 深度优先搜索
void dfs(int u) {
printf("%d ", u); // 访问顶点 u
vis[u] = 1; // 标记顶点 u 已被访问
for (Node *p = graph[u]; p != NULL; p = p->next) {
int v = p->v;
if (!vis[v]) {
dfs(v); // 递归访问顶点 v
}
}
}
int main() {
// 读入顶点数和边数
scanf("%d%d", &n, &m);
// 初始化邻接表
for (int i = 1; i <= n; i++) {
graph[i] = NULL;
}
// 读入每条边,并向邻接表中加入这条边
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
add_edge(u, v);
add_edge(v, u); // 无向图需要反向再加入一遍
}
// 从顶点 1 开始进行深度优先搜索
dfs(1);
printf("\n");
return 0;
}
```
广度优先搜索代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXN 1000
// 邻接表存储方式
typedef struct node {
int v; // 邻接点编号
struct node *next; // 指向下一个邻接点的指针
} Node;
Node *graph[MAXN]; // 存储无向图的邻接表
int vis[MAXN]; // 标记数组,用于记录每个顶点是否被访问过
int n, m; // 顶点数和边数
// 向邻接表中加入一条边 (u, v)
void add_edge(int u, int v) {
Node *p = (Node*)malloc(sizeof(Node));
p->v = v;
p->next = graph[u];
graph[u] = p;
}
// 广度优先搜索
void bfs(int s) {
int q[MAXN], front = 0, rear = 0;
q[rear++] = s; // 将起点加入队列中
vis[s] = 1; // 标记起点已被访问
while (front < rear) {
int u = q[front++]; // 取出队列首部的顶点 u
printf("%d ", u); // 访问顶点 u
for (Node *p = graph[u]; p != NULL; p = p->next) {
int v = p->v;
if (!vis[v]) {
q[rear++] = v; // 将未被访问的邻接点加入队列中
vis[v] = 1; // 标记顶点 v 已被访问
}
}
}
}
int main() {
// 读入顶点数和边数
scanf("%d%d", &n, &m);
// 初始化邻接表
for (int i = 1; i <= n; i++) {
graph[i] = NULL;
}
// 读入每条边,并向邻接表中加入这条边
for (int i = 1; i <= m; i++) {
int u, v;
scanf("%d%d", &u, &v);
add_edge(u, v);
add_edge(v, u); // 无向图需要反向再加入一遍
}
// 从顶点 1 开始进行广度优先搜索
bfs(1);
printf("\n");
return 0;
}
```
希望对你有所帮助!如果你还有其他问题,可以继续问我。
阅读全文