最小生成樹問題是取一個連接的加權圖，並在保持圖形連通的情況下找到其邊的子集具有最低的總權重（並因此導致非循環圖）。這個最小生成樹算法是否正確？
我正在考慮的算法是：
這個版本的動力是一個限制在沒有任何迭代構造的「規則滿意度」的環境。它也可能適用於瘋狂並行的硬件（即一個系統，在這個系統中，你期望有幾倍的並行度，然後是週期）。
編輯：
以上是在無狀態莊園完成（未在任何週期最大邊緣選擇了所有邊緣/保持/忽略，所有其他被移除）。
如果兩個週期重疊會發生什麼？哪一個最長邊被首先移除？這兩個週期之間是否共享每個週期的最長邊緣有關係嗎？
例如：
V = { a, b, c, d }
E = { (a,b,1), (b,c,2), (c,a,4), (b,d,9), (d,a,3) }
有一個一個 - 「乙 - 」ç - >一個週期，和一個 - 「乙 - > d - >一
你的算法是不是很明確規定。如果你有一個完整的圖，你的算法似乎需要在第一步中除去兩個最小元素。此外，列出全部圖中的週期可能需要指數時間。
精化：
在具有n個節點的曲線圖，每對節點之間的邊緣，還有，如果我有我的數學右，正/大小爲k的週期，！（2K（NK）！）如果您要統計一個週期爲k的節點和k的一些子圖，每個節點有度邊2.
@ shrughes.blogspot.com：
我不知道如何移除所有而是兩個 - 我我一直在勾畫出算法的各種運行過程，並假設並行運行可能會多次刪除邊緣，我無法找到沒有生成樹的情況。不知道它是否微乎其微。
@Tynan該系統可以描述（有點過於簡化）作爲描述分類的規則系統。 「事物屬於A類，如果它們在B中但不在C中」，「連接到Z中的節點的節點也在Z中」，「M中的每個類別連接到節點N並具有'子類別'，也在M連接到N「的每個節點。這比這稍微複雜一些。 （我已經證明，通過創建不穩定的規則，您可以對一個車牀進行建模，但這並不重要）。它不能明確定義迭代或遞歸，但可以使用第二個和第三個規則的遞歸數據進行操作。
@Marcin，假設有無限數量的處理器。這是微不足道的，表明該程序可以在O（n^2）中運行，因爲n是最長的循環。有了更好的數據結構，這可以減少到O（n * O（設置查找函數）），我可以設想硬件（量子計算機？）可以在恆定時間內評估所有周期。給MST問題提供O（1）解決方案。
Reverse-delete algorithm似乎提供了正確性的部分證明（即所提出的算法不會生成非最小生成樹），這是通過論證mt算法將刪除反向刪除算法將會的每條邊而得出的。不過，我不知道如何顯示我的算法不會刪除更多的算法。
Hhmm ....
好的，這是一個嘗試完成正確性的證明。通過類比反向刪除算法，我們知道有足夠的邊將被刪除。剩下的就是證明不會去除很多邊緣。
移除到許多邊可以描述爲去除圖節點的二進制分區的邊之間的所有邊。然而，只有一個週期中的邊緣被刪除，因此，對於要移除的分區之間的所有邊緣，需要有一個返回路徑來完成周期。如果我們只考慮分區之間的邊緣，那麼該算法至多可以去除每對邊中較大的一個，這永遠不會移除最小的橋接邊。因此，對於任何任意的二進制分區，算法不能切斷邊之間的所有鏈路。
剩下的是證明這擴展到了> 2分區。
其中一個重點是在系統中實現MST的概念，如'first/second'和'before/after'不存在。 – BCS 2011-02-08 17:04:59