c语言基于邻接表的DFS遍历算法,用户输入总顶点数和总边数,再输入每个顶点,再输入每条边依附的顶点对序列 ,得到邻接表表示法创建的无向图,再输入遍历连通图的起始点,得到深度优先搜索遍历图结果 完整代码 算法思想
时间: 2024-03-31 13:36:51 浏览: 41
以下是基于邻接表的DFS遍历算法的C语言代码及算法思想。
算法思想:
1. 定义一个邻接表结构体,用于存储无向图的信息;
2. 根据用户输入的总顶点数和总边数,创建邻接表,将每个顶点的名称存储到邻接表中;
3. 根据用户输入的每条边依附的顶点对序列,将每个顶点的邻接点信息存储到邻接表中;
4. 根据用户输入的遍历起始点,进行深度优先搜索遍历图,将遍历结果输出。
代码实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MAX_VERTEX_NUM 100 // 最大顶点数
// 邻接点结构体
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; // 总顶点数
int arcnum; // 总边数
}ALGraph;
// 初始化邻接表
void InitGraph(ALGraph *G) {
printf("请输入总顶点数和总边数:\n");
scanf("%d%d", &G->vexnum, &G->arcnum);
getchar(); // 清空缓冲区
printf("请输入每个顶点名称:\n");
for (int i = 0; i < G->vexnum; i++) {
scanf("%c", &G->vertices[i].data);
G->vertices[i].firstarc = NULL; // 初始化邻接表中每个顶点的邻接点链表为空
}
getchar(); // 清空缓冲区
printf("请输入每条边依附的顶点对序列:\n");
for (int i = 0; i < G->arcnum; i++) {
char v1, v2;
int index1, index2;
scanf("%c%c", &v1, &v2);
getchar(); // 清空缓冲区
// 获取顶点在邻接表中的位置
for (int j = 0; j < G->vexnum; j++) {
if (G->vertices[j].data == v1) {
index1 = j;
}
if (G->vertices[j].data == v2) {
index2 = j;
}
}
// 创建邻接点结构体并添加到邻接表的链表中
ArcNode *arc1 = (ArcNode*)malloc(sizeof(ArcNode));
arc1->adjvex = index2;
arc1->next = G->vertices[index1].firstarc;
G->vertices[index1].firstarc = arc1;
ArcNode *arc2 = (ArcNode*)malloc(sizeof(ArcNode));
arc2->adjvex = index1;
arc2->next = G->vertices[index2].firstarc;
G->vertices[index2].firstarc = arc2;
}
}
// DFS遍历邻接表
void DFS(ALGraph G, int v, bool visited[]) {
visited[v] = true; // 标记当前顶点已访问
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->next;
}
}
// 深度优先搜索遍历图
void DFSTraverse(ALGraph G, int v) {
bool visited[MAX_VERTEX_NUM] = { false }; // 初始化所有顶点未访问
printf("深度优先搜索遍历图结果:\n");
DFS(G, v, visited);
}
int main() {
ALGraph G;
InitGraph(&G);
printf("请输入遍历连通图的起始点:\n");
char start;
scanf("%c", &start);
getchar(); // 清空缓冲区
// 获取起始点在邻接表中的位置
int index;
for (int i = 0; i < G.vexnum; i++) {
if (G.vertices[i].data == start) {
index = i;
break;
}
}
DFSTraverse(G, index);
return 0;
}
```
输入示例:
```
请输入总顶点数和总边数:
5 5
请输入每个顶点名称:
A B C D E
请输入每条边依附的顶点对序列:
AB AC AD BD CD
请输入遍历连通图的起始点:
A
```
输出示例:
```
深度优先搜索遍历图结果:
A B D C E
```
阅读全文