directed-acyclic-graphs

0熱度

1回答

所以基本上，我有一個n乘m的浮點值數組，我試圖找到任何第1行值和第m行值之間的最短路徑。圖中的節點(i, j)對於任何不處於邊緣(0 < i < n-1)且不在最後一行(j < m-1)的節點都有子節點{(i, j+1), (i-1, j+1), i+1, j+1)}。我正在尋找一種算法來及時解決這個特定的問題。我目前的思路圍繞A *搜索展開，但讓我知道您的想法。

2熱度

1回答

DAG圖和拓撲排序混淆基本面

我正在閱讀定向非循環圖我不明白拓撲秩序的想法通過relabeling。我對拓撲秩序的理解一般是我們找到頂點的順序，以便我們從沒有輸入邊的那個移動到路徑上的下一個，等等，直到我們完成了頂點的所有頂點DAG。但我不明白重貼標籤有何幫助。我的意思是重新標記頂點的意義是什麼？我們不是真的以這種方式破壞圖表嗎？任何人都可以請簡單解釋一下它的應用程序的例子嗎？

7熱度

1回答

這個數據結構有形式嗎？

我正在爲我正在使用的數據結構尋找數學形式，以便我可以追蹤相關定理和算法。假設你有以下幾點：有向議題的無環圖。在每個主題處，主題，一組文檔中的項目和一組組中的項目之間存在一個或多個關係。這些組可能是一個簡單的集合，或者它們最終可能是一個DAG。它們用於管理文檔與主題關聯的可見性。只是最近我碰到過hypergraphs，這看起來很相關，但太籠統了。這種數據結構是否有形式化？如果沒有，可以用數

14熱度

3回答

Clojure DAG（貝葉斯網絡）

我想建立一個clojure貝葉斯網絡，因爲我還沒有找到任何類似的項目。我已經研究了很多BN的理論，但我仍然看不到如何實現網絡（我不是什麼人稱任何東西的「大師」，但特別是不能用於函數式編程）。我知道一個BN不過是一個DAG和一個很多的概率表（每個節點一個），但現在我沒有粘合劑如何實現DAG。我的第一個想法是一個巨大的集合（DAG）和一些小地圖（DAG的節點），每個地圖應該有一個名稱（可能是一個鍵

3熱度

1回答

評估表達式樹

Skiena的書上算法包含了以下問題： 1）評估爲二叉樹O（n）的時間定表達式，給出n個節點。 2）在DAG中給定n個節點和m個邊緣的情況下，評估在O（n + m）時間中作爲DAG給出的表達式。我能想到的第一個問題的方式： evaluate(node) { if(node has children){ left_val = evaluate(node->left);

3熱度

2回答

用於圖形的C庫

用於圖論的操作有一個很好的C庫嗎？我特別需要計算有向圖的strongly connected components。我已經Ruby實現Tarjan's algorithm如下： def strongly_connected_components graph @index, @stack, @indice, @lowlink, @scc = 0, [], {}, {}, []

1熱度

1回答

在有向非循環圖中尋找最長路徑

我需要從一組有向無環圖的節點0中找到最長的路徑。我正在使用維基百科的Longest Path Problem algorithm。我已經有了適用於大多數圖的算法，但對於其他圖不能給出正確的結果。該算法是： private static int DAGLongestPath(Graph G) { int n = G.order(); int[] topOrder = new int[n]; t

4熱度

3回答

如何調用DAG拓撲重構？

我很長一段時間對直接非循環圖（DAG）感興趣，並且在閱讀維基百科的拓撲排序之後，我沒有發現任何涉及層編號爲（儘管層被廣泛提及用於繪圖）的方法的特別提及。通過這種方法，圖形在技術上沒有進行拓撲排序，但知道每個節點都包含層（層）的正確數字，我們總是可以分辨出特定節點是否比其他拓撲更「大」。另一方面，只要我們沒有一個有序的列表，我們不能枚舉拓撲結構中的節點（雖然這可以通過最終的傳統排序來比較節點的層次）

1熱度

1回答

以下步驟在Trie中構建DAWG結果。爲什麼？

我試圖實現一組函數，直接在線性時間內創建一個DAWG，用於編寫個人項目的某些搜索功能。我讀this paper這恰好詳述了DAWG背後的想法，甚至在線性時間內爲其構建提供了僞代碼！但是，遵循僞代碼似乎會產生（在我的眼中）類似於trie的結構。具體而言，後綴似乎並沒有明確共享（實際上通過圖中的邊連接）。相反，它們由後綴指針表示，它們並不真正影響圖形的實際遍歷。例如，看看這個圖片的DAWG的在集{

5熱度

1回答

DAG中可以有多少條邊？

在有n個頂點的有向無環圖中，有向邊的最大可能數是多少？