用c语言编写图的深度优先遍历程序
时间: 2024-06-13 21:07:32 浏览: 10
以下是用C语言编写图的深度优先遍历程序的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
#define MAX_VERTEX_NUM 20
typedef struct ArcNode {
int adjvex;
struct ArcNode *next;
} ArcNode;
typedef struct VNode {
char data;
ArcNode *firstarc;
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices;
int vexnum, arcnum;
} ALGraph;
int visited[MAX_VERTEX_NUM];
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++) {
char v1, v2;
int i, j;
printf("第%d条边:", k + 1);
scanf("%c%c", &v1, &v2);
getchar();
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->next = G->vertices[i].firstarc;
G->vertices[i].firstarc = p;
}
}
void DFS(ALGraph G, int v) {
visited[v] = 1;
printf("%c ", G.vertices[v].data);
ArcNode *p = G.vertices[v].firstarc;
while (p) {
if (!visited[p->adjvex]) {
DFS(G, p->adjvex);
}
p = p->next;
}
}
void DFSTraverse(ALGraph G) {
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);
}
}
}
int main() {
ALGraph G;
CreateGraph(&G);
printf("深度优先遍历结果为:");
DFSTraverse(G);
printf("\n");
return 0;
}
```
相关推荐
![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_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)