找到有向圖中的關節點的算法

Question

我知道如何找到關於使用DFS變體的無向圖的關節點。但它似乎是無向圖，只能看後面的邊緣。但是，如果我的圖有前沿或者交叉邊，我該如何找到銜接點。我知道我總是可以爲每個節點運行dfs，並計算出來，但有沒有更好的算法。

Answer 1

有向圖上的關節點的定義並不唯一。 這取決於你正在考慮什麼樣的連通性。在有向圖中有3種連接

強連接如果存在從每個頂點到每個其他頂點的路徑。

連接如果有任何兩個節點之間的路徑，但不是在兩個方向。

弱連接如果只有當弧被替換爲無向弧時才連接圖。

如果您使用連接的第二個定義，那麼U可以使用DFS查找點。

我不確定，但我認爲如果你定義連接爲弱連接那麼你也可以使用DFS。但它需要證明。