Yönlendirilmiş bir grafiğin zayıf bağlanmış bileşenlerinin her birini bulmak için algoritma

Question

Yönlendirilmiş bir grafikte zayıf bağlanmış her bileşenin bulunması için bir algoritma arıyorum. Ben bir dfs üzerinden bunu yapabilirsiniz, ama bu açıkça bir yönelimli grafik için işe yaramaz bir grafik için biliyorum. Grafiğimi bir bitişik liste olarak kaydediyorum. Örneğin :

A -> B 
B -> C 
D -> X 

Yani A-B-C, bağlı bileşendir bir D-X

şiddetle bağlı bileşenleri bulmak için bir algoritma ararken değilim !!

Answer 1

Bellek kısıtlamalarınız çok katı olmadıkça, ikinci bir geçici bitişik listesini saklayabilirsiniz. Bu ikinci bitişik listede her kenarı a-> b koyup kenarları ters yönde yerleştirirsiniz. (ör. b-> a) Daha sonra, bağlı bileşenleri bulmak için bu komşu listesindeki DFS'yi kullanabilirsiniz.

Answer 2

Oldukça basit bir çözüm şu şekildedir:
Belirtilen grafikten doğrulanmamış bir grafik oluşturarak başlayın - yalnızca bir kopya oluşturun ve her kenar için kenarları kenarlara ekleyin. Köşe kümesinin bir kopyasını oluşturun, rasgele bir köşe ile başlayın ve DFS'yi köşeyi içeren bileşenle çaprazlayın, tüm çapraz düğümleri kümeden kaldırın ve bir listeye ekleyin. Liste boşalana kadar bunu tekrarlayın. pseudocode

:

bimap edges 
edges.putAll(graph.edges()) 

set vertices = graph.vertices() 

list result 

while !vertices.isEmpty() 
    list component 

    vertex a = vertices.removeAny() 
    dfsTraverse(a , v -> { 
     vertices.remove(v) 
     component.add(v) 
    }) 

    result.add(component)