Théorie des graphes

Trouvez le nombre d'îles ou de grappes (clusters)

Problème : 

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

Par exemple, la matrice ci-dessous contient 3 grappes ou îles


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.

Composants connectés :

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é.

Le problème peut être facilement résolu en appliquant le parcour en profondeur sur chaque composant. Dans chaque appel PARCOURSPROFONDEUR(), un composant ou un sous-graphe est visité. Nous appellerons PARCOURSPROFONDEUR() sur le prochain composant non visité. Le nombre d'appels à PARCOURSPROFONDEUR() donne le nombre de composants connectés. le parcours en largeur peut également être utilisé.
Modélisation :
  • 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
  1. Initialiser le compteur à 0, Initialiser un tableau 2D (visited) d'un booléen de taille égale à la matrice donnée
  2. 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é
  3. répéter l'étape 2 pour tous les éléments d'une matrice 2D donnée
  4. 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())
            
          

Partager ce cours avec tes amis :
Rédigé par Mostafa Sedoki
Computer science teacher and the founder of the e-learning platform "developpement-informatique.com", my mission is to provide high-quality courses for free to all computer science students and teachers

Cours Similaires :