输入无向图的顶点数、边数及各条边的顶点对,建立用邻接表表示的无向图。 (2)对图进行深度优先搜索和广度优先搜索遍历,并分别输出其遍历序列。C语言
时间: 2024-01-21 14:16:14 浏览: 86
以下是使用邻接表表示无向图并进行深度优先搜索和广度优先搜索的C语言代码:
```
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
typedef struct ArcNode {
int adjvex; // 邻接点在顶点数组中的下标
struct ArcNode *nextarc; // 指向下一条边的指针
} ArcNode;
typedef struct VNode {
int data; // 顶点数据
ArcNode *firstarc; // 指向第一条边的指针
} VNode;
typedef struct {
VNode vertices[MAX_VERTEX_NUM]; // 顶点数组
int vexnum, arcnum; // 顶点数和边数
} Graph;
void CreateGraph(Graph *G) {
int i, j, k;
ArcNode *p;
printf("请输入顶点数和边数:\n");
scanf("%d%d", &G->vexnum, &G->arcnum);
printf("请输入顶点数据(整数):\n");
for (i = 0; i < G->vexnum; i++) {
scanf("%d", &G->vertices[i].data);
G->vertices[i].firstarc = NULL;
}
printf("请输入边的顶点对(下标从0开始):\n");
for (k = 0; k < G->arcnum; k++) {
scanf("%d%d", &i, &j);
// 添加边i->j
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = j;
p->nextarc = G->vertices[i].firstarc;
G->vertices[i].firstarc = p;
// 添加边j->i
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = i;
p->nextarc = G->vertices[j].firstarc;
G->vertices[j].firstarc = p;
}
}
void DFS(Graph *G, int v, int visited[]) {
ArcNode *p;
visited[v] = 1;
printf("%d ", G->vertices[v].data);
p = G->vertices[v].firstarc;
while (p) {
if (!visited[p->adjvex]) {
DFS(G, p->adjvex, visited);
}
p = p->nextarc;
}
}
void DFSTraverse(Graph *G) {
int i;
int visited[MAX_VERTEX_NUM];
printf("深度优先搜索遍历序列:\n");
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");
}
void BFSTraverse(Graph *G) {
int i, j, k;
int visited[MAX_VERTEX_NUM];
int queue[MAX_VERTEX_NUM];
int front = 0, rear = 0;
ArcNode *p;
printf("广度优先搜索遍历序列:\n");
for (i = 0; i < G->vexnum; i++) {
visited[i] = 0;
}
for (i = 0; i < G->vexnum; i++) {
if (!visited[i]) {
visited[i] = 1;
printf("%d ", G->vertices[i].data);
queue[rear++] = i;
while (front != rear) {
j = queue[front++];
p = G->vertices[j].firstarc;
while (p) {
k = p->adjvex;
if (!visited[k]) {
visited[k] = 1;
printf("%d ", G->vertices[k].data);
queue[rear++] = k;
}
p = p->nextarc;
}
}
}
}
printf("\n");
}
int main() {
Graph G;
CreateGraph(&G);
DFSTraverse(&G);
BFSTraverse(&G);
return 0;
}
```
该程序使用邻接表表示无向图,并且每个顶点的邻接点按照输入的顺序存储。在深度优先搜索和广度优先搜索遍历图时,使用了递归和队列两种方式实现。
阅读全文