带环图中如何查询每个节点的所有可达连通节点（排除自环）

核心思路 #

要解决带环图遍历的无限递归问题，核心是在遍历过程中增加已访问节点标记，同时按需增加记忆化优化提升效率，具体逻辑如下：

• 首先将图结构转换为邻接表存储，即每个节点对应其直接指向的后继节点列表
• 对每个节点，使用BFS/DFS遍历其所有可达节点：
  • 遍历过程中维护已访问标记集合，已标记的节点不再重复处理，直接跳过，避免环导致的无限循环
  • 最终输出结果前排除节点自身，满足剔除自环关联的要求
• 可选优化：提前缓存已计算完成的节点的可达集合，后续遍历遇到该节点时直接合并缓存的集合，无需重复遍历其子节点，大幅提升大图计算效率

代码实现（Python示例） #

from collections import deque

def calc_all_reachable(adj):
    # 存储每个节点的可达集结果，避免重复计算
    reachable_cache = {}
    
    def bfs(start):
        if start in reachable_cache:
            return reachable_cache[start]
        visited = set()
        q = deque()
        # 先加入起始节点的所有直接后继
        for neighbor in adj[start]:
            if neighbor not in visited:
                visited.add(neighbor)
                q.append(neighbor)
        # 广度优先遍历
        while q:
            cur = q.popleft()
            # 如果当前节点已经算过可达集，直接合并
            if cur in reachable_cache:
                visited.update(reachable_cache[cur])
                continue
            # 否则遍历当前节点的后继
            for neighbor in adj[cur]:
                if neighbor not in visited:
                    visited.add(neighbor)
                    q.append(neighbor)
        # 剔除节点自身，满足排除自环关联的要求
        visited.discard(start)
        # 缓存结果
        reachable_cache[start] = visited
        return visited
    
    result = {}
    for node in adj:
        res = bfs(node)
        result[node] = res if res else None
    return result

# 示例邻接表
adj = {
    1: [3],
    2: [4],
    3: [2],
    4: [5, 3],
    5: []
}

# 计算并输出结果
res = calc_all_reachable(adj)
for node in sorted(res.keys()):
    if res[node] is None:
        print(f"{node} -> NULL")
    else:
        output = ", ".join(map(str, sorted(res[node])))
        print(f"{node} -> {{{output}}}")

输出结果 #

运行上述代码将得到和要求完全匹配的输出：

1 -> {2, 3, 4, 5}
2 -> {3, 4, 5}
3 -> {2, 4, 5}
4 -> {2, 3, 5}
5 -> NULL

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