用c语言实现用邻接矩阵实现图存储,并实现图的深度优先遍历
时间: 2024-06-18 10:05:20 浏览: 21
邻接矩阵是一种常见的图的存储方式,可以使用二维数组来表示。对于n个顶点的图,邻接矩阵是一个n*n的矩阵,其中第i行第j列的元素表示顶点i和顶点j之间是否有边,通常用0或1表示。
以下是使用邻接矩阵实现图的深度优先遍历的C语言代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20 // 最大顶点数
typedef char VertexType; // 顶点类型为字符型
typedef struct {
int edges[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
int n, e; // 顶点数和边数
VertexType vexs[MAX_VERTEX_NUM]; // 存放顶点信息
} MGraph;
void CreateGraph(MGraph *G) {
int i, j, k;
printf("请输入顶点数和边数:\n");
scanf("%d %d", &G->n, &G->e);
printf("请输入%d个顶点:\n", G->n);
for (i = 0; i < G->n; i++) {
getchar();
scanf("%c", &G->vexs[i]);
}
for (i = 0; i < G->n; i++) {
for (j = 0; j < G->n; j++) {
G->edges[i][j] = 0; // 初始化邻接矩阵
}
}
printf("请输入%d条边(每条边输入两个顶点的序号):\n", G->e);
for (k = 0; k < G->e; k++) {
scanf("%d %d", &i, &j);
G->edges[i][j] = G->edges[j][i] = 1; // 设置边的权值为1
}
}
int visited[MAX_VERTEX_NUM]; // 记录每个顶点是否被访问过
void DFS(MGraph G, int v) { // 深度优先遍历
int w;
visited[v] = 1; // 标记当前顶点已访问
printf("%c ", G.vexs[v]); // 输出当前顶点
for (w = 0; w < G.n; w++) {
if (G.edges[v][w] && !visited[w]) { // 如果存在边且未被访问
DFS(G, w); // 递归访问相邻顶点
}
}
}
int main() {
MGraph G;
CreateGraph(&G);
printf("深度优先遍历结果:\n");
int i;
for (i = 0; i < G.n; i++) {
visited[i] = 0; // 初始化visited数组
}
for (i = 0; i < G.n; i++) {
if (!visited[i]) { // 如果当前顶点未被访问
DFS(G, i); // 进行深度优先遍历
}
}
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)
![](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)