拆分圖算法

Question

圖有n個頂點和m個邊。圖形開始連接，然後按照它們出現在列表中的順序刪除邊線。在這個過程結束時，圖形被斷開。

因此，在邊緣列表中存在特定的邊緣，使得在去除邊緣之前，有一個連接的分量超過n/4個頂點的頂點。刪除該邊後，圖中沒有超過n/4個頂點的連通分量。

我該如何去設計最佳算法來找到這個邊緣。我是否剛剛開始刪除邊，然後每次遍歷圖來檢查最大連接組件是否滿足要求？這在O（nm）時間運行，但我覺得必須有一些更快的方式。我認爲答案與使用不連貫的集合來查找連接的組件有關，但我不確定如何去實現它。

Answer 1

考慮運行此過程反向，添加邊而不是刪除邊。該過程與Kruskal的算法非常相似（每個節點由其自身開始，並在連接不同的連接組件時添加邊），但只要至少有一個連接組件至少有＆lfloor; n/4＆rfloor ;節點。

解決此問題的一種方法是使用Kruskal算法的修改版本和聯合查找數據結構，以便聯合查找結構中的每個代表存儲其連接組件中的節點數。以相反的順序遍歷邊，如果端點已經連接，則在每個點放棄邊，否則將它們鏈接起來。如果你添加一個邊緣，導致至少有一個連接組件＆nfl; n/4＆rfloor;節點，你找到了你正在尋找的邊緣。如果使用union-find數據結構的快速實現，這將在時間O（n + m α（n））中運行，這在實踐中基本上是線性的。