c语言完成无向图的创建,用结构体类型描述图的存储结构,并用邻接矩阵表示创建的图和DFS(深度优先遍历)和BFS(广度优先遍历)
时间: 2023-06-13 12:03:10 浏览: 105
以下是基于邻接矩阵的无向图的创建、DFS和BFS的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAXV 100 // 最大顶点数
typedef struct {
int edges[MAXV][MAXV]; // 邻接矩阵
int n; // 顶点数
} Graph;
int visited[MAXV]; // 标记是否已访问
// 初始化图
void initGraph(Graph *g, int n) {
g->n = n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
g->edges[i][j] = 0; // 初始化为0
}
}
}
// 添加边
void addEdge(Graph *g, int u, int v) {
g->edges[u][v] = g->edges[v][u] = 1; // 无向图,需要两个方向都标记
}
// DFS遍历
void dfs(Graph *g, int v) {
printf("%d ", v);
visited[v] = 1;
for (int i = 0; i < g->n; i++) {
if (g->edges[v][i] && !visited[i]) {
dfs(g, i);
}
}
}
// BFS遍历
void bfs(Graph *g, int v) {
int queue[MAXV];
int front = 0, rear = 0;
queue[rear++] = v;
visited[v] = 1;
while (front < rear) {
int t = queue[front++];
printf("%d ", t);
for (int i = 0; i < g->n; i++) {
if (g->edges[t][i] && !visited[i]) {
queue[rear++] = i;
visited[i] = 1;
}
}
}
}
int main() {
Graph g;
initGraph(&g, 5);
addEdge(&g, 0, 1);
addEdge(&g, 1, 2);
addEdge(&g, 2, 3);
addEdge(&g, 3, 4);
addEdge(&g, 4, 0);
printf("DFS: ");
dfs(&g, 0);
printf("\n");
for (int i = 0; i < g.n; i++) {
visited[i] = 0; // 清空visited数组
}
printf("BFS: ");
bfs(&g, 0);
printf("\n");
return 0;
}
```
在这个示例代码中,我们使用了结构体类型`Graph`表示图的存储结构,其中包含了一个邻接矩阵`edges`和顶点数`n`。`initGraph`函数用于初始化图,`addEdge`函数用于添加边。`visited`数组用于标记是否已访问过某个顶点。`dfs`和`bfs`函数分别实现了DFS和BFS的遍历算法。
在主函数中,我们创建了一个5个顶点的图,并且添加了5条边,然后分别调用了`dfs`和`bfs`函数进行遍历。输出如下:
```
DFS: 0 1 2 3 4
BFS: 0 1 4 2 3
```
可以看到,DFS和BFS的遍历结果都是正确的。
阅读全文