用c语言实现深度优先搜索和广度优先搜索
时间: 2023-10-23 17:14:17 浏览: 57
下面是使用C语言实现深度优先搜索和广度优先搜索的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
// 图的邻接表存储结构
typedef struct ArcNode {
int adjvex; // 该弧所指向的顶点的位置
struct ArcNode *next; // 指向下一条弧的指针
} ArcNode;
typedef struct VNode {
int data; // 顶点信息
ArcNode *first; // 指向第一条依附该顶点的弧的指针
} VNode;
typedef struct Graph {
VNode adjList[MAX_VERTEX_NUM]; // 邻接表
int vexNum, arcNum; // 图的顶点数和弧数
} Graph;
// 初始化图
void InitGraph(Graph *G, int vexNum) {
G->vexNum = vexNum;
G->arcNum = 0;
for (int i = 0; i < vexNum; i++) {
G->adjList[i].data = i;
G->adjList[i].first = NULL;
}
}
// 添加弧
void AddArc(Graph *G, int from, int to) {
ArcNode *arc = (ArcNode*)malloc(sizeof(ArcNode));
arc->adjvex = to;
arc->next = G->adjList[from].first;
G->adjList[from].first = arc;
G->arcNum++;
}
// 深度优先搜索
void DFS(Graph *G, int v, int visited[]) {
visited[v] = 1;
printf("%d ", v);
ArcNode *arc = G->adjList[v].first;
while (arc != NULL) {
int w = arc->adjvex;
if (visited[w] == 0) {
DFS(G, w, visited);
}
arc = arc->next;
}
}
// 广度优先搜索
void BFS(Graph *G, int v, int visited[]) {
int queue[MAX_VERTEX_NUM];
int front = 0, rear = 0;
visited[v] = 1;
printf("%d ", v);
queue[rear++] = v;
while (front < rear) {
int w = queue[front++];
ArcNode *arc = G->adjList[w].first;
while (arc != NULL) {
int u = arc->adjvex;
if (visited[u] == 0) {
visited[u] = 1;
printf("%d ", u);
queue[rear++] = u;
}
arc = arc->next;
}
}
}
int main() {
Graph G;
int vexNum = 5;
InitGraph(&G, vexNum);
// 添加弧
AddArc(&G, 0, 1);
AddArc(&G, 0, 2);
AddArc(&G, 1, 3);
AddArc(&G, 1, 4);
// 深度优先搜索
int visited[MAX_VERTEX_NUM] = {0};
printf("DFS: ");
DFS(&G, 0, visited);
printf("\n");
// 广度优先搜索
for (int i = 0; i < vexNum; i++) {
visited[i] = 0;
}
printf("BFS: ");
BFS(&G, 0, visited);
printf("\n");
return 0;
}
```
在这个示例代码中,我们使用邻接表来存储图,其中`VNode`表示顶点,`ArcNode`表示弧。`InitGraph`函数用于初始化图,`AddArc`函数用于添加弧。`DFS`函数和`BFS`函数分别表示深度优先搜索和广度优先搜索。在这个示例代码中,我们使用递归来实现深度优先搜索,使用队列来实现广度优先搜索。最后,我们通过调用`DFS`函数和`BFS`函数来进行搜索。