使用C实现图的广度优先遍历和深度优先遍历,
时间: 2023-10-04 12:08:52 浏览: 37
广度优先遍历(BFS)和深度优先遍历(DFS)都是针对图的遍历算法,以下是使用C语言实现BFS和DFS的示例代码。
首先,定义图的结构体和队列结构体:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXVEX 100 // 最大顶点数
// 边表结点
typedef struct EdgeNode {
int adjvex; // 邻接点域,存储该顶点对应的下标
struct EdgeNode *next; // 指向下一个邻接点的指针
} EdgeNode;
// 顶点表结点
typedef struct VertexNode {
int data; // 顶点域,存储顶点信息
EdgeNode *firstedge; // 边表头指针
} VertexNode, AdjList[MAXVEX];
// 图结构体
typedef struct {
AdjList adjList; // 邻接表
int numVertexes; // 顶点数
int numEdges; // 边数
} Graph;
// 队列结构体
typedef struct {
int data[MAXVEX]; // 存储队列中的元素
int front; // 队头指针
int rear; // 队尾指针
} Queue;
```
接下来,实现BFS算法:
```c
// 初始化队列
void InitQueue(Queue *Q) {
Q->front = 0;
Q->rear = 0;
}
// 判断队列是否为空
int QueueEmpty(Queue *Q) {
if (Q->front == Q->rear)
return 1;
else
return 0;
}
// 进队列
int EnQueue(Queue *Q, int data) {
if ((Q->rear + 1) % MAXVEX == Q->front) // 队列已满
return 0;
Q->data[Q->rear] = data;
Q->rear = (Q->rear + 1) % MAXVEX;
return 1;
}
// 出队列
int DeQueue(Queue *Q, int *data) {
if (QueueEmpty(Q)) // 队列为空
return 0;
*data = Q->data[Q->front];
Q->front = (Q->front + 1) % MAXVEX;
return 1;
}
// 广度优先遍历算法
void BFSTraverse(Graph G) {
int i, j;
Queue Q;
EdgeNode *p;
InitQueue(&Q); // 初始化队列
int visited[MAXVEX] = {0}; // 访问标志数组,初始值为0
// 对每个顶点做循环
for (i = 0; i < G.numVertexes; i++) {
if (!visited[i]) { // 若是未访问过就处理
visited[i] = 1; // 设置当前顶点访问过
printf("%d ", G.adjList[i].data); // 打印顶点
EnQueue(&Q, i); // 将此顶点入队列
while (!QueueEmpty(&Q)) { // 若当前队列不为空
DeQueue(&Q, &i); // 将队中元素出队列,赋值给i
p = G.adjList[i].firstedge; // 找到当前顶点边表链表头指针
while (p) { // 扫描当前顶点的所有邻接点
j = p->adjvex;
if (!visited[j]) { // 若邻接点未访问过
visited[j] = 1; // 设置当前顶点访问过
printf("%d ", G.adjList[j].data); // 打印顶点
EnQueue(&Q, j); // 将此顶点入队列
}
p = p->next; // 指针指向下一个邻接点
}
}
}
}
printf("\n");
}
```
最后,实现DFS算法:
```c
// 深度优先遍历算法
void DFSTraverse(Graph G, int i, int visited[]) {
EdgeNode *p;
visited[i] = 1; // 设置当前顶点访问过
printf("%d ", G.adjList[i].data); // 打印顶点
p = G.adjList[i].firstedge; // 找到当前顶点边表链表头指针
while (p) { // 扫描当前顶点的所有邻接点
if (!visited[p->adjvex]) // 若邻接点未访问过
DFSTraverse(G, p->adjvex, visited); // 递归访问邻接点
p = p->next; // 指针指向下一个邻接点
}
}
// 深度优先遍历入口
void DFS(Graph G) {
int i;
int visited[MAXVEX] = {0}; // 访问标志数组,初始值为0
// 对每个顶点做循环
for (i = 0; i < G.numVertexes; i++) {
if (!visited[i]) // 若是未访问过就处理
DFSTraverse(G, i, visited); // 从第i个顶点开始深度优先遍历
}
printf("\n");
}
```
完整代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXVEX 100 // 最大顶点数
// 边表结点
typedef struct EdgeNode {
int adjvex; // 邻接点域,存储该顶点对应的下标
struct EdgeNode *next; // 指向下一个邻接点的指针
} EdgeNode;
// 顶点表结点
typedef struct VertexNode {
int data; // 顶点域,存储顶点信息
EdgeNode *firstedge; // 边表头指针
} VertexNode, AdjList[MAXVEX];
// 图结构体
typedef struct {
AdjList adjList; // 邻接表
int numVertexes; // 顶点数
int numEdges; // 边数
} Graph;
// 队列结构体
typedef struct {
int data[MAXVEX]; // 存储队列中的元素
int front; // 队头指针
int rear; // 队尾指针
} Queue;
// 初始化队列
void InitQueue(Queue *Q) {
Q->front = 0;
Q->rear = 0;
}
// 判断队列是否为空
int QueueEmpty(Queue *Q) {
if (Q->front == Q->rear)
return 1;
else
return 0;
}
// 进队列
int EnQueue(Queue *Q, int data) {
if ((Q->rear + 1) % MAXVEX == Q->front) // 队列已满
return 0;
Q->data[Q->rear] = data;
Q->rear = (Q->rear + 1) % MAXVEX;
return 1;
}
// 出队列
int DeQueue(Queue *Q, int *data) {
if (QueueEmpty(Q)) // 队列为空
return 0;
*data = Q->data[Q->front];
Q->front = (Q->front + 1) % MAXVEX;
return 1;
}
// 广度优先遍历算法
void BFSTraverse(Graph G) {
int i, j;
Queue Q;
EdgeNode *p;
InitQueue(&Q); // 初始化队列
int visited[MAXVEX] = {0}; // 访问标志数组,初始值为0
// 对每个顶点做循环
for (i = 0; i < G.numVertexes; i++) {
if (!visited[i]) { // 若是未访问过就处理
visited[i] = 1; // 设置当前顶点访问过
printf("%d ", G.adjList[i].data); // 打印顶点
EnQueue(&Q, i); // 将此顶点入队列
while (!QueueEmpty(&Q)) { // 若当前队列不为空
DeQueue(&Q, &i); // 将队中元素出队列,赋值给i
p = G.adjList[i].firstedge; // 找到当前顶点边表链表头指针
while (p) { // 扫描当前顶点的所有邻接点
j = p->adjvex;
if (!visited[j]) { // 若邻接点未访问过
visited[j] = 1; // 设置当前顶点访问过
printf("%d ", G.adjList[j].data); // 打印顶点
EnQueue(&Q, j); // 将此顶点入队列
}
p = p->next; // 指针指向下一个邻接点
}
}
}
}
printf("\n");
}
// 深度优先遍历算法
void DFSTraverse(Graph G, int i, int visited[]) {
EdgeNode *p;
visited[i] = 1; // 设置当前顶点访问过
printf("%d ", G.adjList[i].data); // 打印顶点
p = G.adjList[i].firstedge; // 找到当前顶点边表链表头指针
while (p) { // 扫描当前顶点的所有邻接点
if (!visited[p->adjvex]) // 若邻接点未访问过
DFSTraverse(G, p->adjvex, visited); // 递归访问邻接点
p = p->next; // 指针指向下一个邻接点
}
}
// 深度优先遍历入口
void DFS(Graph G) {
int i;
int visited[MAXVEX] = {0}; // 访问标志数组,初始值为0
// 对每个顶点做循环
for (i = 0; i < G.numVertexes; i++) {
if (!visited[i]) // 若是未访问过就处理
DFSTraverse(G, i, visited); // 从第i个顶点开始深度优先遍历
}
printf("\n");
}
int main() {
int i, j, k;
Graph G;
printf("请输入顶点数和边数:");
scanf("%d %d", &G.numVertexes, &G.numEdges);
// 输入顶点信息,建立顶点表
for (i = 0; i < G.numVertexes; i++) {
printf("请输入顶点%d的值:", i);
scanf("%d", &G.adjList[i].data);
G.adjList[i].firstedge = NULL; // 将边表置为空表
}
// 建立边表
for (k = 0; k < G.numEdges; k++) {
printf("请输入边(vi, vj)的下标:");
scanf("%d %d", &i, &j);
// 头插法建立边表
EdgeNode *e1 = (EdgeNode *)malloc(sizeof(EdgeNode));
e1->adjvex = j;
e1->next = G.adjList[i].firstedge;
G.adjList[i].firstedge = e1;
EdgeNode *e2 = (EdgeNode *)malloc(sizeof(EdgeNode));
e2->adjvex = i;
e2->next = G.adjList[j].firstedge;
G.adjList[j].firstedge = e2;
}
printf("广度优先遍历结果为:");
BFSTraverse(G);
printf("深度优先遍历结果为:");
DFS(G);
return 0;
}
```