Théorie des graphes

Notification de cookies

Nous utilisons des cookies pour améliorer votre expérience. En poursuivant votre navigation sur ce site, vous acceptez l'utilisation de cookies. Plus d'informations

Cercles d'amis

Problème : 

Il y a N étudiants dans une classe, chaque étudiant peut avoir 0 ou plusieurs amis si A est un ami de B et B est un ami de C, le A et le C sont également des amis.

Nous définissons un cercle comme un groupe d’élèves amis, tel que défini par la définition ci-dessus.

étant donnée une matrice friends de taille NxN constitués des caractères Y ou N. Si les friends[i][j]=Y alors les ième et jième étudiants sont des amis, sinon N.

Trouvez le nombre total de ces cercles d'amis en classe


  1. On commence avec le premier élève(i=0), définir visited[i] = Y.
  2. Initialiser NBCercles=1
  3. Passer à l'élève suivant j pour lequel friends[i][j] = Y, définir visited [j] = Y.
  4. Trouvez récursivement les amis de j et marquez-les comme étant visités jusqu'à ce que tous les étudiants pouvant être atteints à partir de i = 0 soient couverts, ils formeront un cercle d'amis.
  5. une fois que tous les amis de l'étudiant 1 sont parcourus, nous passons au prochain étudiant non visité et augmentons le NBCercles de 1.
  6. Répétez les étapes ci-dessus jusqu'à ce que tous les élèves soient visités.
  7. retourne NBCercles.
        friends = [['Y', 'Y', 'N', 'N'], ['Y', 'Y', 'Y', 'N'],
                    ['N', 'Y', 'Y', 'N'], ['N', 'N', 'N', 'Y']]
         
         
         def Cercle(friends):
             NB = len(friends)
             # Nombre de cercles
             NC = 0
             visited = [False for j in range(NB)]
             # parcourir les étudiants
             for i in range(NB):
                 # si l'élément n'est pas encore visité
                 if visited[i] == False:
                     # définir comme visité
                     visited[i] = True
         
                     # visiter ces voisins
                     # i indice de l'étudiant en cours
                     PARCOURSPROFONDEUR(i, visited)
         
                     # incrémenter le compteur
                     NC += 1
             return NC
         
         
         def PARCOURSPROFONDEUR(indice, visited):
             global friends
             for j in range(len(visited)):
                 # si etudiant j est ami(e) avec indice et n'est pas encore visité
                 if friends[indice][j] == 'Y' and indice != j and visited[j] == False:
                     # définir comme visité
                     visited[j] = True
         
                     # visiter ces voisins
                     PARCOURSPROFONDEUR(j, visited)
         
         
         print(Cercle(friends))         
                  
                

Partager ce cours avec tes amis :

Rédigé par M. ESSADDOUKI

Learning a new programming language is an easy thing, but the most difficult thing is how to design efficient algorithms for real-world problems, so don't be a programmer, be a problems solver.

Cours Similaires :