minimum-spanning-tree

1熱度

1回答

我想知道從這個圖中的Prim算法的頂點順序：我的回答是{a,c,b,e,f,g,d}，但也有人說{a,c,b,e,d,f,g}或{a,c,d,e,b,f,g}。哪個答案正確？

0熱度

1回答

我們都知道存在諸如kruskal's和prim的MST算法的算法來查找連通圖的MST（最小生成樹）。我知道的另一種方法是從圖中的每個循環中刪除具有最大值的邊緣，直到沒有更多循環。結果圖將是MST。我不確定的問題是，如果連接圖具有不同的權重，那麼圖中每個週期的最小邊將包含在圖的每個MST中？我們能夠證明/反駁這個嗎？

0熱度

1回答

使用鄰接表來表示最小生成樹

我一直在試圖解決類的問題。問題是：給定一個無向圖摹，發現摹內的最小生成樹。爲了通過這個問題，我的函數必須採取，並返回，一鄰接表。但是，我不確定如何去將輸入和輸出表示爲鄰接列表。 from collections import defaultdict class Graph: def __init__(self,vertices): self.V= vertices

0熱度

1回答

如何找到路徑的最大邊將所有對MST

的頂點作爲我們假設我們有一個已知的最小生成樹。我們的任務是找出每對頂點之間存在路徑上的最大優勢。舉個例子，我們有以下的最小生成樹： 1---10---2 \ 5\ \ 4---4---3 頂點1和2之間，我們與成本10 頂點1和3之間的邊緣，我們具有成本5. 頂點3和4之間的邊緣，我們有與成本的邊緣4. 對於每個路徑的最大邊緣：路徑1-

0熱度

1回答

是對的：所有邊權重都是正數，那麼連接所有頂點並且總重量最小的任何邊權都必須是最小生成樹？

這個問題是從演練23.1-7演變而來的算法介紹。原來的問題是： 23.1-7 認爲，如果一個圖的所有邊緣權重是肯定的，那麼邊緣的任意子集，連接所有的頂點和具有最小的總重量必須爲樹。舉一個例子來說明，如果我們允許一些權重是非正的，那麼同樣的結論就不會遵循。但我認爲如果圖的所有邊權重都是正數，那麼連接所有頂點並且具有最小總權重的邊的任何子集都必須是最小生成樹。是我的必然嗎？如果沒有，請給我一個反

2熱度

1回答

使特定節點的程度最小化的最小生成樹

我們如何找到使節點度數最小的最小生成樹v（在所有最小生成樹中）？會修改Kruskal算法，使得如果有幾個邊具有相同的重量，我們選擇不接觸的那個v解決問題？

1熱度

1回答

從字典創建一個稀疏矩陣

我正在做一個學校項目，我給了一個無向圖G，並且我認爲在G內找到了最小生成樹。我想我會使用Scipy (https://docs.scipy.org/doc/scipy-0.14.0/reference/generated/scipy.sparse.csgraph.minimum_spanning_tree.html)中的minimum_spanning_tree。但要做到這一點，我必須爲它提供一個

1熱度

1回答

具有頂點權重和邊權重的最小Spanninjg樹

我正在解決有關最小生成樹的問題。因此，圖中的每個節點都是一個城市，並且可能具有連接兩個節點的權重邊，這是在兩個城市之間建設公路的成本。問題主要在於告訴我們建設道路的最低成本，並讓所有的城市都有一定的聯繫。我可以通過使用Prim或kruskal算法輕鬆解決這個問題，解決我最大的問題。棘手的部分是現在：每個城市（節點）可以有一個機場，每個機場都有一次性成本（如果你決定建造它）。如果兩個城市都有機場，

1熱度

1回答

總是有一些MST是最短路徑樹嗎？

在我的計算機科學課程。我們的教授給了我們這個期末考試的問題，我有麻煩：瑪麗莎和喬爾會在客場之旅，他們希望確保他們在每個城市停止（想街道作爲圖的邊緣，城市作爲頂點）。他們想要到達每個城市，他們將從家鄉紐約Vertexville的城市開始。他們希望儘可能提高燃料效率，不希望兩次看到相同的景色，因此他們要求在可能的公路行程路線中穿過的高速公路/道路是一個稱爲最短路徑樹的概念（換言之，在他們可能的路線中

0熱度

1回答

java - 如何找到MST中最大的加權邊緣？

根據標題，問題非常簡單。我有一個現有的MST，不帶有加權邊緣，有V個頂點。給定一個起始節點和結束節點，是否有一個有效的算法在O(V)時間運行，返回MST中最大的權重？謝謝！