Théorie des graphes

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 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 :