Trouvez le nombre d'îles ou de grappes (clusters)
Etant donnée une matrice de 0 et de 1, trouvez le nombre total de grappes formées d'éléments de valeur 1
Un groupe de 1 connectés forme une graphe
le problème est similaire aux composants connectés dans un graphique. aussi, avant de commencer à résoudre le problème, nous devons comprendre la notion de composants connectés dans un graphique.
Un composant connecté d'un graphe non orienté est un sous-graphe dans lequel tous les deux sommets sont connectés l'un à l'autre par un ou plusieurs chemins, et qui n'est connecté à aucun autre sommet en dehors du graphe.
Par exemple, le graphe présenté ci-dessous a trois composantes connexes.
Un graphe où tous les sommets sont connectés les uns aux autres a exactement un composant connecté, constitué du graphe entier. Un tel graphe avec un seul composant connecté est appelé graphe fortement connecté.
- traiter une matrice donnée comme un graphe
- l'élément de valeur 1 est considéré comme un sommet.
- les sommets adjacents de valeur 1 sont voisins
- Trouver le nombre de composants connectés dans le graphe
- Initialiser le compteur à 0, Initialiser un tableau 2D (visited) d'un booléen de taille égale à la matrice donnée
- pour chaque élément graphe[i][j], si égal à 1 et visited est faux, alors
- incrémenter le compteur de 1
- lancer le parcours en profondeur sur cet élément, cette recherche en profondeur marquerait tous les sommets qui sont directement ou indirectement connectés à cet élément comme visité
- répéter l'étape 2 pour tous les éléments d'une matrice 2D donnée
- retourner le compteur
graphe = [[1, 0, 1, 0, 1], [1, 1, 0, 0, 0], [0, 1, 0, 1, 1]]
row = len(graphe)
col = len(graphe[0])
def estsommet(i, j, visited):
global graphe, row, col
# vérifier si les indices sont valides, graphe[i][j]=1 et visited[i][j]=false
return (i >= 0 and i < row and j >= 0 and j < col and not visited[i][j] and graphe[i][j])
def PARCOURPROFONDEUR(i, j, visited):
# indices des voisins (8 éléments)
# -1 colonneou ligne précedente ; 0 meme ligne ou colonne, 1 ligne ou colonne suivante
VLignes = [-1, -1, -1, 0, 0, 1, 1, 1]
VCol = [-1, 0, 1, -1, 1, -1, 0, 1]
# marquer cette cellule comme visitéé
visited[i][j] = True
# Répéter pour tous les voisins connectés
for k in range(8):
if estsommet(i + VLignes[k], j + VCol[k], visited):
PARCOURPROFONDEUR(i + VLignes[k], j + VCol[k], visited)
def clusters():
global graphe, row, col
# Initialiser le tableau visited à false
visited = [[False for j in range(col)]for i in range(row)]
# initialiser le compteur à 0
# parcourir les cellules
count = 0
for i in range(row):
for j in range(col):
# SI Cellule est non visitée et contient la valeur 1
if visited[i][j] == False and graphe[i][j] == 1:
# visiter les cellules de la grappe
# incrémenter le compteur
PARCOURPROFONDEUR(i, j, visited)
count += 1
return count
print("Nombre de grappes est :")
print(clusters())
