2.试基于图的深度优先搜索策略编写一程序，判别以邻接表方式存储的有向图中是否存在有顶点vi到vj顶点的路径(i≠j)。

### 回答1：
可以使用深度优先搜索算法来判断以邻接表方式存储的有向图中是否存在从顶点vi到vj的路径（i≠j）。

具体实现步骤如下：

1. 定义一个visited数组，用于记录每个顶点是否已经被访问过。

2. 从顶点vi开始进行深度优先搜索，将vi标记为已访问。

3. 对于vi的每个邻接顶点vj，如果vj没有被访问过，则递归访问vj。

4. 如果在搜索过程中找到了顶点vj，则说明存在从vi到vj的路径。

5. 如果搜索结束后仍然没有找到顶点vj，则说明不存在从vi到vj的路径。

下面是一个简单的Python代码实现：

def dfs(graph, visited, start, end):
    visited[start] = True
    if start == end:
        return True
    for neighbor in graph[start]:
        if not visited[neighbor]:
            if dfs(graph, visited, neighbor, end):
                return True
    return False

# 测试代码
graph = {
    1: [2, 3],
    2: [4],
    3: [4],
    4: [5],
    5: []
}
visited = {i: False for i in graph.keys()}
print(dfs(graph, visited, 1, 5))  # 输出True
print(dfs(graph, visited, 1, 6))  # 输出False

其中，graph表示邻接表存储的有向图，visited表示每个顶点是否已经被访问过，start表示搜索的起点，end表示搜索的终点。在测试代码中，我们使用了一个简单的有向图进行测试，分别测试了存在路径和不存在路径的情况。

### 回答2：
深度优先搜索是一种经典的图遍历算法，它从某个起始顶点开始，沿着深度（或高度）方向搜索，直到找到目标顶点或者无法继续搜索为止。在有向图中，深度优先搜索可以用于判断两个顶点之间是否存在路径。本文将基于邻接表方式存储的有向图，编写一个深度优先搜索的程序，来实现找到从顶点vi 到顶点vj 的路径。

首先来了解一下图的存储方式，图可以通过邻接矩阵和邻接表两种方式存储，其中邻接表的方式更加节省空间。因此，本文采用邻接表作为存储方式。邻接表的关键是使用链表来存储每个顶点相邻的其他顶点。

算法步骤：

1. 从起点vi 开始进行深度优先搜索，遍历从vi 出发能够到达的所有顶点，并将经过的顶点标记为已访问过。

2. 如果当前搜索的顶点是vj，则说明从vi 到vj 存在一条路径，搜索完成。

3. 如果当前搜索的顶点不是vj，则继续递归搜索当前节点的所有未访问过的相邻顶点，直到遍历完所有能到达的顶点。

4. 如果在搜索完成的过程中始终没有找到vj，则说明不存在从vi 到vj 的路径。

以下是基于邻接表方式的深度优先搜索程序代码实现：

class Graph():
    def __init__(self, V):
        self.V = V
        self.adj = [[] for i in range(V)]
        self.visited = [False] * V
        
    def addEdge(self, v, w):
        self.adj[v].append(w)
        
    def DFS(self, v, w):
        self.visited[v] = True
        
        if v == w:
            return True
        
        for i in self.adj[v]:
            if not self.visited[i]:
                if self.DFS(i, w):
                    return True
        return False


#测试代码
g = Graph(4)
g.addEdge(0, 1)
g.addEdge(1, 2)
g.addEdge(2, 3)

v = 0
w = 3

if g.DFS(v, w):
    print("存在从{}到{}的路径".format(v, w))
else:
    print("不存在从{}到{}的路径".format(v, w))

在上述代码中，我们定义了Graph类来表示图。在类的构造函数中，我们初始化了邻接表、访问数组以及顶点数量。addEdge()方法用于在邻接表中添加边。DFS()方法实现了深度优先搜索过程，从起点v 开始搜索，如果找到目标顶点w，则返回True。

最后，我们通过创建Graph对象，调用DFS()方法，并输出结果，来验证程序的正确性。

总结

在本文中，我们基于邻接表方式存储的有向图，编写了一个深度优先搜索的程序，实现了查找从顶点vi 到顶点vj 的路径的功能。深度优先搜索是一种常用的算法，可以用于图的遍历、路径查找等问题。在实际应用中，我们可以根据具体问题来选择适合的图存储方式和搜索算法。

### 回答3：
深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。在深度优先搜索中，首先访问一个顶点，然后再依次访问此顶点的未被访问的邻居，重复此过程直到访问完所有可达的顶点。基于图的深度优先搜索算法可以用于判断以邻接表方式存储的有向图中是否存在从顶点vi到顶点vj的路径。

接下来，我们将编写一个基于邻接表的深度优先搜索算法，用于判断是否存在从vi到vj的路径。（以下代码使用C++语言实现）

1. 从源文件中读入邻接表

我们需要从源文件中读入邻接表，存储为一个二维数组adjacencyList，其中第i个元素adjacencyList[i]表示以i为起点的所有边的终点（即邻居）的一个列表。代码如下：

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

vector<int> adjacencyList[100]; // 假设最多有100个顶点

// 从文件中读入邻接表
void readGraph(string filename) {
    ifstream fin(filename);
    int u, v;
    while (fin >> u >> v) {
        adjacencyList[u].push_back(v);
    }
}

上述代码中，我们定义了一个全局变量adjacencyList，表示邻接表，使用vector容器存储。readGraph函数从文件中读入每个一对顶点对(u,v)，并将v加入以u为起点的邻居列表中。

2. 基于深度优先搜索算法实现路径查找

我们使用递归实现基于深度优先搜索算法的路径查找。具体步骤如下：

（1）定义函数hasPath

这个函数用于判断图中是否存在从顶点i到顶点j的路径。函数返回值类型为bool类型，当存在路径时返回true，否则返回false。

// 判断是否存在从i到j的路径
bool hasPath(int i, int j) {
    // TODO: 实现深度优先搜索算法查找路径
}

（2）针对当前节点i的所有未被访问过的邻居v，进行递归查找

如果一个顶点v未被访问过，我们先将其标记为已访问，并递归调用hasPath函数继续查找以v为起点，j为终点的路径。如果存在这样的路径，则返回true，否则继续遍历i的其他邻居节点。若所有未被访问节点都被检查过仍未找到从i到j的路径，则返回false。

bool hasPath(int i, int j) {
    if (i == j) { // 如果起点和终点相同，直接返回true
        return true;
    }

    for (int v : adjacencyList[i]) { // 针对起点i的所有未被访问过的邻居v
        if (v == j) { // 如果邻居是终点，返回true
            return true;
        }

        // 否则继续递归查找
        if (!visited[v]) {
            visited[v] = true; // 标记为已访问
            if (hasPath(v, j)) {
                return true;
            }
        }
    }

    return false;
}

上述代码中，visited是一个bool类型的数组，表示每个顶点是否已被访问，初始时所有元素都应该为false。

3. 完整程序示例

下面是一个完整的程序代码示例，包括从文件中读入邻接表，并实现了基于深度优先搜索算法的路径查找函数。

#include <iostream>
#include <fstream>
#include <vector>

using namespace std;

vector<int> adjacencyList[100]; // 假设最多有100个顶点
bool visited[100];

// 从文件中读入邻接表
void readGraph(string filename) {
    ifstream fin(filename);
    int u, v;
    while (fin >> u >> v) {
        adjacencyList[u].push_back(v);
    }
}

// 判断是否存在从i到j的路径
bool hasPath(int i, int j) {
    if (i == j) { // 如果起点和终点相同，直接返回true
        return true;
    }

    for (int v : adjacencyList[i]) { // 针对起点i的所有未被访问过的邻居v
        if (v == j) { // 如果邻居是终点，返回true
            return true;
        }

        // 否则继续递归查找
        if (!visited[v]) {
            visited[v] = true; // 标记为已访问
            if (hasPath(v, j)) {
                return true;
            }
        }
    }

    return false;
}

int main() {
    readGraph("graph.txt");

    if (hasPath(1, 5)) {
        cout << "存在从1到5的路径" << endl;
    } else {
        cout << "不存在从1到5的路径" << endl;
    }

    return 0;
}

上述代码中，我们读入文件"graph.txt"，该文件包含了以下邻接表：

1 2
1 3
2 4
2 5
3 4
5 4

我们调用hasPath函数尝试查找从1到5的路径，程序输出"存在从1到5的路径"。

总结

本文介绍了一种基于图的深度优先搜索算法，用于查找有向图中是否存在从起点到终点的路径。虽然本文提到的邻接表存储图的方式适用于较小的图，但通过类似的方式可以更为通用地实现针对大型图的深度优先搜索算法。