Algorithmus zum Ermitteln der Gesamtzahl der verbundenen Sätze in einer Matrix
Ich wollte wissen, welchen Algorithmus ich hier anwenden soll. Würde einDFS tun?
Gegeben eine 2D-Matrix. Suchen Sie die Gesamtzahl der verbundenen Sätze in dieser Matrix.
Verbundene Gruppe kann als Gruppe von Zellen definiert werden, auf denen 1 angegeben ist und die mindestens eine weitere Zelle in der Gruppe haben, mit der sie die Nachbarbeziehung teilen. Eine Zelle mit 1 und kein umgebender Nachbar mit 1 kann als Gruppe mit einer Zelle betrachtet werden. Nachbarn können als alle der gegebenen Zelle benachbarten Zellen in 8 möglichen Richtungen definiert werden (d. H. N-, W-, E-, S-, NE-, NW-, SE-, SW-Richtung). Eine Zelle ist kein Nachbar von sich.
Zum Beispiel:
1 0 0 1
0 0 1 0
0 0 1 0
1 0 0 1
Anzahl der verbundenen Sets ist 3
0 0 1 0 0 1 0 0
1 0 0 0 0 0 0 1
0 0 1 0 0 1 0 1
0 1 0 0 0 1 0 0
1 0 0 0 0 0 0 0
0 0 1 1 0 1 1 0
1 0 1 1 0 1 1 0
0 0 0 0 0 0 0 0
Die Anzahl der angeschlossenen Geräte beträgt 9.