bfs和dfs c原因实现
时间: 2023-08-31 20:05:45 浏览: 41
BFS和DFS是两种基本的图遍历算法,它们都可以用C语言来实现。
BFS(广度优先搜索)是一种逐层扫描图的算法,它从起点开始,遍历所有与该点相邻的点,然后再遍历与这些点相邻的点,直到遍历所有的点。BFS可以使用队列来实现,具体实现步骤如下:
1. 将起点加入队列中。
2. 每次从队列中取出一个节点,并将该节点的未遍历过的相邻节点加入队列中。
3. 标记已经遍历过的节点,避免重复遍历。
4. 重复步骤2,直到队列为空。
DFS(深度优先搜索)是一种递归或者栈的实现方式,它从起点开始,沿着一个路径一直走到底,然后回退到上一个节点,再沿着其他的路径继续遍历,直到遍历完所有的节点。DFS可以使用递归或栈来实现,具体实现步骤如下:
1. 对于当前节点,标记为已经遍历过。
2. 遍历当前节点的未遍历过的相邻节点。
3. 重复步骤1和2,直到遍历完所有节点。
以下是BFS和DFS的C语言实现示例:
BFS:
```
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct node {
int vertex;
struct node* next;
} Node;
typedef struct graph {
Node* vertices[MAX_SIZE];
int visited[MAX_SIZE];
int n;
} Graph;
void init_graph(Graph* g) {
int i;
g->n = 0;
for (i = 0; i < MAX_SIZE; i++) {
g->visited[i] = 0;
g->vertices[i] = NULL;
}
}
void add_edge(Graph* g, int u, int v) {
Node* node = (Node*)malloc(sizeof(Node));
node->vertex = v;
node->next = g->vertices[u];
g->vertices[u] = node;
}
void bfs(Graph* g, int start) {
int queue[MAX_SIZE], front = 0, rear = 0, u, v;
Node* node;
queue[rear++] = start;
g->visited[start] = 1;
while (front != rear) {
u = queue[front++];
printf("%d ", u);
for (node = g->vertices[u]; node != NULL; node = node->next) {
v = node->vertex;
if (!g->visited[v]) {
g->visited[v] = 1;
queue[rear++] = v;
}
}
}
}
int main() {
Graph g;
int i, j, k;
init_graph(&g);
g.n = 6;
add_edge(&g, 0, 1);
add_edge(&g, 0, 2);
add_edge(&g, 1, 2);
add_edge(&g, 2, 0);
add_edge(&g, 2, 3);
add_edge(&g, 3, 3);
bfs(&g, 2);
return 0;
}
```
DFS:
```
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct node {
int vertex;
struct node* next;
} Node;
typedef struct graph {
Node* vertices[MAX_SIZE];
int visited[MAX_SIZE];
int n;
} Graph;
void init_graph(Graph* g) {
int i;
g->n = 0;
for (i = 0; i < MAX_SIZE; i++) {
g->visited[i] = 0;
g->vertices[i] = NULL;
}
}
void add_edge(Graph* g, int u, int v) {
Node* node = (Node*)malloc(sizeof(Node));
node->vertex = v;
node->next = g->vertices[u];
g->vertices[u] = node;
}
void dfs(Graph* g, int u) {
Node* node = g->vertices[u];
g->visited[u] = 1;
printf("%d ", u);
while (node != NULL) {
if (!g->visited[node->vertex]) {
dfs(g, node->vertex);
}
node = node->next;
}
}
int main() {
Graph g;
int i, j, k;
init_graph(&g);
g.n = 6;
add_edge(&g, 0, 1);
add_edge(&g, 0, 2);
add_edge(&g, 1, 2);
add_edge(&g, 2, 0);
add_edge(&g, 2, 3);
add_edge(&g, 3, 3);
dfs(&g, 2);
return 0;
}
```