C语言请基于邻接矩阵存储结构构建带权无向图,输出其深度遍历序列和广度遍历序列。
时间: 2024-02-06 20:09:28 浏览: 101
好的,以下是基于邻接矩阵存储结构的带权无向图的深度遍历和广度遍历的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20 // 顶点数的最大值
typedef struct {
int vertex[MAX_VERTEX_NUM]; // 存放顶点信息
int edge[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 存放边的权值
int vertex_num, edge_num; // 顶点数和边数
} Graph;
// 初始化图
void init_graph(Graph *g) {
g->vertex_num = g->edge_num = 0;
for (int i = 0; i < MAX_VERTEX_NUM; i++) {
g->vertex[i] = 0;
for (int j = 0; j < MAX_VERTEX_NUM; j++) {
g->edge[i][j] = 0;
}
}
}
// 添加顶点
void add_vertex(Graph *g, int v) {
g->vertex[g->vertex_num++] = v;
}
// 添加边
void add_edge(Graph *g, int u, int v, int w) {
g->edge[u][v] = g->edge[v][u] = w;
g->edge_num++;
}
// 深度优先遍历
void dfs(Graph *g, int v, int visited[]) {
visited[v] = 1;
printf("%d ", g->vertex[v]);
for (int i = 0; i < g->vertex_num; i++) {
if (g->edge[v][i] && !visited[i]) {
dfs(g, i, visited);
}
}
}
// 广度优先遍历
void bfs(Graph *g, int v, int visited[]) {
int queue[MAX_VERTEX_NUM], rear = 0, front = 0;
visited[v] = 1;
printf("%d ", g->vertex[v]);
queue[rear++] = v;
while (front != rear) {
int u = queue[front++];
for (int i = 0; i < g->vertex_num; i++) {
if (g->edge[u][i] && !visited[i]) {
visited[i] = 1;
printf("%d ", g->vertex[i]);
queue[rear++] = i;
}
}
}
}
int main() {
Graph g;
int visited[MAX_VERTEX_NUM] = {0};
init_graph(&g); // 初始化图
// 添加顶点和边
add_vertex(&g, 0);
add_vertex(&g, 1);
add_vertex(&g, 2);
add_vertex(&g, 3);
add_edge(&g, 0, 1, 10);
add_edge(&g, 0, 2, 5);
add_edge(&g, 1, 2, 3);
add_edge(&g, 1, 3, 1);
add_edge(&g, 2, 1, 2);
add_edge(&g, 2, 3, 9);
add_edge(&g, 3, 0, 7);
add_edge(&g, 3, 2, 4);
printf("深度优先遍历序列:");
dfs(&g, 0, visited);
printf("\n");
for (int i = 0; i < g.vertex_num; i++) {
visited[i] = 0;
}
printf("广度优先遍历序列:");
bfs(&g, 0, visited);
printf("\n");
return 0;
}
```
上述代码中,我们采用了邻接矩阵存储结构来表示带权无向图。具体实现过程如下:
1. 定义一个结构体`Graph`,其中包括一个数组`vertex`用于存放顶点信息,二维数组`edge`用于存放边的权值,以及两个整型变量`vertex_num`和`edge_num`分别表示顶点数和边数。
2. 定义初始化函数`init_graph()`,将`vertex_num`和`edge_num`初始化为0,将`vertex`数组和`edge`数组中的所有元素初始化为0。
3. 定义添加顶点函数`add_vertex()`,将顶点v添加到`vertex`数组中,顶点数加1。
4. 定义添加边函数`add_edge()`,将边(u,v)的权值w加入`edge`数组中,并将边数加1。由于是无向图,因此对称的边(v,u)也要加上。
5. 定义深度优先遍历函数`dfs()`,采用递归方式实现。从顶点v开始遍历,标记v为已访问,输出v的信息。然后遍历v的邻居,如果邻居未被访问,则递归访问邻居。
6. 定义广度优先遍历函数`bfs()`,采用队列方式实现。从顶点v开始遍历,标记v为已访问,输出v的信息,并将v入队。然后从队头取出一个顶点u,遍历u的邻居,如果邻居未被访问,则标记为已访问,输出邻居的信息,并将邻居入队。
7. 在`main()`函数中,先调用`init_graph()`函数进行图的初始化,然后添加顶点和边。最后分别调用`dfs()`和`bfs()`函数进行深度遍历和广度遍历,并输出遍历序列。
运行程序,输出结果如下:
```
深度优先遍历序列:0 1 2 3
广度优先遍历序列:0 1 2 3
```
可以看到,深度优先遍历和广度优先遍历得到的遍历序列分别为0 1 2 3和0 1 2 3,符合预期结果。
阅读全文