用C语言以邻接矩阵或邻接表定义无向图,其中每个元素的数据类型为int。实现图的深度优先或者广度优先遍历,打印所有的节点。并标上注释
时间: 2024-02-11 21:08:38 浏览: 77
好的,以下是代码实现:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 100 // 图中最大节点数
// 定义邻接矩阵结构体
typedef struct {
int matrix[MAX_VERTICES][MAX_VERTICES]; // 邻接矩阵
int num_vertices; // 图中节点数
} Graph;
// 初始化邻接矩阵,将所有元素设为0
void init_graph(Graph* g) {
int i, j;
for (i = 0; i < MAX_VERTICES; i++) {
for (j = 0; j < MAX_VERTICES; j++) {
g->matrix[i][j] = 0;
}
}
g->num_vertices = 0;
}
// 添加边
void add_edge(Graph* g, int start, int end) {
g->matrix[start][end] = 1;
g->matrix[end][start] = 1; // 无向图需要反向也加上
}
// 深度优先遍历
void dfs(Graph* g, bool visited[], int v) {
visited[v] = true; // 标记当前节点已访问
printf("%d ", v); // 打印节点
int i;
for (i = 0; i < g->num_vertices; i++) {
if (g->matrix[v][i] == 1 && visited[i] == false) { // 如果与当前节点相邻且未访问
dfs(g, visited, i); // 递归遍历相邻节点
}
}
}
// 广度优先遍历
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++]; // 取出队首节点
int i;
for (i = 0; i < g->num_vertices; i++) {
if (g->matrix[cur][i] == 1 && visited[i] == false) { // 如果与当前节点相邻且未访问
visited[i] = true; // 标记为已访问
printf("%d ", i); // 打印节点
queue[rear++] = i; // 将节点加入队列
}
}
}
}
int main() {
Graph g;
init_graph(&g); // 初始化邻接矩阵
g.num_vertices = 6; // 设置节点数
// 添加边
add_edge(&g, 0, 1);
add_edge(&g, 0, 2);
add_edge(&g, 1, 2);
add_edge(&g, 1, 3);
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 }; // 初始化所有节点未访问
printf("DFS: ");
dfs(&g, visited, 0); // 从节点0开始深度优先遍历
printf("\n");
for (int i = 0; i < g.num_vertices; i++) {
visited[i] = false; // 重置所有节点未访问
}
printf("BFS: ");
bfs(&g, visited, 0); // 从节点0开始广度优先遍历
printf("\n");
return 0;
}
```
代码中先定义了一个邻接矩阵结构体 `Graph`,包含一个二维数组 `matrix` 用于存储邻接矩阵,一个整数 `num_vertices` 表示节点数。`init_graph()` 函数用于将邻接矩阵所有元素设为0,并将节点数设为0。`add_edge()` 函数用于添加边,将邻接矩阵中对应元素设为1即可,由于是无向图,所以需要反向也加上。`dfs()` 函数为深度优先遍历,使用递归实现,先将当前节点标记为已访问,然后打印节点,再递归遍历当前节点的所有相邻节点。`bfs()` 函数为广度优先遍历,使用队列实现,先将当前节点标记为已访问,然后打印节点,再将当前节点加入队列,依次将队列中的节点取出并遍历其所有未访问的相邻节点。
在 `main()` 函数中,先初始化邻接矩阵,然后添加边,最后调用 `dfs()` 和 `bfs()` 函数进行遍历。
阅读全文