假設我有一個無向圖，其中我已經確定了關節點（即，洗掉時將斷開圖形的節點）。接下來，我想在該圖中洗掉/添加一個節點并確定關節點如何變化。是否有一種演算法可以使用先前計算的關節點來加快計算速度，或者在每次添加/洗掉我唯一的選擇后從頭開始？
為清楚起見，在下面的示例圖中，節點 2、3 和 5 是關節點。如果我洗掉節點 4，則 3 不再是關節點。如果我添加連接到節點 4 和 8 的節點 9，則節點 3 和 5 不再是關節點。我不確定如何概括這個程序。
uj5u.com熱心網友回復：
一般來說，您可能需要花費 Θ(n) 的作業來更新關節點串列。要看到這一點，假設您的圖只是具有 n 個節點的路徑。最初，您的所有節點都是關節點。添加一個將路徑封閉成回圈的新節點將使您的節點都不是關節點，然后洗掉任何這些節點將再次使所有內容成為關節點。
上述觀點意味著通常不會有一個快速的演算法來重新計算所有的關節點，因為存在糟糕的病理情況。但是，如果您可以接受比這更弱的東西，那么有一些方法可以實作快速插入和洗掉。具體來說，有一些演算法/資料結構可以解決完全動態的雙連接問題。這些資料結構允許您從圖中添加和洗掉節點和邊，并且像您一樣查詢一對節點是否是雙連接的（屬于同一個雙連接組件）。這與您要查找的內容并不完全匹配，但如果您的目標是確定在洗掉節點后哪些節點將保持連接，這可能會有所幫助。缺點是這些資料結構/演算法實作起來相當棘手。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/482721.html