试写一算法，判断以邻接表方式存储的有向图中是否存在由顶点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 【样例说明】 【评分标准】 【代码框架】 #include<stdio.h> #include<malloc.h> #define OK 1 #define ERROR 0 #define MAX_VEX_NUM 100 //最大顶点数量 typedef int Status; typedef enum{AG,AN,DG,DN} GKind; //图类型定义 typedef struct ArcNode{ int adjvex; //邻接点数组下标（从0开始） struct ArcNode *nextarc; int weight; }; typedef struct { int vertex; //顶点编号，从1开始 ArcNode *firstarc; }VNode,AdjList[MAX_VEX_NUM]; typedef struct{ AdjList vertices; int vexnum; int arcnum; GKind kind; }ALGraph; Status InitALGraph(ALGraph &G) { } //创建图的邻接表存储结构 //n: 顶点数 //vertices[]:顶点数组 //edges[][]:边数组 //edgesSize：边数目 Status CreateALGraph(ALGraph &G, int n, int vertices[ ], int edges[20][2], int edgesSize) { } //连通图的深度优先搜索 //v0: 起点的数组下标（从0开始） //visited[ ]:访问标志数组 void DFS(ALGraph G, int v0, int visited[]) { } //图的深度优先搜索 int DFSTraverse(ALGraph G) { } // 判断图的两个顶点是否连通，如果连通，返回true, 否则返回false //v: 起点的编号（从1开始） //w:终点的编号（从1开始） bool isConnect(ALGraph G, int v, int w) { }

#include<stdio.h>
#include<malloc.h>

#define OK 1
#define ERROR 0
#define MAX_VEX_NUM 100 //最大顶点数量

typedef int Status;
typedef enum{AG,AN,DG,DN} GKind; //图类型定义

typedef struct ArcNode{
    int adjvex;      //邻接点数组下标（从0开始）
    struct ArcNode *nextarc;
    int weight;
}ArcNode;

typedef struct VNode{
    int vertex;  //顶点编号，从1开始
    ArcNode *firstarc;
}VNode,AdjList[MAX_VEX_NUM];

typedef struct{
    AdjList vertices;
    int vexnum;
    int arcnum;
    GKind kind;
}ALGraph;

Status InitALGraph(ALGraph &G){
    G.vexnum = 0;
    G.arcnum = 0;
    G.kind = DG;    //默认为有向图
    for(int i = 0; i < MAX_VEX_NUM; i++){
        G.vertices[i].vertex = 0;
        G.vertices[i].firstarc = NULL;
    }
    return OK;
}

Status CreateALGraph(ALGraph &G, int n, int vertices[],  int edges[20][2], int edgesSize){
    G.vexnum = n;
    G.arcnum = edgesSize;
    for(int i = 0; i < n; i++){
        G.vertices[i].vertex = vertices[i];
    }
    for(int i = 0; i < edgesSize; i++){
        int v1 = edges[i][0]-1;
        int v2 = edges[i][1]-1;
        ArcNode *arc = (ArcNode*)malloc(sizeof(ArcNode));
        arc->adjvex = v2;
        arc->nextarc = G.vertices[v1].firstarc;
        G.vertices[v1].firstarc = arc;
    }
    return OK;
}

void DFS(ALGraph G, int v0, int visited[]){
    visited[v0] = 1;
    ArcNode *p = G.vertices[v0].firstarc;
    while(p != NULL){
        int w = p->adjvex;
        if(visited[w] == 0){
            DFS(G, w, visited);
        }
        p = p->nextarc;
    }
}

int DFSTraverse(ALGraph G){
    int visited[MAX_VEX_NUM] = {0};
    int count = 0;
    for(int i = 0; i < G.vexnum; i++){
        if(visited[i] == 0){
            count++;
            DFS(G, i, visited);
        }
    }
    return count;
}

bool isConnect(ALGraph G, int v, int w){
    int visited[MAX_VEX_NUM] = {0};
    int v0 = v-1, w0 = w-1;
    DFS(G, v0, visited);
    if(visited[w0] == 1){
        return true;
    }
    return false;
}

int main(){
    ALGraph G;
    int n, m, v, w;
    int vertices[MAX_VEX_NUM];
    int edges[20][2];
    scanf("%d%d", &n, &m);
    for(int i = 0; i < n; i++){
        scanf("%d", &vertices[i]);
    }
    for(int i = 0; i < m; i++){
        scanf("%d%d", &edges[i][0], &edges[i][1]);
    }
    InitALGraph(G);
    CreateALGraph(G, n, vertices, edges, m);
    scanf("%d%d", &v, &w);
    if(isConnect(G, v, w)){
        printf("True\n");
    }
    else{
        printf("False\n");
    }
    return 0;
}