directed-acyclic-graphs

-3熱度

1回答

給定有向無環圖G = (V,E)和兩個不同的頂點s和t。邊和頂點都被賦予了實值權重。路徑的權重定義爲路徑上所有邊和頂點的總和。問題是要找到從s到t的最短加權簡單路徑。（a）設計一個動態規劃算法並簡要描述它。（b）設計一個貪婪算法並簡要描述它。（c）儘可能提供一個算法的上限和下限。我該怎麼做？ Dijkstra能用嗎？

0熱度

1回答

Varnish支持依賴關係圖緩存失效嗎？

考慮緩存page（包含blogsposts，其中又包含comments）的（假設的）情況。現在更改1 comment。這意味着blogpost的緩存必須失效，並且（可傳遞地）page的緩存必須失效。換句話說：項與海誓山盟在可以被描述爲依賴圖（這是一個Directed Acyclic Graph）不光油支持這種類型的高速緩存無效的方法嗎？如果不是，部分涵蓋這個的其他實施，研究等？

2熱度

2回答

Prolog，確定圖是否是非循環的

我需要定義一個謂詞acyclic/1，它將圖作爲輸入並確定該圖是否是非循環的。因此，從我的理解 graph1(a,b). graph1(b,c). graph1(c,a). 將不會返回和 graph2(a,b). graph2(b,c). 將返回是我做了一個斷言，以確定是否在圖2個節點相連接，如果是的話，他們將返回是。 isConnected(X,Y) :- a(X,Z), isC

0熱度

1回答

將圖形中的路徑編碼爲字符串？

假設我有一個DAG，而不是使用圖形db，路徑被編碼爲{id:"node3", path:"node0|node1|node2"}以表示node3可以通過node2然後node1達到node0。如果讀取不頻繁，將路徑編碼爲字符串會不會是一個好主意？路徑通常每個不包含超過50個節點。感謝

0熱度

1回答

具有更新的節點加權DAG和最長路徑

假設您有一組可以並行完成的作業。每個工作都有時間要求（第i個工作的時間要求是t_i）。還有一些依賴關係，他們中的第一個說你必須在工作v_i之前做u_i工作。你必須最小化所需的總時間。這很容易通過將這些關係轉換爲有向無環圖，然後使用它來確定哪些要並行執行。如果我不清楚，這裏是一個例子。假設你有5個工作時間要求爲2,9,3,12,5，你必須在5之前4，5之前3，之前1和之前1之前做3。然後你能做的

0熱度

1回答

序言圖非循環

我想寫一個謂詞，寫出所有的方式從一個節點到另一個非循環圖。如果我例如有這些節點/邊緣。 node(x,y). node(x,z). node(y,z). 然後，我已經試過類似： predicate(X,Y):- node(X,Y), ... ，但不知何故，我需要做的這個遞歸，我需要幫助。任何人有任何想法？謝謝

2熱度

1回答

python如何爲GraphViz寫一個點文件，要求將某些邊緣塗成紅色？

我使用Python代碼（與Python嵌套類型的字典）寫了一個DOT文件GraphViz的畫我向邊加權圖，由於DAWG的建議... nestedg={1: {2: 3, 3: 8, 5: -4}, 2: {4: 1, 5: 7}, 3: {2: 0.09}, 4: {1: 2, 3: -5}, 5: {4: 6}} with open('/tmp/gra

3熱度

1回答

如何找到有向無環圖的最大獨立集？

假設我們有一個類似於鏈表（或有向無環圖）的圖。一個獨立的集合由不與集合中的任何其他節點共享邊的節點組成。如果每個節點都是加權的，我們如何計算獨立節點集的最大可能值？我知道我們必須使用動態編程，所以我有一點線索，但我希望有人能解釋他們將如何處理它。謝謝！

3熱度

2回答

Dummies的迭代/動態拓撲排序

我目前正在C++中實現一個動態DAG圖形 - 它將通過用戶界面顯示給用戶，插入/移除節點/邊界將是常用操作。圖的大小可能範圍從真正的小規模到大規模 - 我旨在支持數百萬個節點。因此，我正在尋找一種最佳的數據結構，它不會佔用太多的內存空間，但也可以通過在拓撲排序的節點上進行快速多線程迭代來快速插入/刪除（所以多個節點可以並行執行）。我還沒有做過任何分析，看看是否每次修改完成後重新計算拓撲排序的完

2熱度

1回答

如何使用拓撲排序在有向圖中找到一個循環？

我在程序中實現這個僞代碼，以檢查是否有向圖是非循環： L ← Empty list that will contain the sorted elements S ← Set of all nodes with no incoming edges while S is non-empty do remove a node n from S add n to tail of