帮我用c语言写一个图的深度优先遍历
时间: 2023-11-17 10:08:10 浏览: 121
好的,以下是一个基于邻接表的图的深度优先遍历的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; // 顶点个数
int arcnum; // 边个数
} ALGraph;
// 初始化邻接表
void InitGraph(ALGraph* G) {
int i;
G->vexnum = G->arcnum = 0;
for (i = 0; i < MAX_VERTEX_NUM; i++) {
G->vertices[i].data = 0;
G->vertices[i].firstarc = NULL;
}
}
// 向邻接表中插入一条边
void InsertArc(ALGraph* G, int v, int w) {
ArcNode* p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = w;
p->nextarc = G->vertices[v].firstarc;
G->vertices[v].firstarc = p;
}
// 深度优先遍历
void DFS(ALGraph* G, int v, int* visited) {
ArcNode* p;
visited[v] = 1;
printf("%c ", G->vertices[v].data);
for (p = G->vertices[v].firstarc; p; p = p->nextarc) {
if (!visited[p->adjvex]) {
DFS(G, p->adjvex, visited);
}
}
}
// 图的深度优先遍历
void DFSTraverse(ALGraph* G) {
int i;
int visited[MAX_VERTEX_NUM] = {0};
for (i = 0; i < G->vexnum; i++) {
if (!visited[i]) {
DFS(G, i, visited);
}
}
}
int main() {
ALGraph G;
int i, j;
char c;
InitGraph(&G);
printf("请输入顶点个数和边个数:");
scanf("%d %d", &G.vexnum, &G.arcnum);
getchar(); // 去掉换行符
printf("请输入顶点信息:");
for (i = 0; i < G.vexnum; i++) {
scanf("%c", &G.vertices[i].data);
getchar(); // 去掉换行符
}
printf("请输入每条边所连接的两个顶点的编号:\n");
for (i = 0; i < G.arcnum; i++) {
scanf("%d %d", &j, &j);
InsertArc(&G, i, j);
InsertArc(&G, j, i);
}
printf("深度优先遍历结果为:");
DFSTraverse(&G);
printf("\n");
return 0;
}
```
以上代码实现了基于邻接表的图的深度优先遍历。在代码中,`ALGraph`是邻接表存储结构,`InitGraph()`函数用于初始化邻接表,`InsertArc()`函数用于向邻接表中插入一条边,`DFS()`函数用于深度优先遍历,`DFSTraverse()`函数则是图的深度优先遍历函数,`main()`函数用于读入图的信息并调用深度优先遍历函数。