使用Boost圖來搜索DAG圖？

我需要通過DAG圖進行搜索，但是我不希望在看到所有指向它的定向鏈接的其他節點之前超越節點。使用Boost圖來搜索DAG圖？

是否有一個現有算法來處理這種特殊情況，深度優先搜索和呼吸優先搜索不適用於此遍歷順序。

即：

A -> B 
B -> C 
C -> D 
A -> C

我不想永遠到達d之前看過B和C.

來源

2009-10-07 Dan

唐不要把你的DAG圖表帶到ATM機上並使用你的PIN號碼，否則你可能會得到艾滋病病毒。 – chaos 2009-10-07 16:01:19

所以我最近的想法是在整個圖上做一個拓撲排序，每當添加或刪除邊時，存儲要爲每個節點遍歷的直接子節點的順序（這可能是一個棘手的算法寫）。

然後我做了修改的廣度優先搜索（如由混亂所建議的），並且在以下僞代碼BFS，修改線：

for each vertex v in Adj[u]

爲：

for each vertex v in OrderedAdj[u]

僞代碼：

BFS(G, s) 
    for each vertex u in V[G] 
    color[u] := WHITE 
    d[u] := infinity 
    p[u] := u 
    end for 
    color[s] := GRAY 
    d[s] := 0 
    ENQUEUE(Q, s) 
    while (Q != Ø) 
    u := DEQUEUE(Q) 
    for each vertex v in Adj[u] 
     if (color[v] = WHITE) 
     color[v] := GRAY 
     d[v] := d[u] + 1 
     p[v] := u 
     ENQUEUE(Q, v) 
     else 
     if (color[v] = GRAY) 
      ... 
     else 
      ... 
    end for 
    color[u] := BLACK 
    end while 
    return (d, p)

我相信這是實現這一目標的最佳方式，但確實涉及到我寫作o wf bfs遍歷算法，並存儲每個節點上的節點順序（我希望避免的內存開銷），並編寫我自己的dfs訪問者以查找順序並將其存儲在緩存階段的節點中。

我很驚訝，沒有執行該操作的現有方式，因爲在我看來，導航的DAG圖的相當常見的方法...

來源

2009-10-08 09:35:24 Dan

你不能做到這一點與普通的圖形遍歷算法，因爲你要求該算法神奇地具有圖形結構的知識，它不可能違背它自己的要求而不能遍歷。您將不得不使用兩遍方法首先構建向後樹，告訴您哪些節點已從其他節點連接，然後執行修改的廣度優先搜索，使用第一遍中的信息來適當延遲遍歷。我懷疑某些圖形結構可能會導致第二遍的死鎖。

來源

2009-10-07 16:07:22 chaos

那麼先做一個拓撲排序，然後在排序圖上進行深度優先搜索？

會這樣嗎？

來源

2009-10-07 16:10:24 Dan

我認爲這將不得不在排序圖上進行廣度優先搜索。 – divegeek 2009-10-07 17:35:35

任何DAG至少有一個葉節點。刪除任何葉節點節點和所有傳入弧會留下另一個DAG。遞歸地，這個較小的DAG還具有至少一個葉節點。通過以這種方式遞歸地移除所有節點，最終根節點成爲葉節點。

如果您現在反轉您刪除節點的順序，那麼您將擁有具有所需屬性的遍歷順序。通過最後訪問葉節點，您可以保證先看到所有父節點。

來源

2009-10-08 08:39:36 MSalters

謝謝，這被稱爲拓撲排序，並且在Boost中就像這樣實現:)現在，我將如何從這個有序的節點列表去搜索任何特定節點下游的節點（仍然使用這個順序），最好不寫我自己的遍歷算法？ – Dan 2009-10-08 09:18:50

你的意思是，當特定節點不是根節點時？看起來很簡單：對整個DAG進行拓撲排序，並拋出所有無法從您的特定節點到達的節點。剩下的節點是以特定節點爲根的子圖的遍歷順序。 – MSalters 2009-10-08 11:26:23

什麼你要找的是卡恩（ 1962）拓撲排序算法。這不是目前在基於DFS的BGL中實現的拓撲排序算法，它訪問所有頂點並以逆拓撲順序輸出結果，而是非常類似於BFS，並按照您在您的描述中描述的方式訪問頂點第一段。你將不得不自己編寫遍歷，但算法很簡單。

查看拓撲排序維基百科條目中列出的第一個算法：http://en.wikipedia.org/wiki/Topological_sorting。另請參閱Sedgewick「C語言中的算法」中的程序19.8。提示1：使用輔助數據結構來維護每個頂點的邊的數量，但實際上並不執行「從圖中刪除邊」部分。

提示2：有關工作GPLV3'ed例如，你可以看看卡恩的算法在我CoFlo控制流圖的生成和分析項目的實施，特別是文件topological_visit_kahn.h這裏：http://coflo.svn.sourceforge.net/viewvc/coflo/trunk/src/controlflowgraph/topological_visit_kahn.h?view=log

來源

2011-09-24 21:52:35

使用Boost圖來搜索DAG圖？

回答

相關問題