c语言基于邻接表的DFS遍历算法,用户输入总顶点数和总边数，再输入每个顶点，再输入每条边依附的顶点对序列 ,得到邻接表表示法创建的无向图，再输入遍历连通图的起始点，得到深度优先搜索遍历图结果 完整代码 算法思想

以下是基于邻接表的DFS遍历算法的C语言代码及算法思想。

算法思想：

1. 定义一个邻接表结构体，用于存储无向图的信息；
2. 根据用户输入的总顶点数和总边数，创建邻接表，将每个顶点的名称存储到邻接表中；
3. 根据用户输入的每条边依附的顶点对序列，将每个顶点的邻接点信息存储到邻接表中；
4. 根据用户输入的遍历起始点，进行深度优先搜索遍历图，将遍历结果输出。

代码实现如下：

#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