求无向连通图中输入边对应节点集的高效算法

给定含主节点（记为M）的无向连通图，需实现满足以下要求的高效算法：

• 输入为一组边（示例中以粗线标记）
• 输出为每个输入边对应的节点集合
• 若节点到主节点的某条路径包含该输入边，则该节点属于该边的结果集合

示例说明 #

示例1 #

预期输出：{2: [B,C,D,E,F,G,H], 4: [D,E,F]}
解释：从B往右的所有节点到M的路径必须经过边2；A、B、C到M的路径均不含边4，故不属于其结果集。

示例2 #

预期输出：{1: [A,B,C,D,E,F], 2: [A,B,C,D,E,F], 5: [D,E,F]}
解释：A、B到M的路径可经过C，因此同时属于边1和2的结果集；边5的结果集不含环内节点。

示例3（针对反例更新） #

预期输出：{1: [A,B,C,D,E,F], 5: [D,E,F]}
解释：A到F的所有节点均存在经过边1到M的路径；A、B、C无法通过含边5的路径到达M（ACDFECBM是迹而非路径）。

朴素解决方案 #

已实现的朴素算法（伪代码，实际基于Neo4j Traversal框架）可正确运行，但性能低下：

Map<Edge,Set<Node>> execute(Set<Edge> input) {
    Map<Edge,Set<Node>> result = new HashMap<>();
    Node m = graph.getMainNode();
    for (Node n : graph.getAllNodes()) {
        for (Path p : depthFirstSearchAllUniquePathsFrom(n, m)) {
            for (Edge e : p.getEdges().filter(input::contains).toList()) {
                result.computeIfAbsent(e, k -> new HashSet<>()).add(n);
            }
        }
    }
    return result;
}

存在的问题 #

该算法速度极慢，在含758个节点、133条输入边且多环的图上遍历耗时20分钟。调试发现大量重复路径，depthFirstSearchAllUniquePathsFrom采用Uniqueness.NODE_PATH遍历，时间开销极高。

需求 #

寻求可充分利用遍历信息的高效算法（类似Floyd-Warshall比多次Dijkstra更高效的思路），无需枚举路径（路径枚举复杂度为指数/阶乘阶），需判断该问题是否为NP难问题，或是否存在简便解法。

内容的提问来源于stack exchange，提问作者Tomáš Záluský