flâneur

Spanning Tree - 演算法筆記

web.ntnu.edu.tw · 347 words · saved by 1 readers

如果兩點之間有多條邊，預先以 Graph Traversal 掃描一次所有邊，保留權重最小的邊，仍可求得正確答案。兩點之間只剩下一條邊，邊數至多 C(V,2) = V(V-1)/2 = O(V²) 條。時間複雜度 O(ElogE) 可以改寫成 O(ElogV²) = O(2ElogV) = O(ElogV) 。

用途 求出有向圖的其中一棵最小（大）生成樹。 有向圖上，以權重最小的邊，連結兩棵有向 MSS ，不見得形成有向 MSS 。直接套用無向圖的演算法，邊的方向亂七八糟，無法形成有向生成樹。必須設計其他演算法。 想法 生成樹的基本概念是：連接圖上各點的樹。從這個概念下手，並且考慮邊的方向性，得到兩個粗糙的演算法： 有向圖上，每一個點，如果要被連結到，都要至少有一條出邊，除了樹葉以外。 每一個點，找權重最小的出邊，會比較好。 有向圖上，每一個點，如果要被連結到，都要剛好有一條入邊，除了樹根以外。 每一個點，找權重最小的入邊，會比較好。 出邊有許多條，入邊只有一條，從入邊下手比較容易。 樹根是個例外，樹根沒有入邊。但是我們可以假定我們已經知道最小生成樹的樹根是哪個點，如此就不必顧慮例外了。設計好演算法之後，用試誤法嘗試各種樹根即可。 minimum arborescence 預先指定樹根的有向最小生成樹。個人感覺這個詞彙不太討喜。 水母【尚無正式名稱，因為像水母就把它叫做水母】 運氣好的時候，各點的最小入邊，剛好形成一棵生成樹，而且是最小生成樹。 運氣普通的時候，各點的最小入邊，通常形成許多隻水母。 各點各取一條入邊，一旦入邊們形成環，此環一定只有出邊、沒有入邊。環與出邊，形成一個特別的圖：很多棵樹，一個環串起了樹根。又像是太陽、又像是水母。…

saved by

related reading