试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点Vi到顶点Vj的路径（i-->j）。 【输入形式】 顶点个数：n 边的条数：m 边的有向顶点对： （a,b）…… 待判断定点i，j 【输出形式】 True 或 False 【样例输入】 5 4 1 2 1 3 2 4 3 5 1 5 【样例输出】 True.用c语言实现的完整代码

以下是判断有向图中是否存在由Vi到Vj的路径的C语言实现：

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

#define MAX_VERTEX_NUM 100 //最大顶点数

typedef struct ArcNode {
    int adjvex;             //邻接点在数组中的位置下标
    struct ArcNode *nextarc;//指向下一个邻接点的指针
} ArcNode;

typedef struct VertexNode {
    int data;               //顶点的数据
    ArcNode *firstarc;      //指向第一个邻接点的指针
} VertexNode;

typedef struct {
    VertexNode adjlist[MAX_VERTEX_NUM]; //邻接表
    int vexnum, arcnum;                 //顶点数和边数
} ALGraph;

//创建有向图的邻接表
void CreateALGraph(ALGraph *G) {
    int i, j, k;
    ArcNode *e;
    printf("请输入顶点数和边数：");
    scanf("%d%d", &G->vexnum, &G->arcnum);
    printf("请输入各边的顶点对：\n");
    for (i = 0; i < G->vexnum; i++) {
        printf("请输入第%d个顶点的值：", i + 1);
        scanf("%d", &G->adjlist[i].data);
        G->adjlist[i].firstarc = NULL;
    }
    for (k = 0; k < G->arcnum; k++) {
        printf("请输入第%d条边的顶点对：", k + 1);
        scanf("%d%d", &i, &j);
        i--;
        j--;
        e = (ArcNode *) malloc(sizeof(ArcNode));
        e->adjvex = j;
        e->nextarc = G->adjlist[i].firstarc;
        G->adjlist[i].firstarc = e;
    }
}

//判断是否存在从Vi到Vj的路径
int ExistPath(ALGraph *G, int i, int j) {
    int visited[MAX_VERTEX_NUM] = {0}; //标记数组，记录顶点是否被访问过
    ArcNode *p;
    if (i == j) return 1; //起点和终点相同，直接返回1
    visited[i] = 1; //标记起点已访问
    p = G->adjlist[i].firstarc;
    while (p != NULL) {
        if (!visited[p->adjvex] && ExistPath(G, p->adjvex, j)) {
            return 1;
        }
        p = p->nextarc;
    }
    return 0;
}

int main() {
    ALGraph G;
    int i, j;
    CreateALGraph(&G);
    printf("请输入待判断路径的起点和终点：");
    scanf("%d%d", &i, &j);
    i--;
    j--;
    if (ExistPath(&G, i, j)) {
        printf("True.\n");
    } else {
        printf("False.\n");
    }
    return 0;
}

输入样例：

请输入顶点数和边数：5 4
请输入各边的顶点对：
请输入第1个顶点的值：1
请输入第2个顶点的值：2
请输入第3个顶点的值：3
请输入第4个顶点的值：4
请输入第5个顶点的值：5
请输入第1条边的顶点对：1 2
请输入第2条边的顶点对：1 3
请输入第3条边的顶点对：2 4
请输入第4条边的顶点对：3 5
请输入待判断路径的起点和终点：1 5

输出样例：

True.