◆7.228试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点到顶点的路径（i≠j）。注意：算法中涉及的图的基本操作必须在此存储结构上实现。

好的，以下是基于图的深度优先搜索算法实现，用于判断有向图中是否存在从顶点i到顶点j的路径：

// 定义一个辅助函数进行深度优先搜索
void DFS(int i, int j, int *visited, int **adj_matrix, int *flag) {
    visited[i] = 1;  // 标记当前顶点已被访问
    if (i == j) {  // 如果当前顶点为目标顶点j，则说明存在路径
        *flag = 1;
        return;
    }
    for (int k = 0; k < adj_matrix[i][0]; k++) {  // 遍历当前顶点的所有邻居
        int neighbor = adj_matrix[i][k+1];
        if (!visited[neighbor]) {  // 如果邻居顶点未被访问，则递归访问它
            DFS(neighbor, j, visited, adj_matrix, flag);
        }
    }
}

// 判断有向图中是否存在从顶点i到顶点j的路径
int hasPath(int i, int j, int **adj_matrix, int n) {
    int *visited = (int*)malloc(sizeof(int) * n);  // 创建一个标记数组，用于记录每个顶点是否被访问过
    memset(visited, 0, n * sizeof(int));  // 初始化为0，表示所有顶点均未被访问过
    int flag = 0;  // 初始化标记变量为0，表示尚未找到路径
    DFS(i, j, visited, adj_matrix, &flag);  // 从起始顶点i开始进行深度优先搜索
    free(visited);  // 释放标记数组的内存
    return flag;  // 返回标记变量的值，表示是否找到了路径
}

该算法的主要思想是通过深度优先搜索（DFS）遍历整个有向图，通过标记数组记录每个顶点是否被访问过，直到找到目标顶点j或者遍历完整个图为止。在遍历的过程中，如果当前顶点的某个邻居顶点未被访问过，则递归访问它，直到所有邻居顶点都被访问过为止。如果在搜索的过程中找到了目标顶点j，则说明存在从顶点i到顶点j的路径。否则，说明不存在这样的路径。