Algorithmus zum Zählen der Anzahl der verbundenen Elemente für jedes Element in einer Matrix

Question

Ich suche nach Weg, um die Anzahl der verbundenen (benachbarten) Elemente in einer Matrix zu finden. Ich habe ein 2D-Array von Objekten, bei denen für jedes Objekt ein Flag gesetzt sein kann. Wenn das Flag gesetzt ist, muss ich die Anzahl der Nachbarn zählen, für die auch das Flag gesetzt ist. Für jeden Nachbarn wird der Prozess wiederholt.

Siehe das Bild für eine Visualisierung des Problems:

Ich denke, das ein ziemlich häufiges Problem ist. Wie ist der Name, damit ich selbst recherchieren kann?

Answer 1

Es kann mit flood fill, die eine Variante von DFS ist. Dies setzt voraus, dass Ihre Matrix tatsächlich ein Graph ist, bei dem jede Zelle ein Knoten ist und sich zwischen zwei benachbarten Zellen eine Kante befindet.

könnte ein möglicher Pseudo-Code sein:

DFS(v,visited): 
    if v is not set: 
     return [] 
    else: 
     nodes = [v] 
     for each neighbor u of v: 
      if u is not in visited: 
        visited.add(u) 
        nodes.addAll(DFS(u,visited)) 
     return nodes 

Wenn Sie von einem bestimmten Punkt v starten, wird es t Liste mit allen Knoten verbunden v (einschließlich v selbst) zurückzukehren, und Sie ihren „Wert leicht einstellen "wie size(nodes).

Der folgende Pseudocode werden alle Knoten mit der Größe ihres „cluster“ -Markierung:

markAll(V): //V is the set of all cells in the matrix 
    visited = [] //a hash set is probably best here 
    while (V is not empty): 
     choose random v from V 
     visited.add(v) 
     nodes = DFS(v,visited) 
     for each u in nodes: 
      value(u) = size(nodes) 
     V = V \ nodes //set substraction 

Komplexität dieses Ansatzes wird O(|V|) = O(n*m) sein - so in der Größe der Matrix linear (worin n * m ist,)

Answer 2

Wie wäre es mit der Disjoint set or union-find Datenstruktur?

Grundsätzlich gilt:

Jedes Mal, wenn ein Flag hinzugefügt wird, oder Sie bemerken, dass ein Element eine Fahne hat, scannen, die Nachbarn des Elements. Sobald Sie ein Element mit einem Flag darin finden, clustern Sie die Elemente zusammen, indem Sie sie auf das gleiche Elternelement zeigen. Entweder direkt oder rekursiv.

Eine Zählung der Elementanzahl für jeden Cluster beibehalten.