深度优先搜索c语言代码
时间: 2023-03-20 07:03:07 浏览: 123
迷宫问题c语言 深度优先搜索
5星 · 资源好评率100%
以下是深度优先搜索的C语言代码示例:
```c
#include <stdio.h>
#define MAX_VERTEX_NUM 20 // 顶点最大数量
#define TRUE 1
#define FALSE 0
typedef int Boolean;
typedef char VertexType; // 顶点数据类型
// 邻接矩阵存储图
typedef struct {
int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; // 邻接矩阵
VertexType vexs[MAX_VERTEX_NUM]; // 存储顶点信息
int vexnum, arcnum; // 记录图的顶点数和弧数
} MGraph;
Boolean visited[MAX_VERTEX_NUM]; // 标记顶点是否已访问
// 深度优先搜索
void DFS(MGraph G, int v) {
visited[v] = TRUE;
printf("%c ", G.vexs[v]); // 打印访问的顶点
for (int i = 0; i < G.vexnum; i++) {
if (G.arcs[v][i] == 1 && !visited[i]) {
DFS(G, i); // 递归访问与v相邻的未访问顶点i
}
}
}
int main() {
MGraph G;
printf("请输入顶点数和弧数:\n");
scanf("%d%d", &G.vexnum, &G.arcnum);
printf("请输入顶点信息:\n");
for (int i = 0; i < G.vexnum; i++) {
scanf(" %c", &G.vexs[i]);
}
printf("请输入弧的信息:\n");
for (int i = 0; i < G.arcnum; i++) {
int start, end;
scanf("%d%d", &start, &end);
G.arcs[start][end] = 1; // 存在一条从start到end的弧
}
printf("深度优先搜索遍历结果:\n");
for (int i = 0; i < G.vexnum; i++) {
visited[i] = FALSE;
}
for (int i = 0; i < G.vexnum; i++) {
if (!visited[i]) {
DFS(G, i);
}
}
printf("\n");
return 0;
}
```
以上是一个使用邻接矩阵存储图,并实现了深度优先搜索的C语言代码示例。
阅读全文