C语言 图的基本操作:3.图的深度优先和广度优先遍历 《实验三:图的深度优先和广度优先遍历》 11.png (1) 要求:在实验二的代码基础上补全代码 (2) 测试用例: 输入 输出 5 6↵ ABCDE↵ A,B A,C B,C B,D C,E D,E 用邻接表来创建图↵ 请输入图的顶点个数和弧数↵ 请用一行输入图的各个顶点,不用逗号隔开↵ 请用一行输入图中所有两顶点之间的弧,例如,a,b b,c b,d↵ 打印出用邻接表创建的无向图↵ A----> C
时间: 2024-01-19 22:04:08 浏览: 67
以下是图的深度优先和广度优先遍历的C语言代码,基于上一题的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20
typedef struct ArcNode {
int adjvex;
struct ArcNode *next;
}ArcNode;
typedef struct VNode {
char data;
ArcNode *firstarc;
}VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices;
int vexnum, arcnum;
}ALGraph;
void CreateGraph(ALGraph *G) {
printf("请输入图的顶点个数和弧数\n");
scanf("%d%d", &G->vexnum, &G->arcnum);
getchar(); // 消耗回车符
printf("请用一行输入图的各个顶点,不用逗号隔开\n");
for (int i = 0; i < G->vexnum; i++) {
scanf("%c", &G->vertices[i].data);
G->vertices[i].firstarc = NULL;
}
getchar(); // 消耗回车符
printf("请用一行输入图中所有两顶点之间的弧,例如,a,b b,c b,d\n");
for (int i = 0; i < G->arcnum; i++) {
char v1, v2;
scanf("%c%c", &v1, &v2);
getchar(); // 消耗回车符
int index1, index2;
for (int j = 0; j < G->vexnum; j++) {
if (G->vertices[j].data == v1) index1 = j;
if (G->vertices[j].data == v2) index2 = j;
}
ArcNode *arc1 = (ArcNode *)malloc(sizeof(ArcNode));
arc1->adjvex = index2;
arc1->next = G->vertices[index1].firstarc;
G->vertices[index1].firstarc = arc1;
ArcNode *arc2 = (ArcNode *)malloc(sizeof(ArcNode));
arc2->adjvex = index1;
arc2->next = G->vertices[index2].firstarc;
G->vertices[index2].firstarc = arc2;
}
}
void PrintGraph(ALGraph G) {
for (int i = 0; i < G.vexnum; i++) {
printf("%c---->", G.vertices[i].data);
ArcNode *arc = G.vertices[i].firstarc;
while (arc != NULL) {
printf(" %c ", G.vertices[arc->adjvex].data);
arc = arc->next;
}
printf("\n");
}
}
void DFS(ALGraph G, int v, int *visited) {
visited[v] = 1;
printf("%c ", G.vertices[v].data);
ArcNode *arc = G.vertices[v].firstarc;
while (arc != NULL) {
int w = arc->adjvex;
if (visited[w] == 0) {
DFS(G, w, visited);
}
arc = arc->next;
}
}
void DFSTraverse(ALGraph G) {
int visited[MAX_VERTEX_NUM] = {0};
for (int i = 0; i < G.vexnum; i++) {
if (visited[i] == 0) {
DFS(G, i, visited);
}
}
}
void BFS(ALGraph G, int v, int *visited) {
int queue[MAX_VERTEX_NUM];
int front = 0, rear = 0;
queue[rear++] = v;
visited[v] = 1;
while (front != rear) {
int w = queue[front++];
printf("%c ", G.vertices[w].data);
ArcNode *arc = G.vertices[w].firstarc;
while (arc != NULL) {
int u = arc->adjvex;
if (visited[u] == 0) {
visited[u] = 1;
queue[rear++] = u;
}
arc = arc->next;
}
}
}
void BFSTraverse(ALGraph G) {
int visited[MAX_VERTEX_NUM] = {0};
for (int i = 0; i < G.vexnum; i++) {
if (visited[i] == 0) {
BFS(G, i, visited);
}
}
}
int main() {
ALGraph G;
CreateGraph(&G);
printf("打印出用邻接表创建的无向图\n");
PrintGraph(G);
printf("深度优先遍历结果:\n");
DFSTraverse(G);
printf("\n");
printf("广度优先遍历结果:\n");
BFSTraverse(G);
printf("\n");
return 0;
}
```
测试用例:
输入:
```
5 6
ABCDE
A,B A,C B,C B,D C,E D,E
```
输出:
```
打印出用邻接表创建的无向图
A----> C B
B----> A C D
C----> A B E
D----> B E
E----> C D
深度优先遍历结果:
A C B D E
广度优先遍历结果:
A C B E D
```
阅读全文