查找有向加權圖的所有生成樹

Question

到目前爲止我找到this紙。它過時了嗎？有更快更好的實現嗎？

順便說一下，維基百科說，在無向圖中可以有n^n-2棵生成樹。有向圖中有多少棵生成樹？

Answer 1

如果你使用你所提到的紙張術語和定義有向圖的樹植根於頂點爲r的生成樹，具有從r的唯一路徑到任何其他頂點，則：

很明顯，最壞的情況下向圖時具有最多的生成樹是完整的圖形（對於任何對都有a-> b和b-> a的邊）。 如果我們「忘記」方向，我們將得到n^{n-2}個生成樹，就像無向圖一樣。對於這些生成樹中的任何一個，我們都有n個選項來選擇一個根，並且此選項定義了唯一定義我們需要使用的邊的方向。不難看出，我們獲得的所有樹木都是跨越式的，獨一無二的，沒有其他選擇。所以我們得到n^{n-1}個生成樹。嚴格的證明需要時間，我希望簡單的解釋就足夠了。

所以這個任務將取決於最壞情況下頂點計數的指數時間。考慮到輸出的大小（所有生成樹），我得出結論，對於任意圖，算法不能更快更好地顯着。我認爲你需要以某種方式重新構建你原來的問題，不要處理所有的生成樹，並且可能只是按照某些標準進行搜索。

Answer 2

只無向圖....

N 1，N-2跨越發辮是可能的唯一完整的圖形....找到任何圖形U可以應用此方法的生成樹總數.. ...

1. 找到圖的鄰接矩陣。
2. 如果列值由「i」和行表項由「J」表示隨後...
3. 如果我= j的...則該值將是頂點
度
4. 假設，有一個在頂點v1和v2之間的單個邊緣，則矩陣條目的值將是-1 ...... 7，如果存在兩條邊，那麼它將是-2 ... &等等......
5. 構建鄰接矩陣....排除任何行和列...即第N行和第N列....
6. 答案將是生成樹的總數。