在图或树中寻找冗余边的算法

Question

在图或树中寻找冗余边的算法

algorithmlanguage-agnostictreegraph-theory

26

在图中寻找冗余边的算法是否已经被确立？

例如，我想找到a->d和a->e是冗余的，然后将它们去掉，像这样:

=>

编辑：Strilanc很好心地替我思考。 "冗余"这个词太绝对了，在上面的例子中，既不认为a->b也不认为a->c是冗余的，但a->d是。

- Ryan Fox

我们可以考虑将B--->C视为冗余吗？ - Zach Scrivena

"Redundant" 的意思是 "如果从 X 到 Y 存在非边路径，则边 X->Y 是冗余的"，还是你只是在寻找一棵生成树？ - David Lehavi

@Zach：不，B->C 不是冗余的，因为如果它被移除，结果图中就没有从 B 到 C 的路径了。 - ShreevatsaR

很抱歉让你的评论变得不正确，但我已经更新了更好的示例。 - Ryan Fox

这很奇怪。用来描述问题的图片是链接解决方案（维基百科）中使用的图片。这里发生了什么？ - ABu

已经过去10年了，所以我的记忆有些模糊，但我认为当我找到维基百科上的那张图片时，我把它替换成了它，因为它比我想出来的那张好多了。 - Ryan Fox

5个回答

2

@Craig提到的维基百科文章只提供了一个实现，所以我在这里使用Java 8流发布了我的实现：

Original Answer翻译成“最初的回答”

Map<String, Set<String>> reduction = usages.entrySet().stream()
                .collect(toMap(
                        Entry::getKey,
                        (Entry<String, Set<String>> entry) -> {
                            String start = entry.getKey();
                            Set<String> neighbours = entry.getValue();
                            Set<String> visited = new HashSet<>();
                            Queue<String> queue = new LinkedList<>(neighbours);

                            while (!queue.isEmpty()) {
                                String node = queue.remove();
                                usages.getOrDefault(node, emptySet()).forEach(next -> {
                                    if (next.equals(start)) {
                                        throw new RuntimeException("Cycle detected!");
                                    }
                                    if (visited.add(next)) {
                                        queue.add(next);
                                    }
                                });
                            }

                            return neighbours.stream()
                                    .filter(s -> !visited.contains(s))
                                    .collect(toSet());
                        }
                ));

- FLUXparticle

0

我曾经遇到过类似的问题，最终是这样解决的：

我的数据结构由一个名为dependends的字典组成，从节点ID到依赖于它的节点列表（即DAG中的后继节点）。请注意，它仅适用于DAG - 即有向无环图。

我没有计算它的确切复杂度，但它可以在瞬间处理数千个节点的图形。

_transitive_closure_cache = {}
def transitive_closure(self, node_id):
    """returns a set of all the nodes (ids) reachable from given node(_id)"""
    global _transitive_closure_cache
    if node_id in _transitive_closure_cache:
        return _transitive_closure_cache[node_id]
    c = set(d.id for d in dependents[node_id])
    for d in dependents[node_id]:
        c.update(transitive_closure(d.id))  # for the non-pythonists - update is update self to Union result
    _transitive_closure_cache[node_id] = c
    return c

def can_reduce(self, source_id, dest_id):
    """returns True if the edge (source_id, dest_id) is redundant (can reach from source_id to dest_id without it)"""
    for d in dependents[source_id]:
        if d.id == dest_id:
            continue
        if dest_id in transitive_closure(d.id):
            return True # the dest node can be reached in a less direct path, then this link is redundant
    return False

# Reduce redundant edges:
for node in nodes:      
    dependents[node.id] = [d for d in dependents[node.id] if not can_reduce(node.id, d.id)]

- Iftah

我只是想评论前面的答案 - 减少冗余边并不等同于生成树，甚至不等同于最小生成树。如果从A到B的某条路径比另一条路径更长，并不能说明哪些边（如果有的话）是冗余的。在他上面的例子中，你可以构造一棵没有a->b边的生成树，但它并不是多余的。 - Iftah

0

有几种方法可以解决这个问题，但首先你需要更精确地定义问题。首先，你所拥有的图是无环有向图：这种情况是否总是成立？

接下来，你需要定义“冗余边”的含义。在这种情况下，你从一个具有两条路径a->c的图开始：一条通过b，另一条直接到达。由此我推断出，你所说的“冗余”是指这样的情况。让G=< V，E >成为一个图，其中V是顶点集合，E ⊆ V×V是边集。看起来你正在定义所有从v_i到v_j的边都比最长边短，因此最简单的方法是使用深度优先搜索，枚举路径，并在找到新路径时将其保存为最佳候选。

不过我无法想象你想要它用于什么。你能告诉我吗？

- Charlie Martin

0

我认为最简单的方法是，想象一下在实际工作中它会是什么样子，想象一下如果你有关节，比如

(A->B)(B->C)(A->C)，想象一下接近图形之间的距离相等，所以

(A->B) = 1，(B->C) = 1，(A->C) = 2。

所以你可以删除(A->C)这个关节。

换句话说，就是最小化。

这只是我开始思考时的想法。网络上有各种文章和资源，你可以查看并深入了解。

以下是可以帮助你的资源：

用于删除非二元CSP的双重图中冗余边缘的算法

图形数据结构和基本图形算法