深度优先搜索遍历c语言
时间: 2023-12-11 22:31:50 浏览: 42
以下是C语言实现深度优先搜索遍历的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20 // 最大顶点数
typedef struct ArcNode { // 边表结点
int adjvex; // 邻接点在数组中的位置下标
struct ArcNode *nextarc; // 指向下一个邻接点的指针
} ArcNode;
typedef struct VNode { // 顶点表结点
char data; // 顶点信息
ArcNode *firstarc; // 指向第一个邻接点的指针
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct { // 图
AdjList vertices; // 顶点数组
int vexnum, arcnum; // 顶点数和边数
} ALGraph;
void CreateGraph(ALGraph *G) { // 创建图
printf("请输入顶点数和边数:");
scanf("%d%d", &G->vexnum, &G->arcnum);
getchar(); // 吸收回车符
printf("请输入各个顶点的信息:\n");
for (int i = 0; i < G->vexnum; i++) {
printf("第%d个顶点:", i + 1);
scanf("%c", &G->vertices[i].data);
G->vertices[i].firstarc = NULL;
getchar(); // 吸收回车符
}
printf("请输入各个边的信息:\n");
for (int k = 0; k < G->arcnum; k++) {
printf("第%d条边:", k + 1);
char v1, v2;
scanf("%c%c", &v1, &v2);
getchar(); // 吸收回车符
int i, j;
for (i = 0; i < G->vexnum; i++) {
if (G->vertices[i].data == v1) {
break;
}
}
for (j = 0; j < G->vexnum; j++) {
if (G->vertices[j].data == v2) {
break;
}
}
ArcNode *p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = j;
p->nextarc = G->vertices[i].firstarc;
G->vertices[i].firstarc = p;
}
}
int visited[MAX_VERTEX_NUM]; // 访问标记数组
void DFS(ALGraph G, int v) { // 深度优先搜索遍历
visited[v] = 1; // 标记为已访问
printf("%c ", G.vertices[v].data); // 输出顶点信息
ArcNode *p = G.vertices[v].firstarc;
while (p != NULL) {
int w = p->adjvex;
if (!visited[w]) { // 如果未访问过,则递归访问
DFS(G, w);
}
p = p->nextarc;
}
}
int main() {
ALGraph G;
CreateGraph(&G);
printf("深度优先搜索遍历结果为:");
for (int i = 0; i < G.vexnum; i++) {
visited[i] = 0; // 初始化访问标记数组
}
for (int i = 0; i < G.vexnum; i++) {
if (!visited[i]) { // 如果未访问过,则从该顶点开始遍历
DFS(G, i);
}
}
printf("\n");
return 0;
}
```
相关推荐
![](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)