实现图的遍历算法c代码
时间: 2023-12-10 22:35:28 浏览: 31
以下是实现图的遍历算法的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("请输入各个顶点的数据:");
for (int i = 0; i < G->vexnum; i++) {
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;
printf("请输入第%d条边的顶点1和顶点2:", k + 1);
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; p = (ArcNode *)malloc(sizeof(ArcNode));
p->adjvex = i;
p->nextarc = G->vertices[j].firstarc;
G->vertices[j].firstarc = p;
}
}
void DFS(ALGraph G, int v, int visited[]) { // 深度优先遍历
visited[v] = 1;
printf("%c ", G.vertices[v].data);
ArcNode *p = G.vertices[v].firstarc;
while (p != NULL) {
if (!visited[p->adjvex]) {
DFS(G, p->adjvex, visited);
}
p = p->nextarc;
}
}
void DFSTraverse(ALGraph G) { // 深度优先遍历图
int visited[MAX_VERTEX_NUM] = {0};
printf("深度优先遍历结果为:");
for (int i = 0; i < G.vexnum; i++) {
if (!visited[i]) {
DFS(G, i, visited);
}
}
printf("\n");
}
void BFS(ALGraph G, int v, int visited[]) { // 广度优先遍历
int queue[MAX_VERTEX_NUM], front = 0, rear = 0;
printf("%c ", G.vertices[v].data);
visited[v] = 1;
queue[rear++] = v;
while (front != rear) {
int w = queue[front++];
ArcNode *p = G.vertices[w].firstarc;
while (p != NULL) {
if (!visited[p->adjvex]) {
printf("%c ", G.vertices[p->adjvex].data);
visited[p->adjvex] = 1;
queue[rear++] = p->adjvex;
}
p = p->nextarc;
}
}
}
void BFSTraverse(ALGraph G) { // 广度优先遍历图
int visited[MAX_VERTEX_NUM] = {0};
printf("广度优先遍历结果为:");
for (int i = 0; i < G.vexnum; i++) {
if (!visited[i]) {
BFS(G, i, visited);
}
}
printf("\n");
}
int main() {
ALGraph G;
CreateGraph(&G);
DFSTraverse(G);
BFSTraverse(G);
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)