C语言通过输入无向图的顶点数、边数及各条边的顶点对,建立用邻接表表. 示的无向图,对图进行深度优先搜索和广度优先搜索遍历,并分别输出其遍历序列。
时间: 2024-03-16 20:44:22 浏览: 66
好的,这是一个关于图的算法问题,我会尽力回答你的。
首先,我们需要了解图的邻接表表示法。邻接表是一种图的表示方法,它把每个顶点和与之相邻的顶点列表存储起来,以便于遍历和操作。对于无向图,每条边都是双向的,因此在邻接表中,每个顶点的相邻顶点列表中都要包含与之相连的所有顶点。
接下来,我们需要了解深度优先搜索(DFS)和广度优先搜索(BFS)这两种图的遍历算法。DFS 是一种沿着图的深度遍历的算法,它从某个顶点开始,递归地访问其相邻顶点,直到所有可达顶点都被访问。BFS 是一种按层次遍历图的算法,它从某个顶点开始,先访问其所有相邻顶点,然后按照它们与起点的距离递增的顺序依次访问其他顶点。
下面是 C 语言实现建立无向图的邻接表和 DFS、BFS 遍历的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
// 邻接表存储结构
typedef struct ArcNode {
int adjvex; // 该弧所指向的顶点的位置
struct ArcNode *next; // 指向下一条弧的指针
} ArcNode;
typedef struct VNode {
int data; // 顶点信息
ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices; // 邻接表
int vexnum, arcnum; // 顶点数和边数
} ALGraph;
// 初始化邻接表
void InitGraph(ALGraph *G) {
int i;
for (i = 0; i < G->vexnum; i++) {
G->vertices[i].data = i + 1;
G->vertices[i].firstarc = NULL;
}
}
// 增加一条边
void AddEdge(ALGraph *G, int v, int w) {
ArcNode *p;
// 添加弧<v, w>
p = (ArcNode *) malloc(sizeof(ArcNode));
p->adjvex = w - 1;
p->next = G->vertices[v - 1].firstarc;
G->vertices[v - 1].firstarc = p;
// 添加弧<w, v>
p = (ArcNode *) malloc(sizeof(ArcNode));
p->adjvex = v - 1;
p->next = G->vertices[w - 1].firstarc;
G->vertices[w - 1].firstarc = p;
}
// 深度优先搜索
void DFS(ALGraph *G, int v, int visited[]) {
visited[v] = 1;
printf("%d ", G->vertices[v].data);
ArcNode *p = G->vertices[v].firstarc;
while (p) {
if (!visited[p->adjvex]) {
DFS(G, p->adjvex, visited);
}
p = p->next;
}
}
// 广度优先搜索
void BFS(ALGraph *G, int v, int visited[]) {
int queue[MAX_VERTEX_NUM], front = 0, rear = 0;
visited[v] = 1;
printf("%d ", G->vertices[v].data);
queue[rear++] = v;
while (front < rear) {
int k = queue[front++];
ArcNode *p = G->vertices[k].firstarc;
while (p) {
if (!visited[p->adjvex]) {
visited[p->adjvex] = 1;
printf("%d ", G->vertices[p->adjvex].data);
queue[rear++] = p->adjvex;
}
p = p->next;
}
}
}
int main() {
int n, m, i, v, w;
ALGraph G;
printf("请输入顶点数和边数:");
scanf("%d%d", &n, &m);
G.vexnum = n;
G.arcnum = m;
InitGraph(&G);
printf("请输入各条边的顶点对:\n");
for (i = 0; i < m; i++) {
scanf("%d%d", &v, &w);
AddEdge(&G, v, w);
}
int visited[MAX_VERTEX_NUM] = {0};
printf("深度优先搜索遍历序列:");
for (i = 0; i < n; i++) {
if (!visited[i]) {
DFS(&G, i, visited);
}
}
printf("\n");
for (i = 0; i < n; i++) {
visited[i] = 0;
}
printf("广度优先搜索遍历序列:");
for (i = 0; i < n; i++) {
if (!visited[i]) {
BFS(&G, i, visited);
}
}
printf("\n");
return 0;
}
```
以上代码中,先定义了图的邻接表存储结构 `ALGraph`,包括顶点信息和指向第一条依附该顶点的弧的指针。然后实现了初始化邻接表、增加一条边、深度优先搜索和广度优先搜索等基本操作。在主函数中,先输入顶点数和边数,然后输入各条边的顶点对,再对图进行深度优先搜索和广度优先搜索,并输出遍历序列。
希望我的回答能够帮助到你。如果还有问题,可以继续问我。
阅读全文