c语言通过图的遍历输出邻接矩阵
时间: 2023-10-15 21:04:06 浏览: 96
以下是使用邻接矩阵存储图,并通过深度优先遍历输出邻接矩阵的C语言代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
typedef struct {
int vex[MAX_VERTEX_NUM]; // 顶点数组
int arc[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int vexnum, arcnum; // 顶点数和边数
} MGraph;
// 初始化邻接矩阵
void init(MGraph *G) {
int i, j;
G->vexnum = G->arcnum = 0;
for (i = 0; i < MAX_VERTEX_NUM; i++) {
G->vex[i] = 0;
for (j = 0; j < MAX_VERTEX_NUM; j++) {
G->arc[i][j] = 0;
}
}
}
// 添加边
void add_edge(MGraph *G, int u, int v) {
G->arc[u][v] = 1;
G->arc[v][u] = 1;
G->arcnum++;
}
// 深度优先遍历
void dfs(MGraph *G, int v, int *visited) {
int i;
visited[v] = 1;
printf("%d ", G->vex[v]);
for (i = 0; i < G->vexnum; i++) {
if (G->arc[v][i] && !visited[i]) {
dfs(G, i, visited);
}
}
}
// 输出邻接矩阵
void print_matrix(MGraph *G) {
int i, j;
printf("邻接矩阵:\n ");
for (i = 0; i < G->vexnum; i++) {
printf("%d ", G->vex[i]);
}
printf("\n");
for (i = 0; i < G->vexnum; i++) {
printf("%d: ", G->vex[i]);
for (j = 0; j < G->vexnum; j++) {
printf("%d ", G->arc[i][j]);
}
printf("\n");
}
}
int main() {
MGraph G;
int i, j, visited[MAX_VERTEX_NUM] = {0};
init(&G);
G.vexnum = 5;
for (i = 0; i < G.vexnum; i++) {
G.vex[i] = i + 1;
}
add_edge(&G, 0, 1);
add_edge(&G, 0, 4);
add_edge(&G, 1, 0);
add_edge(&G, 1, 2);
add_edge(&G, 1, 3);
add_edge(&G, 1, 4);
add_edge(&G, 2, 1);
add_edge(&G, 2, 3);
add_edge(&G, 3, 1);
add_edge(&G, 3, 2);
add_edge(&G, 4, 0);
add_edge(&G, 4, 1);
print_matrix(&G);
printf("深度优先遍历:");
dfs(&G, 0, visited);
printf("\n");
return 0;
}
```
在示例代码中,使用邻接矩阵存储图。首先使用 `init` 函数初始化邻接矩阵,然后使用 `add_edge` 函数添加边。`print_matrix` 函数输出邻接矩阵。`dfs` 函数是深度优先遍历,使用递归实现,遍历顶点时打印出顶点数据,并标记已访问过的顶点。在程序中,首先调用 `print_matrix` 函数输出邻接矩阵,然后调用 `dfs` 函数进行深度优先遍历。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)