图的dfs和bfs算法实现c
时间: 2024-09-23 22:02:19 浏览: 16
深度优先搜索 (Depth First Search, DFS) 和广度优先搜索 (Breadth First Search, BFS) 是图论中最基本的两个遍历算法。以下是它们在 C 语言中的简单实现:
**DFS(递归版)**:
```c
#include <stdio.h>
#define MAX 100
// 用于标记节点是否已访问
int visited[MAX];
void dfs(int graph[], int v, int n) {
printf("%d ", v);
visited[v] = 1;
for (int i = 0; i < n; i++) {
if (graph[v][i] && !visited[i]) {
dfs(graph, i, n);
}
}
}
void dfs_iterative(int graph[][], int n) {
// 初始化栈和标记数组
int stack[MAX], top = -1;
int* visited = malloc(n * sizeof(int));
memset(visited, 0, n);
stack[++top] = 0;
while (top >= 0) {
int current = stack[top--];
printf("%d ", current);
for (int j = 0; j < n; j++) {
if (!visited[j] && graph[current][j]) {
visited[j] = 1;
stack[++top] = j;
}
}
}
free(visited);
}
```
**BFS(队列版)**:
```c
#include <stdio.h>
#include <stdlib.h>
void bfs(int graph[][], int n, int start) {
// 初始化队列和访问数组
int queue[MAX], front = 0, rear = -1;
int* visited = malloc(n * sizeof(int));
memset(visited, 0, n);
queue[++rear] = start;
visited[start] = 1;
while (front <= rear) {
int current = queue[front++];
printf("%d ", current);
for (int i = 0; i < n; i++) {
if (graph[current][i] && !visited[i]) {
visited[i] = 1;
queue[++rear] = i;
}
}
}
free(visited);
}
```