用c语言写一个邻接表存储连通图,并分别用深度优先和广度优先遍历该连通图
时间: 2024-02-26 11:57:30 浏览: 19
好的,我可以帮你回答这个问题。以下是用C语言实现邻接表存储连通图,并分别用深度优先和广度优先遍历该连通图的代码:
```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;
G->vexnum = G->arcnum = 0;
for (i = 0; i < MAX_VERTEX_NUM; i++) {
G->vertices[i].data = 0;
G->vertices[i].firstarc = NULL;
}
}
// 添加边
void AddArc(ALGraph *G, int v, int w) {
ArcNode *p;
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = w;
p->next = G->vertices[v].firstarc;
G->vertices[v].firstarc = p;
G->arcnum++;
}
// 深度优先遍历
void DFS(ALGraph *G, int v, int visited[]) {
ArcNode *p;
visited[v] = 1;
printf("%d ", G->vertices[v].data);
for (p = G->vertices[v].firstarc; p; p = p->next) {
if (!visited[p->adjvex]) {
DFS(G, p->adjvex, visited);
}
}
}
// 广度优先遍历
void BFS(ALGraph *G, int v, int visited[]) {
int queue[MAX_VERTEX_NUM];
int front = 0, rear = 0;
ArcNode *p;
visited[v] = 1;
printf("%d ", G->vertices[v].data);
queue[rear++] = v;
while (front < rear) {
int k = queue[front++];
for (p = G->vertices[k].firstarc; p; p = p->next) {
if (!visited[p->adjvex]) {
visited[p->adjvex] = 1;
printf("%d ", G->vertices[p->adjvex].data);
queue[rear++] = p->adjvex;
}
}
}
}
int main() {
int i, v, w, visited[MAX_VERTEX_NUM];
ALGraph G;
InitGraph(&G);
printf("请输入连通图的顶点数和边数:\n");
scanf("%d%d", &G.vexnum, &G.arcnum);
printf("请输入连通图的顶点:\n");
for (i = 0; i < G.vexnum; i++) {
scanf("%d", &G.vertices[i].data);
}
printf("请输入连通图的边(以v w的方式输入):\n");
for (i = 0; i < G.arcnum; i++) {
scanf("%d%d", &v, &w);
AddArc(&G, v, w);
AddArc(&G, w, v); // 无向图需要添加反向边
}
printf("深度优先遍历结果:");
for (i = 0; i < G.vexnum; i++) {
visited[i] = 0;
}
for (i = 0; i < G.vexnum; i++) {
if (!visited[i]) {
DFS(&G, i, visited);
}
}
printf("\n广度优先遍历结果:");
for (i = 0; i < G.vexnum; i++) {
visited[i] = 0;
}
for (i = 0; i < G.vexnum; i++) {
if (!visited[i]) {
BFS(&G, i, visited);
}
}
printf("\n");
return 0;
}
```
以上代码实现了一个邻接表存储连通图的数据结构,并分别实现了深度优先遍历和广度优先遍历。其中,`InitGraph`函数用于初始化邻接表,`AddArc`函数用于添加边,`DFS`函数和`BFS`函数分别实现了深度优先遍历和广度优先遍历。在`main`函数中,我们先读入连通图的顶点数和边数,然后读入连通图的顶点和边,最后调用`DFS`函数和`BFS`函数进行遍历。