Algorithmus um Articulation Punkte in einem gerichteten Graphen zu finden

Question

Ich kann Articulation Punkte für einen ungerichteten Graphen finden, der DFS Variante benutzt. Aber es scheint, als ob es für ungerichtete Graphen ist und nur nach Back Edge sucht. Aber wie finde ich Articulation-Punkte, wenn mein Graph eine Vorwärts- oder eine Cross-Flanke hat? Ich weiß, dass ich immer dfs für jeden Knoten ausführen kann und das herausfinden kann, aber gibt es einen besseren Algorithmus.

Answer 1

Definition für Articulation Punkte auf gerichteten Graphen ist nicht eindeutig. Es hängt davon ab, welche Art von Verbundenheit Sie in Betracht ziehen. Es gibt 3 Arten von Verbindungen in gerichteten Graphen

Stark verbunden, wenn es einen Pfad von jedem Eckpunkt zu jedem anderen Eckpunkt gibt.

Verbunden wenn zwischen zwei Knoten ein Pfad besteht, aber nicht in beiden Richtungen.

Schwach verbunden wenn der Graph nur verbunden ist, wenn die Bögen durch ungerichtete Bögen ersetzt werden.

Wenn Sie die zweite Definition der Verbindung verwenden, kann U DFS zum Suchen von Punkten verwenden.

Ich bin mir nicht sicher, aber ich denke, dass, wenn Sie Verbindung als Weakly verbunden definieren, dann können Sie auch DFS verwenden. Aber es muss bewiesen werden.