用C语言编写程序实现深度优先搜索和广度优先搜索算法
时间: 2023-06-19 10:05:56 浏览: 71
深度优先搜索和广度优先搜索是常用的图搜索算法,可以用来解决很多实际问题。以下是用C语言编写的深度优先搜索和广度优先搜索算法:
深度优先搜索:
```
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 100
// 定义邻接矩阵图结构体
typedef struct {
int matrix[MAX_VERTICES][MAX_VERTICES];
int num_vertices;
} Graph;
// 初始化图
void init_graph(Graph *g, int num_vertices) {
g->num_vertices = num_vertices;
for (int i = 0; i < num_vertices; i++) {
for (int j = 0; j < num_vertices; j++) {
g->matrix[i][j] = 0;
}
}
}
// 添加边
void add_edge(Graph *g, int v1, int v2) {
g->matrix[v1][v2] = 1;
g->matrix[v2][v1] = 1;
}
// 深度优先搜索
void dfs(Graph *g, bool visited[], int v) {
visited[v] = true;
printf("%d ", v);
for (int i = 0; i < g->num_vertices; i++) {
if (g->matrix[v][i] == 1 && !visited[i]) {
dfs(g, visited, i);
}
}
}
int main() {
Graph g;
init_graph(&g, 6);
add_edge(&g, 0, 1);
add_edge(&g, 0, 2);
add_edge(&g, 1, 3);
add_edge(&g, 1, 4);
add_edge(&g, 2, 4);
add_edge(&g, 3, 4);
add_edge(&g, 3, 5);
add_edge(&g, 4, 5);
bool visited[MAX_VERTICES] = { false };
dfs(&g, visited, 0);
printf("\n");
return 0;
}
```
广度优先搜索:
```
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 100
// 定义邻接矩阵图结构体
typedef struct {
int matrix[MAX_VERTICES][MAX_VERTICES];
int num_vertices;
} Graph;
// 初始化图
void init_graph(Graph *g, int num_vertices) {
g->num_vertices = num_vertices;
for (int i = 0; i < num_vertices; i++) {
for (int j = 0; j < num_vertices; j++) {
g->matrix[i][j] = 0;
}
}
}
// 添加边
void add_edge(Graph *g, int v1, int v2) {
g->matrix[v1][v2] = 1;
g->matrix[v2][v1] = 1;
}
// 广度优先搜索
void bfs(Graph *g, bool visited[], int v) {
int queue[MAX_VERTICES];
int front = 0, rear = 0;
visited[v] = true;
printf("%d ", v);
queue[rear++] = v;
while (front != rear) {
int cur = queue[front++];
for (int i = 0; i < g->num_vertices; i++) {
if (g->matrix[cur][i] == 1 && !visited[i]) {
visited[i] = true;
printf("%d ", i);
queue[rear++] = i;
}
}
}
}
int main() {
Graph g;
init_graph(&g, 6);
add_edge(&g, 0, 1);
add_edge(&g, 0, 2);
add_edge(&g, 1, 3);
add_edge(&g, 1, 4);
add_edge(&g, 2, 4);
add_edge(&g, 3, 4);
add_edge(&g, 3, 5);
add_edge(&g, 4, 5);
bool visited[MAX_VERTICES] = { false };
bfs(&g, visited, 0);
printf("\n");
return 0;
}
```