18
是否存在用於在圖形中查找冗餘邊緣的已建立算法？用於在圖形或樹中查找冗餘邊緣的算法
例如，我想找到A-> d和A->電子是多餘的，然後擺脫他們，就像這樣：
=>
編輯： Strilanc很高興爲我閱讀我的想法。 「冗餘」太強大了，因爲在上面的例子中，a-> b或a-> c都被認爲是多餘的，但a-> d是。
A
回答
24
您想要計算保持頂點可達性的最小圖。
這被稱爲圖的transitive reduction。維基百科的文章應該讓你開始走向正確的道路。
1
不包含「冗餘邊」的給定圖的子圖稱爲該圖的'spanning tree'。對於任何給定的圖，可能有多個生成樹。
因此，爲了擺脫冗餘邊緣，您只需要找到圖形的任何一個生成樹。您可以使用任何depth-first-search或breadth-first-search算法，並繼續搜索直到您訪問了圖中的每個頂點。
+0
現在已經很晚了，但是他真的描述了一棵生成樹嗎？ – 2009-02-04 06:56:35
+0
是的。他想要一個包含原始圖的所有頂點的子圖，只有一種方法可以從一個頂點到達另一個頂點。這正是一棵生成樹。 – 2009-02-04 07:04:00
1
1
幾種方法來攻擊這一點，但首先你要需要多一點的精確定義問題。首先，你在這裏的圖是非循環的並且是直接的：這總是會是真的嗎？
接下來，您需要定義「冗餘邊緣」的含義。在這種情況下，您從具有兩條路徑a-> c的圖形開始：一個通過b和一個直接路徑。從這我推斷，「冗餘」你的意思是這樣的。讓G = < V，E>是一個圖，用V該組頂點和Ë⊆ V × V邊的集合。它看起來像你正在定義所有邊緣從v 我到v j短於最長邊作爲「冗餘」。所以最簡單的事情就是使用深度優先搜索，列舉路徑，並且當您找到更長的新路徑時，將其保存爲最佳候選路線。
雖然我無法想象你想要什麼。你能告訴？
-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
Redundant trees for preplanned recovery in arbitraryvertex-redundant or edge-redundant graphs
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)]
我們可以改爲考慮B ---> C是多餘的嗎？ – 2009-02-04 07:52:32
冗餘是否意味着「如果存在從X到Y的非邊緣路徑，則邊X→Y是多餘的」或者您只是在尋找生成樹？ – 2009-02-04 08:24:16
@Zach：不，B-> C不是多餘的，因爲如果它被移除，從B到C的結果圖中沒有路徑。 – ShreevatsaR 2009-02-04 14:52:40