minimum-spanning-tree

    4熱度

    1回答

    使用Kruskal算法尋找圖中的最小切點？

    我們已經看到，生成樹和切割是密切相關的。這是另一個連接。讓我們刪除克魯斯卡爾算法添加到生成樹的最後一條邊;這將樹分成兩個部分，從而在圖中定義一個切割（S，S）。我們可以說這個削減？假設我們正在使用的圖是未加權的，並且它的邊是隨機排列的，以便Kruskal算法處理它們。這是一個值得注意的事實：在概率至少爲1/n^2的情況下，（S，S）是圖中的最小切割，其中切割的大小（S，S）是S和S之間的邊的數量。
    algorithm math minimum-spanning-tree minimum-cut kruskals-algorithm 2012-07-06

    1熱度

    4回答

    使用最小生成樹查找從A到B的路徑 - C/C++

    假設我們找到最小生成樹。現在，我們只需要在MST中從A到Z的路徑。我們如何在O（n^2）時間內做到這一點？ 我們從根A開始，然後我們查看Ax形式的樹（其中x是任何頂點）中的所有邊。 然後，說我們找到：AB，AC，AD等...... 然後對於每一個，我們尋找形式的邊：Bx，Cx，Dx ...這顯然不是O（n^2 ）。 那麼什麼是更好/有效的方式來找到路徑A - > Z給定MST？ 由於
    c++ algorithm tree graph-algorithm minimum-spanning-tree 2012-07-09

    0熱度

    2回答

    Prim和Kruskal的算法複雜度

    給定一個帶有權重的無向連通圖。 w：E - > {1,2,3,4,5,6,7} - 意思是隻有7個砝碼可能。 我需要使用O（n + m）中的Prim算法和O（m * a（m，n））中的Kruskal算法找到生成樹。 我不知道如何做到這一點，真的需要一些關於如何權重可以幫助我在這裏的指導。
    algorithm minimum-spanning-tree prims-algorithm kruskals-algorithm 2012-05-28

    1熱度

    2回答

    更改爲圖中非MST邊緣以更改MST

    設計一個算法，該算法採用加權圖G，並找到非MST邊緣的成本中的最小變化，這將導致生成最小生成樹的最小生成樹G. 我的解決方案至今（需要建議）： 若要更改爲MST，我們需要改變非MST邊緣ST的重量它比MST中其起始頂點和結束頂點的路徑中的最大邊緣小1。因此，我們可以先步行MST的邊緣，併爲每個頂點檢查是否存在非MST邊緣。如果有，可以完成一個bfs到達邊緣的終點（在MST中）。非MST邊權重必須更
    algorithm graph minimum-spanning-tree 2012-05-28

    2熱度

    3回答

    找到一個最小瓶頸生成樹

    嗨，我正在做一些測試準備，我需要找出部分B和C.我知道a部分是真的，我可以證明這一點，但找到部分b和c的算法目前正在逃避我。 爲最小瓶頸樹求解以下問題，其中成本最大的邊被稱爲瓶頸。 （a）G的最小生成樹的每個最小瓶頸是哪個最小生成樹G？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？證明你的主張。 （b）對於給定的代價c，給出一個O（n + m）時間算
    algorithm tree graph-theory minimum-spanning-tree 2012-10-29

    7熱度

    1回答

    查找所選頂點的最小生成樹的算法

    可以使用Prim算法或Kruskal算法來查找頂點/節點和邊/鏈接集合的最小生成樹/圖。我想要的是找到這個集合的最小生成圖的算法，但是生成的圖只需要包含任意選擇的節點，而不是所有的節點。如果結果圖包含的節點數多於所需數量，那麼這樣做沒問題。 這樣的算法是否存在？也許可以在修改圖形後僅使用Prim（或Kruskal's）算法來僅包含所需的節點？但是，我不確定如何在保持連通性的同時修改圖形。 例如，假
    algorithm graph minimum-spanning-tree 2012-10-30

    1熱度

    1回答

    以鄰接矩陣爲參數的Prim MST

    我正在C中使用Prim MST，並且該功能需要一個鄰接矩陣。鑑於當然在A[i][j]的重量。 假設我有一個前驅數組，跟蹤我迄今爲止發現的最小邊。 predecessor[u]=v {這也是最終MST} 現在我想修改當前A[i][j]矩陣和更改爲1 的權重即當邊緣（索引）的前身陣列中也存在。 否則我將其更改爲零。 我該怎麼做？這是我的解決方案： for (x....) for (y...)
    c algorithm minimum-spanning-tree prims-algorithm 2012-07-24

    0熱度

    3回答

    如何以快速方式查找邊緣序列中的所有路徑？

    設E是給定的有向邊集。假設已知E中的邊可以形成有向樹T，其中所有節點（根節點除外）只有1個入度。問題是如何有效地遍歷邊集E，以找到T中的所有路徑？例如，給定有向邊集E = {（1,2），（1,5），（5,6），（1,4），（2,3）}。我們知道這樣一個集合E可以生成一個只有1個入度的有向樹T（除了根節點）。有沒有遍歷邊集E，爲了找到所有的路徑如下任何快速的方法： Path1 = {(1,2),(2
    algorithm graph graph-algorithm minimum-spanning-tree 2012-06-16

    1熱度

    1回答

    請詳細說明優先級隊列中的減少密鑰和提取最小值操作之間的關係

    EXTRACT-MIN操作和DECREASE-KEY優先級隊列中的操作之間的關係是什麼？我在使用Prim算法的最小生成問題講座中遇到了這個問題。 麻省理工學院教授refers to it at point 01:07:16 seconds in the video但我沒有得到它。有人可以幫我解決這個問題嗎？ P.S：對於我對優先隊列的理解，我感覺很舒服。
    algorithm data-structures priority-queue minimum-spanning-tree prims-algorithm 2012-09-27

    0熱度

    1回答

    在最小生成樹的Prims算法中π[v]←u是什麼意思？

    在這MIT video regarding Prims algorithm for minimum spanniing tree教授在時間71:16秒解釋π[v] ←u。但我不明白爲什麼我們需要這一步。 π[v] ←u是什麼意思？算法中最後一行的含義是什麼？ 在源給出的整個算法如下： Q←V key[v] ←∞for all v∈V key[s] ←0for some arbitrary s∈
    algorithm data-structures graph-algorithm minimum-spanning-tree 2012-10-01
最新問題