Nombre de grappes dans une matrice
Étant 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 grappe (ou île).
Par exemple, la matrice ci-dessus contient 3 grappes (ou îles).
Le problème est similaire aux composants connectés dans un graphe. Avant de résoudre le problème, il est important de comprendre cette notion.
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.
Le graphe ci-dessus a trois composants connectés.
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 connexe.
- Traiter une matrice donnée comme un graphe
- Un élément de valeur 1 est considéré comme un sommet.
- Les sommets adjacents (8 directions) de valeur 1 sont voisins.
- Objectif : Trouver le nombre de composants connectés dans ce graphe.
Le problème peut être facilement résolu en appliquant le parcours en profondeur (DFS) sur chaque composant.
- Dans chaque appel DFS, un composant (ou sous-graphe) est visité.
- Nous appellerons DFS sur le prochain composant non visité.
- Le nombre d'appels à DFS donne le nombre de composants connectés (grappes).
Le parcours en largeur (BFS) peut également être utilisé.
- Initialisation : Initialiser le compteur à 0. Créer un tableau 2D
visitedde booléens de même taille que la matrice, initialisé àFalse. - Parcours de la matrice : Pour chaque élément
matrice[i][j]:- Si l'élément vaut 1 et n'a pas encore été visité (
visited[i][j] == False) :- Incrémenter le compteur de 1 (nouvelle grappe trouvée).
- Lancer un parcours en profondeur (DFS) à partir de cet élément.
- Ce DFS marquera tous les sommets (1) connectés directement ou indirectement à cet élément comme visités.
- Si l'élément vaut 1 et n'a pas encore été visité (
- Répétition : Répéter l'étape 2 pour tous les éléments de la matrice.
- Résultat : Retourner la valeur du compteur.
Implémentations
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define ROWS 3
#define COLS 5
// Matrice exemple
int graphe[ROWS][COLS] = {
{1, 0, 1, 0, 1},
{1, 1, 0, 0, 0},
{0, 1, 0, 1, 1}
};
// Tableau des visites
bool visited[ROWS][COLS];
// Vecteurs pour les 8 directions (voisins)
int VLignes[] = {-1, -1, -1, 0, 0, 1, 1, 1};
int VCol[] = {-1, 0, 1, -1, 1, -1, 0, 1};
// Fonction pour vérifier si une cellule est valide et non visitée
bool estSommet(int i, int j) {
return (i >= 0 && i < ROWS && j >= 0 && j < COLS &&
!visited[i][j] && graphe[i][j] == 1);
}
// Parcours en profondeur (DFS)
void dfs(int i, int j) {
visited[i][j] = true;
// Explorer tous les voisins (8 directions)
for (int k = 0; k < 8; k++) {
int ni = i + VLignes[k];
int nj = j + VCol[k];
if (estSommet(ni, nj)) {
dfs(ni, nj);
}
}
}
// Fonction principale pour compter les grappes
int compterGrappes() {
int count = 0;
// Initialiser le tableau visited à false
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
visited[i][j] = false;
}
}
// Parcourir toutes les cellules
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
// Si cellule non visitée et contient 1
if (!visited[i][j] && graphe[i][j] == 1) {
// Découvrir toute la grappe
dfs(i, j);
count++;
}
}
}
return count;
}
int main() {
printf("Matrice :\n");
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLS; j++) {
printf("%d ", graphe[i][j]);
}
printf("\n");
}
int resultat = compterGrappes();
printf("\nNombre de grappes : %d\n", resultat);
return 0;
}# Matrice exemple
graphe = [
[1, 0, 1, 0, 1],
[1, 1, 0, 0, 0],
[0, 1, 0, 1, 1]
]
row = len(graphe)
col = len(graphe[0])
# Vecteurs pour les 8 directions
VLignes = [-1, -1, -1, 0, 0, 1, 1, 1]
VCol = [-1, 0, 1, -1, 1, -1, 0, 1]
def estSommet(i, j, visited):
"""Vérifie si la cellule (i,j) est un sommet valide et non visité"""
return (i >= 0 and i < row and j >= 0 and j < col and
not visited[i][j] and graphe[i][j] == 1)
def dfs(i, j, visited):
"""Parcours en profondeur pour marquer tous les sommets d'une grappe"""
visited[i][j] = True
# Explorer tous les voisins (8 directions)
for k in range(8):
ni = i + VLignes[k]
nj = j + VCol[k]
if estSommet(ni, nj, visited):
dfs(ni, nj, visited)
def compterGrappes():
"""Compte le nombre de grappes dans la matrice"""
# Initialiser la matrice des visites
visited = [[False for _ in range(col)] for _ in range(row)]
count = 0
# Parcourir toutes les cellules
for i in range(row):
for j in range(col):
# Si cellule non visitée et contient 1
if not visited[i][j] and graphe[i][j] == 1:
# Découvrir toute la grappe
dfs(i, j, visited)
count += 1
return count
print("Matrice :")
for ligne in graphe:
print(' '.join(map(str, ligne)))
resultat = compterGrappes()
print(f"\nNombre de grappes : {resultat}")Matrice : 1 0 1 0 1 1 1 0 0 0 0 1 0 1 1 Nombre de grappes : 3
- Complexité temporelle : \(O(rows \times cols)\) - chaque cellule est visitée au plus une fois.
- Complexité spatiale : \(O(rows \times cols)\) - pour la matrice
visited, plus la pile de récursion (profondeur maximale = taille de la plus grande grappe).
Selon la définition de "connecté", on peut considérer uniquement les 4 directions (haut, bas, gauche, droite) au lieu des 8 directions (incluant les diagonales). Il suffit de modifier les vecteurs de déplacement :
VLignes = [-1, 1, 0, 0]
VCol = [0, 0, -1, 1]
Discussion (0)
Soyez le premier à laisser un commentaire !
Laisser un commentaire
Votre commentaire sera visible après modération.