用于在图形或树中查找冗余边缘的算法

接下来，您需要定义“冗余边缘”的含义。在这种情况下，您从具有两条路径a-> c的图形开始：一个通过b和一个直接路径。从这我推断，“冗余”你的意思是这样的。让G = < V，E>是一个图，用V该组顶点和Ë⊆ V × V边的集合。它看起来像你正在定义所有边缘从v _我到v _j短于最长边作为“冗余”。所以最简单的事情就是使用深度优先搜索，列举路径，并且当您找到更长的新路径时，将其保存为最佳候选路线。

虽然我无法想象你想要什么。你能告诉？

来源

2009-02-04 06:53:58

-1

我认为这样做最简单的方法，其实想象它会怎样看在实际工作中，试想一下，如果你有缝，像

（A-> B）（B-> C）（A- > C），试想如果邻近图之间的距离是等于1，所以

（A-> B）= 1，（B-> C）= 1，（A-> C）= 2

所以你可以删除联合（A-> C）。

换句话说，最小化。

这只是我的想法，我会在开始时考虑它。网上有各种各样的文章和资料，你可以看看它们并且深入。

资源，这将帮助你：

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

来源

2009-02-04 07:00:00

我也有类似的问题，并最终解决这样说：

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

来源

2011-06-29 07:29:24 Iftah

用于在图形或树中查找冗余边缘的算法

回答

相关问题