C语言【问题描述】 试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点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 语言实现：

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

#define MAXN 1000

typedef struct Node {
    int val;
    struct Node *next;
} Node;

Node *graph[MAXN]; // 邻接表
int visited[MAXN]; // 标记数组

// 添加有向边
void add_edge(int u, int v) {
    Node *node = (Node*) malloc(sizeof(Node));
    node->val = v;
    node->next = graph[u];
    graph[u] = node;
}

// DFS 遍历图，判断是否存在从 i 到 j 的路径
int has_path(int i, int j) {
    if (i == j) return 1; // 到达目标结点
    visited[i] = 1; // 标记当前结点已访问
    for (Node *p = graph[i]; p != NULL; p = p->next) {
        if (!visited[p->val] && has_path(p->val, j)) {
            return 1;
        }
    }
    return 0;
}

int main() {
    int n, m, u, v, i, j;
    scanf("%d %d", &n, &m);
    // 初始化邻接表
    for (i = 1; i <= n; i++) {
        graph[i] = NULL;
        visited[i] = 0;
    }
    // 读入边
    for (i = 0; i < m; i++) {
        scanf("%d %d", &u, &v);
        add_edge(u, v);
    }
    // 读入待判断的 i 和 j
    scanf("%d %d", &i, &j);
    // 判断是否存在从 i 到 j 的路径
    if (has_path(i, j)) {
        printf("True\n");
    } else {
        printf("False\n");
    }
    return 0;
}

算法的思路是使用 DFS 遍历图，从结点 i 开始，递归地访问其邻接点，直到到达目标结点 j 或者遍历完所有可到达的结点。visited 数组用于标记已访问的结点，避免重复访问和死循环。时间复杂度为 O(n+m)，其中 n 为顶点个数，m 为边的条数。