用C或C++语言编写一个完整代码,用结构体类型描述图的存储结构,编写具体函数实现对无向图或有向图进行DFS(深度优先遍历)和BFS(广度优先遍历)等基本操作,并给一个实例图输入和输出运行结果。
时间: 2024-05-01 08:20:41 浏览: 84
基于C++进行图的深度优先遍历(高级语言程序设计实验)
以下是使用C语言编写的一个基于邻接表存储的无向图的DFS和BFS遍历的完整代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20
// 定义邻接表中的边结构体
typedef struct ArcNode {
int adjvex; // 边指向的顶点编号
struct ArcNode *next; // 指向下一条边的指针
} ArcNode;
// 定义邻接表中的顶点结构体
typedef struct VertexNode {
char data; // 顶点的数据(可以是字符、数字等)
ArcNode *firstarc; // 指向第一条依附该顶点的边的指针
} VertexNode;
// 定义邻接表
typedef struct {
VertexNode adjlist[MAX_VERTEX_NUM]; // 顶点数组
int vexnum, arcnum; // 顶点数和边数
} ALGraph;
// 初始化邻接表
void InitGraph(ALGraph *G, int vexnum, int arcnum) {
G->vexnum = vexnum;
G->arcnum = arcnum;
for (int i = 0; i < vexnum; i++) {
printf("请输入第%d个顶点的数据:", i);
scanf(" %c", &G->adjlist[i].data);
G->adjlist[i].firstarc = NULL;
}
for (int j = 0; j < arcnum; j++) {
int v1, v2;
printf("请输入第%d条边依附的两个顶点的编号(用空格分隔):", j);
scanf("%d %d", &v1, &v2);
// 添加一条边
ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = v2;
p->next = G->adjlist[v1].firstarc;
G->adjlist[v1].firstarc = p;
// 无向图需要添加一条反向边
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = v1;
p->next = G->adjlist[v2].firstarc;
G->adjlist[v2].firstarc = p;
}
}
// DFS遍历邻接表
void DFS(ALGraph *G, int v, int visited[]) {
visited[v] = 1;
printf("%c ", G->adjlist[v].data);
ArcNode *p = G->adjlist[v].firstarc;
while (p != NULL) {
if (visited[p->adjvex] == 0) {
DFS(G, p->adjvex, visited);
}
p = p->next;
}
}
// BFS遍历邻接表
void BFS(ALGraph *G, int v, int visited[]) {
int queue[MAX_VERTEX_NUM], front = 0, rear = 0;
visited[v] = 1;
printf("%c ", G->adjlist[v].data);
queue[rear++] = v;
while (front != rear) {
int k = queue[front++];
ArcNode *p = G->adjlist[k].firstarc;
while (p != NULL) {
int w = p->adjvex;
if (visited[w] == 0) {
visited[w] = 1;
printf("%c ", G->adjlist[w].data);
queue[rear++] = w;
}
p = p->next;
}
}
}
// 主函数
int main() {
ALGraph G;
int vexnum, arcnum;
printf("请输入图的顶点数和边数(用空格分隔):");
scanf("%d %d", &vexnum, &arcnum);
InitGraph(&G, vexnum, arcnum);
int visited[MAX_VERTEX_NUM] = {0};
printf("DFS遍历结果:");
for (int i = 0; i < vexnum; i++) {
if (visited[i] == 0) {
DFS(&G, i, visited);
}
}
printf("\n");
for (int j = 0; j < vexnum; j++) {
visited[j] = 0;
}
printf("BFS遍历结果:");
for (int k = 0; k < vexnum; k++) {
if (visited[k] == 0) {
BFS(&G, k, visited);
}
}
printf("\n");
return 0;
}
```
以下是一个无向图的输入和输出运行结果的示例:
```
请输入图的顶点数和边数(用空格分隔):6 7
请输入第0个顶点的数据:A
请输入第1个顶点的数据:B
请输入第2个顶点的数据:C
请输入第3个顶点的数据:D
请输入第4个顶点的数据:E
请输入第5个顶点的数据:F
请输入第0条边依附的两个顶点的编号(用空格分隔):0 1
请输入第1条边依附的两个顶点的编号(用空格分隔):0 2
请输入第2条边依附的两个顶点的编号(用空格分隔):1 2
请输入第3条边依附的两个顶点的编号(用空格分隔):1 3
请输入第4条边依附的两个顶点的编号(用空格分隔):2 3
请输入第5条边依附的两个顶点的编号(用空格分隔):2 4
请输入第6条边依附的两个顶点的编号(用空格分隔):3 4
DFS遍历结果:A B C D E F
BFS遍历结果:A B C D E F
```
阅读全文