图的深度优先遍历c
时间: 2023-07-24 16:09:35 浏览: 47
以下是图的深度优先遍历的 C 语言代码实现:
```c
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTEX_NUM 100 // 定义顶点数的最大值
typedef int VertexType; // 顶点的数据类型
// 邻接表存储结构
typedef struct ArcNode {
int adjvex; // 该弧所指向的顶点的位置
struct ArcNode *nextarc; // 指向下一条弧的指针
} ArcNode;
// 邻接表的头结点
typedef struct VNode {
VertexType data; // 顶点信息
ArcNode *firstarc; // 指向第一条依附该顶点的弧的指针
} VNode, AdjList[MAX_VERTEX_NUM];
// 定义图的结构体
typedef struct {
AdjList vertices; // 邻接表
int vexnum, arcnum; // 图的顶点数和弧数
} ALGraph;
// 初始化邻接表
void InitGraph(ALGraph *G) {
G->vexnum = G->arcnum = 0;
for (int i = 0; i < MAX_VERTEX_NUM; i++) {
G->vertices[i].data = 0;
G->vertices[i].firstarc = NULL;
}
}
// 添加一条边
void AddArc(ALGraph *G, int u, int v) {
ArcNode *p = (ArcNode *) malloc(sizeof(ArcNode));
p->adjvex = v;
p->nextarc = G->vertices[u].firstarc;
G->vertices[u].firstarc = p;
G->arcnum++;
}
// 访问顶点
void Visit(VertexType v) {
printf("%d ", v);
}
// 深度优先遍历
void DFS(ALGraph *G, int v, bool *visited) {
Visit(G->vertices[v].data);
visited[v] = true;
for (ArcNode *p = G->vertices[v].firstarc; p; p = p->nextarc) {
int w = p->adjvex;
if (!visited[w]) {
DFS(G, w, visited);
}
}
}
// 对图进行深度优先遍历
void DFSTraverse(ALGraph *G) {
bool visited[MAX_VERTEX_NUM];
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, visited);
}
}
}
int main() {
ALGraph G;
InitGraph(&G);
G.vexnum = 5;
AddArc(&G, 0, 1);
AddArc(&G, 0, 2);
AddArc(&G, 1, 2);
AddArc(&G, 1, 3);
AddArc(&G, 2, 1);
AddArc(&G, 2, 3);
AddArc(&G, 3, 0);
AddArc(&G, 3, 4);
AddArc(&G, 4, 3);
DFSTraverse(&G);
return 0;
}
```
以上代码实现了一个邻接表存储结构的图,并对其进行了深度优先遍历。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)