是否有任何算法的實現，在Golang中具有自邊緣的有向多圖中查找所有周期？我發現約翰遜算法是有向圖的最佳解決方案，并且實現是在gonum中給出的，但它僅適用于有向圖（而不是多圖），并且不支持自邊緣（實際上gonum中的有向圖不支持自邊緣）。有沒有一個簡短/聰明的黑客，我可以在gonum中做約翰遜的工作與自我邊緣的定向多圖？還是在Golang中還有其他實現？可以做的一件事是在自邊緣之間創建一個虛擬節點，并在同一對節點之間的重復邊緣之間創建一個虛擬節點。這將刪除所有自體邊，圖形將是有向的，我可以在這里使用約翰遜的。但是有更好的方法嗎？
1 回答
四季花海
TA貢獻1811條經驗 獲得超5個贊
自邊緣 ：您只需要掃描圖形的每個節點并檢查是否存在自我邊緣。如果有 ：添加到循環列表
X -> X多圖：第一種算法將生成路徑作為頂點序列。當您有此列表時，請迭代從 到 的所有可能的邊緣，然后從 到 的所有可能的邊緣，依此類推...
X1 -> X2 -> X3 -> ...X1X2X2X3
“聰明”的黑客：從你的多圖中，創建一個新的圖，其中的邊緣也顯示為頂點：
GG2G
# if A and B are connected # create the following 3 vertices and
# by a single edge in G : # 2 edges in G2 :
A ---w--> B A -> w -> B
# if A and B are connected # create the following 4 vertices and
# by two edges in G : # 4 edges in G2 :
/--x--\ /-> x --\
A B A B
\--y--/ \-> y --/
# etc ...
然后在 上運行循環枚舉，并根據需要調整輸出。G2
- 1 回答
- 0 關注
- 139 瀏覽
添加回答
舉報
0/150
提交
取消