C语言编程实现如下功能: (1)输入无向图的顶点数、边数及各条边的顶点对,建立用邻接表表示的无向图。 (2)对图进行深度优先搜索和广度优先搜索遍历,并分别输出其遍历序列。
时间: 2024-02-11 22:03:45 浏览: 115
好的,我可以为您解答这个问题。
以下是C语言代码实现:
```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, AdjList[MAX_VERTEX_NUM];
typedef struct { // 图
AdjList vertices; // 顶点表
int vexnum, arcnum; // 顶点数和边数
} ALGraph;
typedef struct QueueNode { // 队列结点
int data;
struct QueueNode *next;
} QueueNode;
typedef struct { // 队列
QueueNode *front, *rear;
} Queue;
int visited[MAX_VERTEX_NUM]; // 访问标记数组
void CreateGraph(ALGraph *G) { // 建立无向图
int i, j, k;
ArcNode *p;
printf("请输入顶点数和边数:");
scanf("%d%d", &G->vexnum, &G->arcnum);
for (i = 0; i < G->vexnum; i++) { // 初始化邻接表
G->vertices[i].data = i;
G->vertices[i].firstarc = NULL;
}
printf("请输入每条边的顶点对:\n");
for (k = 0; k < G->arcnum; k++) { // 建立邻接表
scanf("%d%d", &i, &j);
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = j;
p->nextarc = G->vertices[i].firstarc;
G->vertices[i].firstarc = p;
p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = i;
p->nextarc = G->vertices[j].firstarc;
G->vertices[j].firstarc = p;
}
}
void DFS(ALGraph *G, int v) { // 深度优先搜索遍历
ArcNode *p;
visited[v] = 1;
printf("%d ", v);
p = G->vertices[v].firstarc;
while (p) {
if (!visited[p->adjvex])
DFS(G, p->adjvex);
p = p->nextarc;
}
}
void DFSTraverse(ALGraph *G) { // 深度优先搜索遍历图
int i;
for (i = 0; i < G->vexnum; i++)
visited[i] = 0;
for (i = 0; i < G->vexnum; i++)
if (!visited[i])
DFS(G, i);
}
void InitQueue(Queue *Q) { // 初始化队列
Q->front = Q->rear = NULL;
}
void EnQueue(Queue *Q, int data) { // 入队
QueueNode *p = (QueueNode *)malloc(sizeof(QueueNode));
p->data = data;
p->next = NULL;
if (Q->rear)
Q->rear->next = p;
Q->rear = p;
if (!Q->front)
Q->front = Q->rear;
}
int DeQueue(Queue *Q) { // 出队
int data;
QueueNode *p;
if (!Q->front)
return -1;
data = Q->front->data;
p = Q->front;
Q->front = Q->front->next;
free(p);
if (!Q->front)
Q->rear = NULL;
return data;
}
int QueueEmpty(Queue *Q) { // 判断队列是否为空
return Q->front == NULL;
}
void BFS(ALGraph *G, int v) { // 广度优先搜索遍历
ArcNode *p;
Queue Q;
InitQueue(&Q);
visited[v] = 1;
printf("%d ", v);
EnQueue(&Q, v);
while (!QueueEmpty(&Q)) {
v = DeQueue(&Q);
p = G->vertices[v].firstarc;
while (p) {
if (!visited[p->adjvex]) {
visited[p->adjvex] = 1;
printf("%d ", p->adjvex);
EnQueue(&Q, p->adjvex);
}
p = p->nextarc;
}
}
}
void BFSTraverse(ALGraph *G) { // 广度优先搜索遍历图
int i;
for (i = 0; i < G->vexnum; i++)
visited[i] = 0;
for (i = 0; i < G->vexnum; i++)
if (!visited[i])
BFS(G, i);
}
int main() {
ALGraph G;
CreateGraph(&G);
printf("深度优先搜索遍历序列:");
DFSTraverse(&G);
printf("\n广度优先搜索遍历序列:");
BFSTraverse(&G);
printf("\n");
return 0;
}
```
在上面的代码中,我们定义了邻接表的结构体,包括顶点结点和边结点,并使用邻接表表示无向图。然后,我们实现了深度优先搜索和广度优先搜索遍历,并分别输出其遍历序列。
在 `CreateGraph()` 函数中,我们先输入顶点数和边数,然后对每条边的顶点对建立邻接表。在 `DFS()` 函数中,我们使用递归实现深度优先搜索遍历。在 `DFSTraverse()` 函数中,我们遍历图中所有未访问过的顶点,并对每个未访问过的顶点调用 `DFS()` 函数。在 `BFS()` 函数中,我们使用队列实现广度优先搜索遍历。在 `BFSTraverse()` 函数中,我们遍历图中所有未访问过的顶点,并对每个未访问过的顶点调用 `BFS()` 函数。
希望能够帮到您!
阅读全文