基于Directed graph的城市道路系统全域可达性检测算法需求

嘿，你的需求本质就是要判断一个有向图是否是强连通图——简单说就是图里任意两个路口（节点），既能从A顺着单行道开到B，也能从B顺着单行道开回A。给你分享个高效的实现思路和代码：

核心校验逻辑 #

其实不用复杂的算法，两次遍历（DFS或BFS）就能搞定：

• 第一步：随便挑一个路口当起点，做一次深度/广度遍历，标记所有能开到的路口。如果有路口没被标记，那肯定不符合要求，直接返回不通过。
• 第二步：把所有单行道的方向反过来，再从同一个起点做一次遍历，标记所有能“到”的路口（这其实等价于原图里所有路口能开到起点）。要是这次还有没标记的，也不符合要求。
• 只有两次遍历都能覆盖所有路口，才能证明任意两个路口之间都能互相到达。

Python代码实现（邻接表输入） #

假设你的道路地图是用邻接表表示的——比如一个字典，键是路口编号，值是这个路口能直接开到的路口列表：

def is_road_network_valid(graph):
    if not graph:
        return True  # 空地图默认合理
    
    # 随便选一个起始路口
    start = next(iter(graph.keys()))
    
    # 第一次遍历：从start出发，标记所有可达路口
    visited = set()
    def dfs(node):
        visited.add(node)
        for neighbor in graph.get(node, []):
            if neighbor not in visited:
                dfs(neighbor)
    
    dfs(start)
    if len(visited) != len(graph):
        return False
    
    # 构建反向道路图（所有单行道掉头）
    reversed_graph = {node: [] for node in graph}
    for from_node in graph:
        for to_node in graph[from_node]:
            reversed_graph[to_node].append(from_node)
    
    # 第二次遍历：在反向图里从start出发，标记所有可达节点
    visited_rev = set()
    def rev_dfs(node):
        visited_rev.add(node)
        for neighbor in reversed_graph.get(node, []):
            if neighbor not in visited_rev:
                rev_dfs(neighbor)
    
    rev_dfs(start)
    return len(visited_rev) == len(graph)

# 测试用例
# 合理的道路网：三角单向循环
valid_network = {
    0: [1],
    1: [2],
    2: [0]
}
print(is_road_network_valid(valid_network))  # 输出True

# 不合理的道路网：单向链，最后一个路口开不回去
invalid_network = {
    0: [1],
    1: [2],
    2: []
}
print(is_road_network_valid(invalid_network))  # 输出False

额外提示 #

• 如果你的输入是邻接矩阵形式，只需要把邻接表的遍历逻辑改成矩阵索引判断就行，核心思路完全一样。
• 要是道路网特别大，递归DFS可能会栈溢出，换成BFS用队列实现就好，比如把dfs函数改成用while循环处理队列，效果是一样的。
• 这个方法的时间复杂度是O(V+E)，V是路口数，E是道路数，效率很高，完全能应付城市道路的规模。

内容的提问来源于stack exchange，提问作者Cyndi