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

您需要计算保持顶点可达性的最小图。

transitive reduction

有几种方法可以解决这个问题,但首先需要更精确地定义问题。首先,这里的图是非循环的和有方向的:这永远是真的吗?

接下来,您需要定义“冗余边”的含义。在本例中,您从一个具有两条路径a->c:一个通过b,一个直接。从这一点,我推断“多余”的意思是这样的。允许 v 和 E⊆ V×V 边的集合。看起来你在定义所有的边 v v 比最长边短的称为“冗余”。因此,最简单的方法是使用深度优先搜索,枚举路径,当您找到一个较长的新路径时,将其保存为最佳候选路径。

给定图中不包含“冗余边”的子图称为“A” spanning tree “那是一张图表。对于任何给定的图,多个生成树都是可能的。

所以,为了去除多余的边,你需要做的就是找到你的图的任何一个生成树。你可以使用任何 depth-first-search breadth-first-search 算法并继续搜索,直到您访问了图中的每个顶点。

因为@Craig提到的Wikipedia文章只给出了一个实现的成功案例,所以我用Java 8 streams发布了我的实现:

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());
                        }
                ));

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

(A->B)(B->C)(A->C),想象一下,如果近图之间的距离等于1,那么

换句话说,最小化。

这只是我的想法,我将如何考虑它在一开始。网上有各种各样的文章和资料来源,你可以查看它们并深入了解。

Algorithm for Removing Redundant Edges in the Dual Graph of a Non-Binary CSP

Graph Data Structure and Basic Graph Algorithms

Google Books, On finding minimal two connected Subgraphs

Graph Reduction

Redundant trees for preplanned recovery in arbitraryvertex-redundant or edge-redundant graphs

我有一个类似的问题,最终以这种方式解决:

我的数据结构是由 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)]