Was für die Suche nach isolierten Untergruppen

Question

Bild des richtigen Algorithmus ist mehr als tausend Worte wert ist, so:

Mein Eingang die Matrix auf der linken Seite ist, und was wir finden müssen, ist, die Sätze von Knoten, die sind maximal einen Schritt voneinander entfernt (nicht diagonal). Knoten, die mehr als einen Aufwärts/Abwärts/Links/Rechts-Schritt entfernt sind, würden in einem separaten Satz sein.

Also, mein Plan lief ein BFS von jedem Knoten, den ich finde, dann die Menge zurück, die es durchquerte, und es von der ursprünglichen Menge entfernend. Wiederhole diesen Prozess, bis ich fertig bin. Aber dann hatte ich die wilde Idee, nach Graph-Analysewerkzeugen zu suchen - und ich habe NetworkX gefunden. Gibt es einen einfachen Weg (Algorithmus?), Um dies zu erreichen, ohne BFS manuell zu schreiben und die gesamte Matrix zu durchlaufen?

Dank

Answer 1

Was Sie versuchen, für „verbundenen Komponenten“ zu tun, ist auf der Suche und NetworX hat sich ein Verfahren zur genau das wie tun können auf dieser documentation page wie andere im ersten Beispiel zu sehen ist bereits darauf hingewiesen, zu den Kommentaren.

Wenn Sie Ihre Frage lesen, scheint es, dass sich Ihre Knoten auf einem diskreten Gitter befinden und das von Ihnen beschriebene Konzept von Verbunden das gleiche ist, das auf dem Pixel eines Bildes verwendet wird.

Angeschlossene Komponenten Algorithmen sind auch für Grafiken und Bilder verfügbar.

Wenn die Leistung in Ihrem Fall wichtig ist, empfehle ich Ihnen, die Bildversion der verbundenen Komponenten zu verwenden. Dies kommt durch die Tatsache, dass Bilder (Raster von Pixeln) sind eine bestimmte Klasse von Graphen, so dass die verbundenen Komponenten Algorithmen mit Gittern von Knoten mit der Topologie des Graphen selbst erstellt werden (dh Graph ist planar, der maximale Eckpunkt ist vier). Ein allgemeiner Algorithmus für Graphen kann an allgemeinen Graphen arbeiten (dh sie können nicht planar sein, mit mehreren Kanten zwischen einigen Knoten), so dass er mehr Arbeit aufwenden muss, weil er nicht viel über die Eigenschaften der Eingabe annehmen kann Graph.

Da angeschlossene Komponenten auf Graphen in linearer Zeit gefunden werden kann, sage ich nicht, dass die Bildversion um Größenordnungen schneller wäre. Es wird nur einen konstanten Faktor zwischen den beiden geben. Aus diesem Grund sollten Sie auch berücksichtigen, welche Datenstruktur Ihre Eingabedaten enthält und wie viel Zeit in die Erstellung der Eingabestrukturen investiert wird, die von jeder Version des Algorithmus benötigt werden.