graph-algorithm

-1熱度

1回答

鑑於無向，加權圖，我需要找到從頂點A到頂點B的路徑與n條邊的最小總重量。我發現關於「最寬的路徑問題」維基百科文章和我的問題看起來相似，但我怎麼能延長該算法幾個邊？有另一種算法，有人可以建議？

0熱度

4回答

#include <iostream> #include <vector> using namespace std; void addEdge(vector<vector<int> > adj, int, int); void print_graph(vector<vector<int> > adj); int main() { vector<vector<int> >

1熱度

1回答

2可滿足性強連接組件拓撲排序

我正在解決SCCs的兩個可滿足性問題，並且有關於拓撲排序的問題。我基於此的算法是以逆向拓撲順序處理SCC，這在所有連接時都很好。我的算法是打破的情況下是這樣的： 3 3 -2 3 1 -2 -2 -1 這使得看起來像這樣的圖表：有兩個來源，並在此圖中，兩個水槽，並根據你開始有多個拓撲排序，所以有兩個可能的最終節點。沒有周期，所以每個節點都是SCC。從源到匯有多條路徑，所以當我做逆向拓撲

1熱度

1回答

查找具有給定數量的節點和邊的圖的算法

我有許多節點，每個節點都有多個邊。例如節點A有3條邊，B有2條，C有2條，D有1條。我正在尋找一種算法，以找到兩個節點之間沒有多條邊的可能無向圖。對於這個簡單的例子的一種可能的解決辦法是： A /|\ /| \ B--C D 所以A與其他3個節點，因爲它有3個連接，B連接到A和C連接，d與A.連接所有的邊緣所有節點必須滿足。又如： A（3），B（3），C（2），d（1），

2熱度

2回答

平面性測試，除了邊緣類型的例外

我想了解平面性檢查算法（如LR Planarity，PC樹，PQ樹等）是否可以增強，使得一些邊緣被允許交叉取決於他們的類型。我有3種不同類型的邊的圖：A，B，C類型A的邊緣不能跨越任何其它邊緣。 B型的邊緣可以與C型的邊緣交叉，反之亦然。我已經看過簡單的LR平面度測試，但無法成功實現此功能。是否有可能採取現有的算法並用這些規則進行調整，或者是否已有算法支持？

0熱度

1回答

使用動態規劃尋找最小邊緣覆蓋的有效方法

給定一個無自循環和平行邊的無向圖。我的目標是找到minimum edge cover。我開始知道使用bitmask DP可以有效地完成。我嘗試了很多，但無法弄清楚如何定義state of DP。請幫助決定DP狀態。

3熱度

1回答

爲什麼Dijkstra的算法必須在每一輪中提取min？

考慮圖形是有效的用於施加Dijkstra算法即沒有負邊緣的權重。我很難說服自己，只有選擇每一輪中的最小距離節點進行提取時，Dijkstra算法纔有效。什麼構成一個證明，除了最小距離節點之外的任何東西都會導致Dijkstra算法的失敗？我在尋找一個很好的論點，但支持的例子是受歡迎的。

0熱度

1回答

迭代深化與週期實行A *圖形

我一直在努力實現迭代深化A *算法，在那裏我有一張圖表。我已經看過了維基百科的僞碼週期下面發現： node current node g the cost to reach current node f estimated cost of the cheapest path (root..node..goal) h(node) estimated cost of t

1熱度

3回答

如何高效地從特定節點產生二叉樹？

不知道這是一個正確的地方要問這樣的問題。但我只是將它張貼反正... 假設我有一個二叉樹，其中某些節點標記爲red： n1 /\ red n2 /\ \ n3 n4 red /\ n5 n6 所以我想要做的，是每個red節點，產生樹成兩棵新的樹，並把每個孩子成一棵樹。因此，對於上述情況下，它會成爲四棵樹是這樣的： n1 /\ n3

1熱度

1回答

計算有向圖的平方的算法（以鄰接表的形式表示）

我正在構建計算有向圖的G^2的算法，該有向圖是一個鄰接表的形式，其中G^2 = （V，E'），其中如果在G中u和v之間存在長度爲2的路徑，那麼E'被定義爲（u，v）∈E'。我非常瞭解這個問題並找到了一個我假設的算法是正確的，但是我的算法的運行時間是O（VE^2），其中V是頂點的數量，E是圖的邊數。我想知道如何在O（VE）時間內做到這一點，以提高效率？這裏的算法，我想出了：在鄰居頂點頂點中鄰居