6
我不想找到所有最小生成樹，但我想知道有多少人在那裏，這裏是我所考慮的方法：如何查找圖中最小生成樹的總數？
- 採用古板的或者Kruskal算法和查找一個最小生成樹然後找到所有生成樹的權重，並在運行計數器等於最小生成樹的權重時增加運行計數器。
我找不到任何方法來發現所有的生成樹，也生成樹的數量可能是非常大的權重，因此這種方法可能不適合的問題。 由於最小生成樹的數量是指數，所以數它們不會是一個好主意。
- 所有的權重將是積極的。
- 我們還可以假設，沒有重將在圖形顯示的三倍以上。
- 頂點的數量將小於或等於40,000。
- 邊數將小於或等於100,000。
圖中只有一個最小生成樹，其頂點權重不同。我認爲找到最小生成樹數的最好方法必須是使用這個屬性的東西。
編輯：
我找到了解決這個問題，但我不知道，爲什麼它的工作原理。任何人都可以請解釋它。
解決方案：找到最小生成樹的長度的問題是相當知名;尋找最小生成樹的兩個最簡單的算法是Prim算法和Kruskal算法。在這兩個中，Kruskal的算法按照權重的升序來處理邊緣。然而，克魯斯卡爾算法需要考慮的一個重要關鍵點是：當考慮按權重排序的邊緣列表時，邊緣可以被貪婪地添加到生成樹中（只要它們不連接已經以某種方式連接的兩個頂點）。
現在考慮使用Kruskal算法部分形成生成樹。我們插入了一些長度小於N的邊，現在必須選擇長度爲N的多個邊。算法規定，如果可能，我們必須在長度大於N的任何邊之前插入這些邊。但是，我們可以以我們想要的任何順序插入這些邊緣。另請注意，無論我們插入哪條邊，它都不會改變圖的連通性。 （讓我們考慮兩個可能的圖，一個從頂點A到頂點B有一個邊，另一個沒有，第二個圖必須有A和B作爲同一連通分量的一部分;否則從A到B的邊將被插入一點）
這兩個事實一起意味着我們的答案將是使用Kruskal算法插入長度爲K（對於K的每個可能值）的邊的數量的乘積。由於任意長度的邊至多有三個邊，所以不同的情況可以是強制性的，並且可以在每一步之後確定連接的部件，正如他們通常那樣。
我試圖解決的問題具有高達100,000的邊緣。所以從每個邊緣運行prim算法將需要很長時間。 – 2147483647
您可以通過檢查是否有任何中間圖是您已經作爲中間圖遇到的圖來加速它。任何這樣的圖形肯定會產生我們已有的最小生成樹。儘管這會讓你記憶。無論如何，它將保持緩慢。 – bowmore
您可以同時爲每個起始邊緣運行算法：首先製作Prim算法中第一步結果的所有樹木的森林。 （從40k頂點產生abt.2萬棵樹）然後在該森林中的每棵樹上執行該算法的下一步，並創建一個包含具有兩條邊的樹的新森林（可能刪除更多副本）。每個步驟都會繼續消除重複項，並且該結構還可以輕鬆地處理多種可能性，作爲下一步將所有可能性添加到下一代森林 – bowmore