我正在閱讀BOOST庫，發現他們有一個算法來查找圖中的橋，他們確實有一個找到關節點。無論如何，這可以有效地完成？在圖C++（BOOST）中查找橋樑？
我有一個想法：
使用升壓找到鉸接點
2.使用out_edges，找到所有邊緣連接的每個關節點
3.刪除它們並計算連接組件上的數量（我假設我的圖形最初是完全連接的），如果它超過1，我添加這邊緣的橋樑。
問題：橋樑是否需要連接到關節點？我只是假設他們是，找不到任何網絡。
我也想知道如何解決這個問題。
我的另一種方法會更天真，並採取O（V *（V + E）），這是非常糟糕的。
整個圖形重寫的聲音有點慢。您必須檢查Boost是否計算單連接頂點作爲關節點。 （如果不是，這會使事情稍微複雜一些）。
現在很明顯，一個橋必須是兩個關節點之間的邊緣，而不是關節點之間的所有邊緣都必須是橋。考慮由3個邊連接的4個關節點鏈：A-b-c-D。現在添加一個連接到b和c的節點。外部的兩座橋樑仍然是橋樑，所以所有4個原始節點都保持鉸接點，但中間節點不再是橋樑。
這意味着我們有一個必要但不足的額外條件：邊的兩個節點都必須是關節點。這是輕微複雜的步驟;如果Boost不將單連接節點計算爲關節點，則必須特別對待它們。但這仍然很簡單。那邊緣必然是一座橋樑。
這個額外的條件在密集圖中是非常有效的，因爲大多數節點不會是關節點。因此，在嘗試更改圖形之前，請先挑選出大多數候選邊緣。其次，你不需要測試結果改變圖的組件數。你只需要檢查直接鏈接它們的邊緣後，兩個關節點是否仍然連接。
當你意識到如果一個雙連通元件只包含一條邊，這條邊就是一座橋，那麼有一種更簡單的方法。這是很容易使用boost（http://www.boost.org/doc/libs/1_58_0/libs/graph/example/biconnected_components.cpp）來實現：
林一點不清楚，所以你說我只需要檢查邊緣的整個末端都是關節點？ – LoveMeow 2014-11-24 13:49:50
@LoveMeow：嘗試使用具有兩個節點和一個邊的平凡圖。如果Boost將兩個節點都算作關節節點，那麼是的。如果Boost不把它們算作關節節點，那麼你需要對圖進行預處理（但效率更高）。迭代地，枚舉所有單連接的節點，將它們的單邊標記爲橋，刪除該邊並再次檢查。 （這反覆修剪線性鏈，其中所有的邊緣都是橋樑） – MSalters 2014-11-24 14:00:52
我檢查了，boost並沒有在關節點上對它們進行計數！所以我需要枚舉所有連接到一個邊的節點，並將它們標記爲橋，除了兩個關節點之間的那些節點？ – LoveMeow 2014-11-24 14:13:39