Finden aller getrennten Teilgraphen in einem Graphen

Ich habe einen Graphen, der eine unbekannte Anzahl getrennter Teilgraphen enthält. Was ist ein guter Algorithmus (oder eine Java-Bibliothek), um sie alle zu finden?

Ich denke, was Sie suchen, wird allgemein als a bezeichnet Flutfüllung. Es liegt an Ihnen, ob Sie den Graphen durch ein BFS oder ein DFS durchlaufen.

Grundsätzlich nehmen Sie einen unbeschrifteten (AKA ungefärbten) Knoten und weisen ihm eine neue Beschriftung zu. Sie weisen allen benachbarten Knoten dieselbe Bezeichnung zu und so weiter allen Knoten, die von diesem Knoten aus erreichbar sind.

Wenn keine erreichbaren Knoten mehr beschriftet werden können, beginnen Sie erneut, indem Sie einen anderen unbeschrifteten Knoten auswählen. Beachten Sie, dass die Tatsache, dass dieser neue Knoten nicht gekennzeichnet ist, impliziert, dass er von unserem früheren Knoten nicht erreichbar ist und sich daher in einer anderen getrennten Komponente befindet.

Wenn es keine unbeschrifteten Knoten mehr gibt, ist die Anzahl der unterschiedlichen Beschriftungen, die Sie verwenden mussten, die Anzahl der Komponenten des Diagramms. Die Bezeichnung für jeden Knoten sagt Ihnen, welcher Knoten Teil welcher Komponente ist.

Keine Java-Implementierung, aber vielleicht ist sie für jemanden nützlich, hier ist, wie man es in Python macht:

import networkx as nx
g = nx.Graph()
# add nodes/edges to graph

d = list(nx.connected_components(g)) 
# d contains disconnected subgraphs
# d[0] contains the biggest subgraph

Mehr Informationen Hier.

Es gibt viele Facetten dieser Frage, die nicht vollständig erklärt werden, daher werde ich eine etwas erschöpfende Antwort geben. Ungeachtet meiner Tendenz, Walls-of-Text zu posten. :/ Beachten Sie auch, dass ich annehme, dass dies eine Hausaufgabenfrage oder eine Frage zum Selbststudium ist, also werde ich keine direkte Antwort geben.

Die beiden grundlegenden Algorithmen zum Erkennen der Konnektivität eines Graphen sind Tiefensuche zuerst Und Breitensuche zuerst. Das sind wirklich die 2 Ausgangspunkte, die Sie sich ansehen möchten. Beide werden Sie zur Lösung bringen, aber auf unterschiedliche Weise, und es ist schwer zu argumentieren, was “besser” ist, ohne einige ziemlich tiefgehende Aspekte des Problems zu berücksichtigen. Aber lass uns weitermachen.

Wie ich bereits erwähnt habe, haben Sie einige wichtige Details ausgelassen, und ich werde hier auf einige Möglichkeiten eingehen.

Ist Ihr Graph gerichtet oder ungerichtet? und betrachten Sie Konnektivität im “starken” Sinne (in diesem Fall siehe Oggys Antwort) oder Konnektivität im “schwachen” Sinne? Abhängig von Ihrer Antwort müssen Sie Ihren Algorithmus auf subtile Weise anders angehen. Beachten Sie, dass für einen ungerichteten Graphen schwache und starke Konnektivität äquivalent sind, das ist also schön. Aber Sie müssen trotzdem die Struktur des Diagramms im Auge behalten, während Sie einen Algorithmus implementieren oder finden.

Darüber hinaus stellt sich die Frage, was Sie mit “Finden der Teilgraphen” (Paraphrase) meinen. Normalerweise ist die Konnektivität von Graphen ein Entscheidungsproblem – einfach “es gibt einen verbundenen Graphen” oder “es gibt zwei oder mehr Teilgraphen (auch bekannt als getrennt)”. Einen Algorithmus dafür zu haben, erfordert am wenigsten Bucharbeit, was schön ist. 🙂 Der nächste Schritt nach oben wäre der zählen von Grafiken, buchstäblich die Anzahl von ihnen, und diese Bucharbeit ist auch nicht so schlecht. Vorletztes Mal möchten Sie vielleicht eine Liste von Knoten in jedem Unterdiagramm. Schließlich möchten Sie vielleicht die Untergraphen, Kanten und alles buchstäblich herauskopieren (der Rückgabetyp wäre also eine Liste von Graphen, nehme ich an, mit einer impliziten Invariante, dass jeder Graph verbunden ist). Keiner dieser unterschiedlichen Ergebnistypen würde einen anderen Algorithmus erfordern, aber wird sicher erfordern eine andere Herangehensweise an die Bucharbeit.

All dies mag wie eine lächerliche Menge an Overkill für eine ziemlich grundlegende Frage erscheinen, aber ich dachte, ich würde nur alle Aspekte hervorheben, die selbst bei einer so einfachen Grafikfrage eine Rolle spielen. Beachten Sie als eine Art Cliffhanger, dass dies noch nicht einmal die Laufzeit oder die Speichernutzung berührt! 🙂 – Agor

JGraphT ist eine schöne Open-Source-Grafikbibliothek, die unter der LGPL-Lizenz lizenziert ist. Ich habe es in der Vergangenheit verwendet, um mit Graphen umzugehen und Zyklen innerhalb der Graphen zu erkennen. Es ist auch ziemlich einfach zu bedienen, und Sie können es verwenden JGraph um die Graphen zu visualisieren.

Ich nehme an, Sie möchten alle (stark) verbundenen Komponenten finden? Dafür können Sie verwenden Tarjans Algorithmus (eine Variante von DFS)

Wie wäre es mit einer Breitensuche, um alle verbundenen Knoten zu finden? Sobald Sie die Liste der verbundenen Knoten haben, subtrahieren Sie diese Liste von der Liste aller Knoten. Am Ende erhalten Sie eine Liste mit getrennten Knoten

Ich hätte wahrscheinlich einen Standardalgorithmus finden sollen (Wikipedia hat einige Vorschläge), aber ich habe mir das selbst ausgedacht und es hat für meine Zwecke gut funktioniert. Meine C#-Implementierung benötigt ein paar Sekunden, um ein Diagramm mit 40.000 Knoten und 44.000 Kanten zu verarbeiten, um 160 Unterdiagramme und 20.000 nicht verbundene Knoten zu finden. Ich habe ein HashSet verwendet, um jede Subgraph-Gruppe zu speichern, sodass die Testgruppenmitgliedschaft ungefähr O (1) beträgt und der Gesamtalgorithmus zu O (E * C) wird, wobei E die Anzahl der Kanten und C die Anzahl der verbundenen Komponenten im Diagramm ist . Wikipedia erwähnt einen O(N)-Algorithmus, der in der Anzahl der Knoten linear ist, daher bin ich mir sicher, dass meiner nicht maximal effizient ist, aber für meine Anwendung war er ausreichend schnell. (Bearbeiten: Ich beschönige auch die Kosten für das Zusammenführen von Gruppen, also legen Sie nicht zu viel Gewicht auf meine Komplexitätsanalyse.)

Logik:

For each edge A->B
  If A is in a group and B is not, add B to group A
  If A is not in a group and B is, add A to group B
  If A and B are in different groups, merge the groups
  If neither A or B is in a group, create new group containing A and B

Pseudocode:

graph = {nodes, edges}
groups = {}
foreach edge A->B in graph.edges:
    groupA = findgroup(A)
    groupB = findgroup(B)
    if (groupA && !groupB)
        groupA.add(B)
    elif (!groupA && groupB)
        groupB.add(A)
    elif (groupA && groupB)
        if (groupA != groupB)
            groupA.union(groupB)
            groups.delete(groupB)
    else
        groups.add({A,B})

findgroup(node):
    for group in groups:
        if group.contains(node):
            return group
    return null

Beachten Sie, dass dadurch keine Knoten erfasst werden, die nicht an Kanten beteiligt sind. Für meine speziellen Zwecke war das in Ordnung. Wenn Sie alle Einzelknotengruppen erhalten möchten, können Sie einen letzten Durchgang durchführen:

foreach node in graph.nodes:
    group = findgroup(node)
    if !group:
        groups.add({node})