采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法 c语言

以下是采用深度优先搜索算法实现的判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。其中，邻接表存储结构使用了结构体数组和链表。

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

#define MAX_VERTEX_NUM 100 // 最大顶点数
#define FALSE 0
#define TRUE 1

typedef struct ArcNode { // 邻接表中边结点的类型
    int adjvex; // 该边所指向的顶点的位置
    struct ArcNode *nextarc; // 指向下一条边的指针
} ArcNode;

typedef struct VertexNode { // 邻接表中顶点结点的类型
    int data; // 顶点信息
    ArcNode *firstarc; // 指向第一条依附该顶点的边的指针
} VertexNode;

typedef struct { // 邻接表的类型
    VertexNode vertices[MAX_VERTEX_NUM]; // 顶点数组
    int vexnum, arcnum; // 图的当前顶点数和边数
} ALGraph;

int visited[MAX_VERTEX_NUM]; // 访问标志数组

// 创建邻接表
void CreateALGraph(ALGraph *G) {
    int i, j, k;
    ArcNode *p;
    printf("请输入顶点数和边数（空格隔开）：");
    scanf("%d %d", &G->vexnum, &G->arcnum);
    for (i = 0; i < G->vexnum; ++i) {
        printf("请输入第%d个顶点信息：", i + 1);
        scanf("%d", &G->vertices[i].data);
        G->vertices[i].firstarc = NULL;
    }
    for (k = 0; k < G->arcnum; ++k) {
        printf("请输入边（vi，vj）的下标i和j及其边权值w（空格隔开）：");
        scanf("%d %d", &i, &j);
        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;
    }
}

// 深度优先搜索算法
int DFS(ALGraph *G, int v, int w, int k) {
    int flag = FALSE;
    if (k == 0) { // 到达目标深度
        if (v == w) // 判断是否为目标顶点
            flag = TRUE;
    } else {
        visited[v] = TRUE; // 将当前顶点标记为已访问
        ArcNode *p = G->vertices[v].firstarc;
        while (p && !flag) { // 遍历当前顶点的所有邻接顶点
            if (!visited[p->adjvex]) // 如果邻接顶点未被访问过
                flag = DFS(G, p->adjvex, w, k - 1);
            p = p->nextarc;
        }
        visited[v] = FALSE; // 恢复当前顶点的未访问状态
    }
    return flag;
}

// 判断无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法
int ExistSimplePath(ALGraph *G, int u, int v, int k) {
    int i;
    if (u < 0 || u >= G->vexnum || v < 0 || v >= G->vexnum) // 判断输入的顶点是否合法
        return FALSE;
    if (k <= 0) // 判断输入的深度是否合法
        return FALSE;
    for (i = 0; i < G->vexnum; ++i)
        visited[i] = FALSE; // 初始化访问标志数组
    return DFS(G, u, v, k); // 判断是否存在一条长度为k的简单路径
}

int main() {
    ALGraph G;
    CreateALGraph(&G);
    int u, v, k;
    printf("请输入要判断的两个顶点u和v以及路径长度k（空格隔开）：");
    scanf("%d %d %d", &u, &v, &k);
    if (ExistSimplePath(&G, u, v, k))
        printf("存在一条长度为%d的简单路径从顶点%d到顶点%d\n", k, u, v);
    else
        printf("不存在一条长度为%d的简单路径从顶点%d到顶点%d\n", k, u, v);
    return 0;
}

在上述算法中，先通过CreateALGraph函数建立无向图的邻接表，然后在ExistSimplePath函数中对给定的两个顶点u和v以及路径长度k进行判断。接着，在DFS函数中实现了深度优先搜索算法，其中visited数组用于标记顶点是否被访问过，p指针用于遍历当前顶点的所有邻接顶点。最后，根据DFS函数的返回结果，判断是否存在一条长度为k的简单路径。