Vérifier si un graphe donné est connecté ou non - solution en python

Le problème 

Un graphe \(G=(S,A)\) est dit connecté, si pour tout couple de sommets \((u,v)\) il existe un chemin reliant \(u\) et \(v\)

Exemple 1 : graphe orienté

le graphe ci-dessus est connecté parce que nous pouvons trouver un chemin entre chaque couple de sommets
les couples de sommets sont : (1,2), (1,3), (1,4), (1,5), (2,3), (2,4), (2,5), (3,2), (3,4), (3,5), (4,5)

Exemple 2 : graphe non orienté

Le graphe ci-dessus n'est pas connecté car nous ne pouvons pas trouver de chemin entre les sommets (5,6) et les autres sommets.
Ce graphe est composé de deux composants connectés

Question

Ecrivez une fonction qui permet de vérifier si un graphe donné est connecté ou non

 Remarque ! le graphe est représenté en utilisant la matrice d'adjacence

Solution

Pour résoudre ce problème, je vais décomposer le problème en deux sous-problèmes:

  • Vérifiez d'abord s'il existe un chemin entre deux sommets
  • Deuxièmement, la fonction principale, pour chaque couple de sommets, vérifiez s'il existe un chemin entre eux
Vérifiez d'abord s'il existe un chemin entre deux sommets
# Cette fonction utilise un algorithme de parcours en largeur
# pour savoir s'il existe un chemin entre deux sommets
# le graphe est représenté par la matrice d'adjacence


def ExistChemin(matriceAdj, u, v):
    n = len(matriceAdj)  # nombre de sommets dans le graphe
    file = []
    visites = [False] * n
    # ajouter le premier sommet à la file d'attente
    file.append(u)
    while file:
        # supprimer le sommet supérieur de la pile et marqué comme visité
        courant = file.pop(0)
        visites[courant] = True

        # visiter les sommets adjacents
        for i in range(n):
            # s'il existe et qu'un bord entre u et i et
            # le sommet i n'est pas encore visité
            if matriceAdj[courant][i] > 0 and visites[i] == False:
                # ajouter i à la file marqué comme visité
                file.append(i)
                visites[i] = True

            # Si le sommet i est le sommet voulu (i = v)
            # donc il existe un chemin de u à i(v)
            elif matriceAdj[courant][i] > 0 and i == v:
                return True

    return False

                            
La fonction principale - cas graphe non orienté
def connecte(matriceAdj):
    n = len(matriceAdj)  # nombre de sommets
    for i in range(i):
        for j in range(i+1, n):
            if ExistChemin(matriceAdj, i, j) == False:
                return False

    return True
                            
La fonction principale - cas graphe orienté
def connecte(matriceAdj):
    n = len(matriceAdj)  # nombre de sommets
    for i in range(i):
        for j in range(n):
            if (i != j) and ExistChemin(matriceAdj, i, j) == False:
                return False

    return True

                            

Partager ce cours avec tes amis :

Rédigé par ESSADDOUKI Mostafa

The education of the 21st century opens up opportunities to not merely teach, but to coach, mentor, nurture and inspire.

Commentaire(s)