判断有向图g中两个顶点间是否存在路径代码

以下是判断有向图g中两个顶点间是否存在路径的Python代码示例：

def has_path(g, start, end):
    """
    判断有向图g中从start到end是否存在路径
    参数：
    g: 有向图，使用字典表示，键为顶点，值为该顶点指向的顶点列表
    start: 起始顶点
    end: 目标顶点
    返回值：
    如果存在从start到end的路径，返回True，否则返回False
    """
    visited = set()  # 已访问过的顶点集合
    stack = [start]  # 存储待访问的顶点栈
    while stack:
        vertex = stack.pop()
        if vertex == end:
            return True
        if vertex not in visited:
            visited.add(vertex)
            stack.extend(g[vertex])
    return False

使用示例：

g = {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': ['E'], 'E': []}
print(has_path(g, 'A', 'E'))  # 输出 True
print(has_path(g, 'B', 'C'))  # 输出 False

相关问题

判断有向图g中两个顶点间是否存在路径

可以使用深度优先搜索（DFS）或广度优先搜索（BFS）来判断有向图g中两个顶点间是否存在路径。具体地，以其中一个顶点作为起点，沿着有向边进行搜索，如果能够到达另一个顶点，则说明它们之间存在路径。如果搜索完所有顶点都没有找到目标顶点，则说明它们之间不存在路径。需要注意的是，如果图中存在环路，则可能会导致死循环，因此需要标记已经访问过的顶点，避免重复访问。

采用邻接表存储有向图，设计算法判断任意两个顶点间是否存在路径。

### 回答1：
可以使用深度优先搜索（DFS）或广度优先搜索（BFS）算法来判断任意两个顶点间是否存在路径。

具体实现步骤如下：

1. 初始化一个布尔型数组visited，用于记录每个顶点是否被访问过，初始值为false。

2. 从起始顶点开始，对邻接表中的每个相邻顶点进行遍历，如果该相邻顶点未被访问过，则将其标记为已访问，并递归调用该顶点的相邻顶点，直到找到目标顶点或者所有相邻顶点都被访问过。

3. 如果找到目标顶点，则返回true，否则返回false。

4. 如果使用BFS算法，则需要使用一个队列来存储待访问的顶点，每次从队列中取出一个顶点进行访问，并将其相邻顶点加入队列中，直到找到目标顶点或者队列为空。

需要注意的是，如果图中存在环，则需要对已访问过的顶点进行标记，以避免死循环。

### 回答2：
有向图是由一些点和有向边连接这些点所组成的图，其中每个点表示一个事物，每条有向边表示关系。

邻接表是一种存储图的方式，它是由一个一维数组和各个链表组成的，每个数组元素对应一个顶点，每个链表表示以它的数组下标为起点的一条边。

判断任意两个顶点间是否存在路径，可以采用深度优先遍历(DFS)的方法，从一个点开始深度遍历整张图来找到与该节点有路径相通的其他节点。深度遍历可以通过递归实现，具体步骤如下：

1. 从起始节点开始，将该节点标记为已访问，同时输出该节点的值。

2. 查找该节点的邻居节点，如果邻居节点未被访问过，则递归访问它，并将邻居节点标记为已访问。

3. 重复步骤2，直到所有与该节点有路径相通的节点都被遍历完。

如果在执行深度优先遍历时遇到目标节点，则说明这两个节点间存在路径；否则，两个节点间不存在路径。

具体代码实现如下：

bool hasPathDFS(int start, int target, vector<vector<int>>& graph, vector<bool>& visited) {
    if (start == target) {
        return true;
    }
    visited[start] = true;
    for (int neighbor : graph[start]) {
        if (!visited[neighbor]) {
            if (hasPathDFS(neighbor, target, graph, visited)) {
                return true;
            }
        }
    }
    return false;
}

bool hasPath(int start, int target, vector<vector<int>>& graph) {
    vector<bool> visited(graph.size(), false);
    return hasPathDFS(start, target, graph, visited);
}

其中，hasPath是主函数，hasPathDFS是深度优先遍历的递归函数。graph表示邻接表，visited用于标记是否访问过节点。如果有路径相连，则返回true，否则返回false。

总之，邻接表存储有向图，深度优先遍历可以判断任意两个顶点间是否存在路径，通过递归访问与起始节点相连的所有节点来查找目标节点。

### 回答3：
邻接表是一种常用的存储有向图的方式，它把每个顶点的出边放在一个链表中，我们可以使用邻接表存储有向图，并设计一个算法判断任意两个顶点间是否存在路径。

一种朴素的想法是：从起始顶点开始，一层层地往外扩展，看是否能够到达终止顶点。这种方法可以使用深度优先搜索（DFS）或广度优先搜索（BFS）实现。

以下是使用DFS实现的算法步骤：

1. 初始化visited数组为False，用于记录每个顶点的访问状态。
2. 从起始顶点开始，对邻接表链表的第一个节点依次进行深度遍历，如果当前节点未被访问过（visited为False），则将其visited标记为True。如果在这个过程中找到了终止顶点，算法结束并返回True，否则继续对相邻的节点进行DFS搜索。
3. 如果在整个图中都无法到达终止顶点，则返回False。

以下是使用BFS实现的算法步骤：

1. 初始化visited数组为False，用于记录每个顶点的访问状态。
2. 从起始顶点开始，将其加入队列中，并将visited标记为True。
3. 从队列中出队一个元素，遍历它的所有相邻节点，如果该节点未被访问过（visited为False），则将其加入队列，并将visited标记为True。
4. 如果在这个过程中找到了终止顶点，算法结束并返回True，否则继续出队下一个元素。
5. 如果在整个图中都无法到达终止顶点，则返回False。

无论是DFS还是BFS，其时间复杂度都是O(V+E)，其中V表示顶点数，E表示边数。因此，当有多组顶点需要判断时，如果图规模比较大，可以考虑预处理出每对顶点间的路劲，以便快速查询。此外，对于特定的结构化图，比如DAG（有向无环图），还可以使用拓扑排序等高效算法，更快地判断两个顶点是否存在路径。