利用C建立图的邻接表,并实现图的深度优先遍历
时间: 2023-12-18 17:30:23 浏览: 25
以下是利用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 {
int data;
ArcNode *firstarc;
} VNode, AdjList[MAX_VERTEX_NUM];
typedef struct {
AdjList vertices;
int vexnum, arcnum;
} ALGraph;
ALGraph *initALGraph() {
ALGraph *graph = (ALGraph *)malloc(sizeof(ALGraph));
printf("请输入图的顶点数和边数:");
scanf("%d %d", &(graph->vexnum), &(graph->arcnum));
printf("请输入图的顶点信息:");
for (int i = 0; i < graph->vexnum; i++) {
scanf("%d", &(graph->vertices[i].data));
graph->vertices[i].firstarc = NULL;
}
printf("请输入图的边信息:");
for (int i = 0; i < graph->arcnum; i++) {
int v1, v2;
scanf("%d %d", &v1, &v2);
ArcNode *arc1 = (ArcNode *)malloc(sizeof(ArcNode));
arc1->adjvex = v2;
arc1->next = graph->vertices[v1].firstarc;
graph->vertices[v1].firstarc = arc1;
ArcNode *arc2 = (ArcNode *)malloc(sizeof(ArcNode));
arc2->adjvex = v1;
arc2->next = graph->vertices[v2].firstarc;
graph->vertices[v2].firstarc = arc2;
}
return graph;
}
void DFS(ALGraph *graph, int v, int *visited) {
visited[v] = 1;
printf("%d ", graph->vertices[v].data);
ArcNode *arc = graph->vertices[v].firstarc;
while (arc != NULL) {
if (!visited[arc->adjvex]) {
DFS(graph, arc->adjvex, visited);
}
arc = arc->next;
}
}
void DFSTraverseM(ALGraph *graph) {
int visited[MAX_VERTEX_NUM] = {0};
printf("深度优先遍历结果:");
for (int i = 0; i < graph->vexnum; i++) {
if (!visited[i]) {
DFS(graph, i, visited);
}
}
printf("\n");
}
int main() {
ALGraph *graph = initALGraph();
DFSTraverseM(graph);
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)