如何有效地從圖形生成所有可能的生成樹

首先請注意，這個問題是不是詢問約MST，相反，只是all possible spanning trees。如何有效地從圖形生成所有可能的生成樹

所以這是不一樣finding all minimal spanning trees或All minimum spanning trees implementation

我只需要生成從圖中所有可能的spanning trees。

我覺得蠻力的方法是直接：

假設我們有V節點和E邊緣。

獲取圖表
的所有邊緣獲取的V-1出E邊緣的所有可能組合。
過濾掉non-spanning-tree出組合（一個生成樹，一組V-1邊緣內的所有節點都恰好出現一次）

但我認爲面對大圖時實在是太慢了。

我們有更好的方法嗎？

來源

2014-03-02 Jackson Tale

其實你鏈接到的算法將爲你工作後，你設置所有的邊緣權重相同的值。權重的最明顯選擇是1或0，但它是完全不相關的（除了溢出問題，如果有的話）。 –

@ G.Bach您能否將您的評論轉換爲答案？ –

將所有邊的權重設置爲相同的值，然後使用算法查找所有最小生成樹。由於所有生成樹都具有邊緣並且所有邊緣權重相等，因此所有生成樹都將是最小生成樹。

來源

2014-03-02 15:21:35

我想這是一個正確的答案，但它回想起[關於數學家開水的笑話]（http://www-users.cs.york.ac.uk/susan/joke/3.htm#boil ），因爲我知道每個MST枚舉算法枚舉安全邊的子圖中的所有生成樹。 –

@DavidEisenstat我從來沒有看過枚舉MST的任何算法，所以只有將它作爲黑盒子，顯而易見的方法就是我的答案。不過，我喜歡那個笑話。不知道它是取笑工程師還是數學家，或者兩者兼而有之。編輯：感謝那個網站，有一段時間沒有這樣笑過。 –

@DavidEisenstat你有什麼更好的主意嗎？ –

我對這個問題感興趣，還沒有找到真正滿意的答案。但是，我發現了許多參考文獻：Knuth在TAOCP第4卷第4分冊中的Knuth算法S和S'，paper by Sorensen and Janssens和GRAYSPAN,SPSPAN和GRAYSPSPAN。這太糟糕了，他們都不是在我可以使用的語言實現...我想我將不得不花費一些時間編碼這些...

來源

2015-08-25 04:14:34

如何有效地從圖形生成所有可能的生成樹

回答

相關問題