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

算法思想：

深度优先搜索（Depth First Search，DFS）是一种用于遍历或搜索树或图的算法。其思路是从起点出发，沿着一条路径不断往下搜索直到无法继续为止，然后回溯到前一个节点继续搜索，直到所有的节点都被访问一次。

在基于邻接表表示法的图中，每个顶点都对应一个链表，链表中存储该顶点所连接的其他顶点。可以使用数组来存储每个链表的头结点，然后按照指定顺序将每条边加入邻接表中。

深度优先搜索算法可以使用递归或栈来实现。递归实现时，从起点开始，按照某种顺序遍历其相邻的节点，并对每个未访问过的节点进行递归搜索。栈实现时，从起点开始，将其入栈，然后循环进行以下操作：弹出栈顶元素并访问，将其未访问过的相邻节点入栈，直到栈为空为止。

完整代码如下：

#include <stdio.h>
#include <stdlib.h>

#define MAXV 100 // 图的最大顶点数

// 边结构体
typedef struct EdgeNode {
    int adjvex; // 邻接点编号
    struct EdgeNode *next; // 指向下一条边的指针
} EdgeNode;

// 顶点结构体
typedef struct VertexNode {
    char data; // 顶点数据
    EdgeNode *firstedge; // 指向第一条边的指针
} VertexNode;

// 邻接表结构体
typedef struct {
    VertexNode adjlist[MAXV]; // 顶点数组
    int n, e; // 顶点数和边数
} AdjList;

// 标记数组，记录每个顶点是否已被访问过
int visited[MAXV];

// 创建邻接表
void createGraph(AdjList *G) {
    printf("请输入总顶点数和总边数：");
    scanf("%d%d", &G->n, &G->e);
    getchar(); // 读取换行符
    printf("请输入每个顶点的数据：");
    for (int i = 0; i < G->n; i++) {
        scanf("%c", &G->adjlist[i].data);
        G->adjlist[i].firstedge = NULL; // 初始化链表头指针
    }
    getchar(); // 读取换行符
    printf("请输入每条边依附的顶点对序列：\n");
    for (int k = 0; k < G->e; k++) {
        int i, j;
        scanf("%d%d", &i, &j);
        EdgeNode *e1 = (EdgeNode*)malloc(sizeof(EdgeNode));
        EdgeNode *e2 = (EdgeNode*)malloc(sizeof(EdgeNode));
        e1->adjvex = j;
        e1->next = G->adjlist[i].firstedge;
        G->adjlist[i].firstedge = e1;
        e2->adjvex = i;
        e2->next = G->adjlist[j].firstedge;
        G->adjlist[j].firstedge = e2;
    }
}

// 深度优先搜索遍历连通图的递归函数
void DFS(AdjList G, int v) {
    visited[v] = 1; // 标记顶点 v 已被访问过
    printf("%c ", G.adjlist[v].data); // 输出顶点 v 的数据
    EdgeNode *p = G.adjlist[v].firstedge;
    while (p != NULL) {
        int w = p->adjvex; // 取出邻接点编号
        if (visited[w] == 0) { // 如果邻接点未被访问过，则递归访问它
            DFS(G, w);
        }
        p = p->next; // 找下一个邻接点
    }
}

int main() {
    AdjList G;
    createGraph(&G);
    printf("请输入遍历连通图的起始点：");
    int v;
    scanf("%d", &v);
    printf("深度优先搜索遍历结果为：");
    DFS(G, v);
    printf("\n");
    return 0;
}

以上代码基于邻接表实现了深度优先搜索遍历算法，用户可以根据提示输入图的信息和遍历起点，程序将输出深度优先搜索遍历的结果。