27 - Graphe : Largeur en Python

⏪

⏬

⏩

1 - algorithme

2 - Impl.Graphe

3 - Parcours en largeur

4 - Plus simple

5 - FAQ

Logiciel nécessaire pour l'activité : -

Prérequis :

Algo : Parcours en largeur d'un Graphe

Evaluation ✎ : 01-02-03-08-09-10-11-12-13-14-15

Documents de cours : open document ou pdf

MODE COURS (cacher les questions)

1 - [rappel] Algorithme de parcours en largeur

⇩ ⇧ ⤊

Algorithme du parcours en largeur

ENTREES

Un graphe noté g
Un sommet qui servira de sommet origine, noté s appartenant au graphe g

SORTIE

Aucune ici mais on peut facilement modifier l'algorithme pour qu'il renvoie par exemple l'Arbre de parcours.

ALGORITHME PARCOURS EN LARGEUR

on initialise tous les sommets

POUR chaque sommet u appartenant au graphe g

u.couleur ← BLANC

u.distance ← INFINI

u.parent ← VIDE

Fin Pour

on initialise le sommet origine

s.couleur ← GRIS

s.distance ← 0

s.parent ← VIDE

on crée la file et on y place le sommet origine

a_traiter ← nouvelleFileVide()

enfiler(a_traiter, s)

on sort et active un sommet à la fois de la file

TANT QUE NON estVide(a_traiter)

u ← defiler(a_traiter)

POUR chaque sommet v appartenant à la liste d'adjacence du sommet u

SI v.couleur est BLANC

si on arrive ici, c'est que le sommet n'a pas encore été découvert

v.couleur ← GRIS

v.distance ← u.distance + 1

v.parent ← u

enfiler(a_traiter, v)

Fin Si

u.couleur ← NOIR

Fin Pour

Fin Tant Que

Renvoyer VIDE (∅)

Les informations liées au parcours sont stockées directement dans les sommets.

Aucune importance tant qu'il s'agit de réfléchir à la façon de gérer les choses. C'est plus ennuyeux lorsqu'on passe à l'implémentation réelle : modifier le graphe des routes à chaque fois qu'on lance le GPS n'est pas une bonne idée.

Dans les implémentations Python proposées, nous allons donc séparer les deux types de données :

D'un côté le graphe avec les sommets et les arêtes
De l'autre les informations sur le parcours en largeur.

2 - Implémentation du graphe

⇩ ⇧ ⤊

Il existe deux grandes familles d'implémentation des arêtes d'un graphe :

Par une matrice d'adjacence
Par des listes d'adjacence

Nous n'avons pas envie de fournir une fonction de parcours par implémentation...

Possibilité 1: matrice d'adjacence


Matrice d'adjacence :
[[0, 1, 1, 0, 0], 
 [1, 0, 0, 1, 0], 
 [1, 0, 0, 1, 0], 
 [0, 1, 1, 0, 1], 
 [0, 0, 0, 1, 0]
]

Possibilité 2 : l'ensemble des arêtes (dans un tuple car set n'est pas au programme)


Ensemble S des arêtes :
((0,1), 
 (0,2), 
 (1,3),
 (2,3),
 (3,4)
)

Possibilité 3 : listes d'adjacence dans un tableau


Listes d'adjacence stockées dans un tableau :
[[1, 2], 
 [0, 3], 
 [0, 3], 
 [1, 2, 4], 
 [3]]

Possibilité 4 : listes d'adjacence dans un dictionnaire


Listes d'adjacence stockées dans un dictionnaire :
{0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3]}

Possibilité ... : ...

Bref, il faut choisir un des formats en tant que format reconnu par notre fonction de parcours et fournir des fonctions de conversion de façon à toujours pouvoir y revenir.

Nous décidons de faire travailler nos fonctions de parcours sur des listes d'adjacences de la possibilité 4, qui ressemblent à ceci :


Listes d'adjacence stockées dans un dictionnaire :
{0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3]}

Dans le but de simplifier encore le problème, on considérera ici que les sommets ne contiennent aucune information à part leur numéro.

La liste d'adjacence caractérise donc le graphe en totalité.


>>> graphe = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3]}
>>> s = list(graphe.keys())
>>> s
[0, 1, 2, 3, 4]
 
>>> temporaire = []
>>> for s, lst_adj in graphe.items(): 
        for s2 in lst_adj: 
            if not (s2, s) in temporaire:
                temporaire.append( (s, s2) )
 
>>> a = tuple(temporaire)
>>> a
((0, 1), (0, 2), (1, 3), (2, 3), (3, 4))
 
>>> g = (s, a)

On voit donc qu'on peut passer du graphe "dictionnaire" au graphe version "mathématique".

Voici comment passer du graphe "mathématique" au graphe "dictionnaire".

01° Donner le dictionnaire dont les clés sont les étiquettes des sommets et les valeurs sont les listes d'adjacence de ce sommet.

  1
  2
  3

s = (0, 1, 2, 3, 4)                      # Ensemble s des sommets du graphe 
a = ((0,1), (0,2), (1,3), (2,3), (3,4))  # Ensemble a des arêtes
g = (s, a)                               # Graphe défini comme un couple

Correction ?

...CORRECTION...


{0: [1, 2], 
 1: [0, 3], 
 2: [0, 3], 
 3: [1, 2, 4], 
 4: [3]
}

02° Lancer le programme puis expliquer comment fonctionne cette fonction en fournissant un commentaire sur les lignes de la fonction.

"""Implémentation du parcours en largeur"""
 
# Fonctions =====================================================
 
def creer_graphedico_no_np(g:tuple) -> dict[int, list]:
    """Renvoie un graphe-dico à partir du graphe-couple (non orienté, non pondéré)"""
 
    s, a = g
    graphe = {}
 
    for sommet in s:
        graphe[sommet] = []
    for arete in a:
        s1, s2 = arete
        graphe[s1].append(s2)
        graphe[s2].append(s1)
 
    return graphe
 
def largeur_d_abord_v1(g:dict[int, list], s:int) -> dict:
    """Renvoie un dictionnaire contenant la distance à s et le parent de chaque sommet"""
 
    return {}
 
def donner_chemin(sommet_initial, sommet_final, parcours:dict) -> list:
    """Renvoie une liste des sommets permettant d'aller de initial vers final"""
 
    return []
 
 
# Programme principal =================================================
 
if __name__ == "__main__":
 
    s = (0, 1, 2, 3, 4)                      # Ensemble s des sommets du graphe 
    a = ((0,1), (0,2), (1,3), (2,3), (3,4))  # Ensemble a des arêtes
    g = (s, a)                               # Graphe défini comme un couple
 
    graphe = creer_graphedico_no_np(g)
    print("Graphe en tant que dictionnaire :")
    print(graphe)
    

Correction ?

...CORRECTION...

"""Implémentation du parcours en largeur"""
 
# Fonctions =====================================================
 
def creer_graphedico_no_np(g:tuple) -> dict[int, list]:
    """Renvoie un graphe-dico à partir du graphe-couple (non orienté, non pondéré)"""
 
    s, a = g                 # Désempaquetage de s et a depuis g
    graphe = {}              # Dictionnaire vide
 
    for sommet in s:         # pour chaque sommet de l'ensemble des sommets
        graphe[sommet] = []  # on crée une clé correspond au sommet menant à une liste vide
    for arete in a:          # pour chaque arête présente dans l'ensemble a
        s1, s2 = arete         # Désempaquetage de s1 et s2 depuis le couple arete
        graphe[s1].append(s2)  # Rajout de s2 dans la liste d'adj. de s1
        graphe[s2].append(s1)  # Rajout de s1 dans la liste d'adj. de s2
 
    return graphe
 
def largeur_d_abord_v1(g:dict[int, list], s:int) -> dict:
    """Renvoie un dictionnaire contenant la distance à s et le parent de chaque sommet"""
 
    return {}
 
def donner_chemin(sommet_initial, sommet_final, parcours:dict) -> list:
    """Renvoie une liste des sommets permettant d'aller de initial vers final"""
 
    return []
 
 
# Programme principal =================================================
 
if __name__ == "__main__":
 
    s = (0, 1, 2, 3, 4)                      # Ensemble s des sommets du graphe 
    a = ((0,1), (0,2), (1,3), (2,3), (3,4))  # Ensemble a des arêtes
    g = (s, a)                               # Graphe défini comme un couple
 
    graphe = creer_graphedico_no_np(g)
    print("Graphe en tant que dictionnaire :")
    print(graphe)
    

3 - Implémentation de l'algorithme de parcours en largeur

⇩ ⇧ ⤊

03° Considérons que le graphe g est caractérisé par ceci :


>>> graphe = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3]}

Questions

Quel code Python permet de récupérer une à une tous les sommets depuis le dictionnaire g ?
Quel code Python permet de récupérer une à une toutes les listes d'adjacence des les sommets depuis le dictionnaire g ?
Quel code Python permet de récupérer un par un à la fois un sommet et sa liste d'adjacence depuis le dictionnaire g ?

Correction ?

...CORRECTION...


for sommet in g.keys():

for liste in g.values():

for sommet, liste in g.items():

04° Pour réaliser le parcours en largeur, va-t-on avoir besoin d'un File ou d'une Pile ?

Correction ?

...CORRECTION...

Une File.

05° Lire le début de la documentation de façon à vous souvenir comment utiliser facilement une File en Python.

06° Compléter la fonction de parcours de façon à la faire fonctionner correctement :

"""Implémentation du parcours en largeur pour :
 
* un graphe implémenté sous forme d'un graphe-dico  {sommet:liste d'adjacence}
* une file muable implémentée via la classe Deque du module collections
    -> nouvelleFile() avec file = collections.deque()
    -> enfiler()      avec file.append(x)
    -> defiler()      avec file.popleft()
    -> lireAvant()    avec file[0]
    -> estVide()      avec file
 
Le module comporte les fonctions :
-> creer_graphedico_no_np(g:tuple) -> dict[int, list]
-> largeur_d_abord_v1(g:dict[int, list], s:int) -> dict
-> donner_chemin(sommet_initial, sommet_final, parcours:dict) -> list
 
 
 
"""
 
# Importations =================================================
 
import collections
import math
 
# Constantes ===================================================
 
BLANC = 0
GRIS = 1
NOIR = 2
INFINI = math.inf
 
# Fonctions =====================================================
 
def creer_graphedico_no_np(g:tuple) -> dict[int, list]:
    """Renvoie un graphe-dico à partir du graphe-couple (non orienté, non pondéré)"""
 
    s, a = g                 # Désempaquetage de s et a depuis g
    graphe = {}              # Dictionnaire vide
 
    for sommet in s:         # pour chaque sommet de l'ensemble des sommets
        graphe[sommet] = []  # on crée une clé correspond au sommet menant à une liste vide
    for arete in a:          # pour chaque arête présente dans l'ensemble a
        s1, s2 = arete         # Désempaquetage de s1 et s2 depuis le couple arete
        graphe[s1].append(s2)  # Rajout de s2 dans la liste d'adj. de s1
        graphe[s2].append(s1)  # Rajout de s1 dans la liste d'adj. de s2
 
    return graphe
 
def largeur_d_abord_v1(g:dict[int, list], s:int) -> dict:
    """Renvoie un dictionnaire contenant la distance à s et le parent de chaque sommet"""
 
    parcours = {}
 
    # on initialise tous les sommets
    for sommet in g.keys():
        parcours[sommet] = {}
        parcours[...]['couleur'] = ...
        parcours[...]['distance'] = ...
        parcours[...]['parent'] = ...
 
    # on initialise le sommet de départ
    parcours[...]["couleur"] = ...
    parcours[...]["distance"] = ...
 
    # on crée la file et on y place le sommet origine
    a_traiter = collections.deque()  # on crée un nouvelle file muable
    ...              # on enfile s dans la file muable
 
    # on sort et active un sommet à la fois de la file
    while a_traiter:   # tant que la file des sommets à traiter n'est pas vide
        u = ...        # on défile le prochain sommet à traiter
        for ... in ...:   # pour chaque sommet v dans la liste d'adjacence de u
            if parcours[...]["couleur"] == ...:
                parcours[...]["couleur"] = ...
                parcours[...]["distance"] = ...
                parcours[...]["parent"] = ...
                ...
        parcours[...]["couleur"] = ...
 
    # on renvoie le résultat du parcours
    return ...
 
def donner_chemin(sommet_initial, sommet_final, parcours:dict) -> list:
    """Renvoie une liste des sommets permettant d'aller de initial vers final"""
 
    reponse = []
 
    if sommet_initial in parcours.keys() and sommet_final in parcours.keys():
        sommet = sommet_final
        while sommet is not None:
            reponse.append(sommet)
            sommet = parcours[sommet]['parent']
 
    inversion = []
    while reponse:
        inversion.append(reponse.pop())
    return inversion
 
 
# Programme principal =================================================
 
if __name__ == "__main__":
 
    s = (0, 1, 2, 3, 4)                      # Ensemble s des sommets du graphe 
    a = ((0,1), (0,2), (1,3), (2,3), (3,4))  # Ensemble a des arêtes
    g = (s, a)                               # Graphe défini comme un couple
 
    graphe = creer_graphedico_no_np(g)
    print("Graphe en tant que dictionnaire :")
    print(graphe)
 
    parcours = largeur_d_abord_v1(graphe, 0)
    print("\nRésultat du parcours en largeur d'abord")
    for couple in parcours.items():
        print(couple)
 
    print("\nRecherche du chemin entre 0 et 3")
    print(donner_chemin(0, 3, parcours))

Correction ?

...CORRECTION...

"""Implémentation du parcours en largeur pour :
 
* un graphe implémenté sous forme d'un graphe-dico  {sommet:liste d'adjacence}
* une file muable implémentée via la classe Deque du module collections
    -> nouvelleFile() avec file = collections.deque()
    -> enfiler()      avec file.append(x)
    -> defiler()      avec file.popleft()
    -> lireAvant()    avec file[0]
    -> estVide()      avec file
 
Le module comporte les fonctions :
-> creer_graphedico_no_np(g:tuple) -> dict[int, list]
-> largeur_d_abord_v1(g:dict[int, list], s:int) -> dict
-> donner_chemin(sommet_initial, sommet_final, parcours:dict) -> list
 
 
 
"""
 
# Importations =================================================
 
import collections
import math
 
# Constantes ===================================================
 
BLANC = 0
GRIS = 1
NOIR = 2
INFINI = math.inf
 
# Fonctions =====================================================
 
def creer_graphedico_no_np(g:tuple) -> dict[int, list]:
    """Renvoie un graphe-dico à partir du graphe-couple (non orienté, non pondéré)"""
 
    s, a = g                 # Désempaquetage de s et a depuis g
    graphe = {}              # Dictionnaire vide
 
    for sommet in s:         # pour chaque sommet de l'ensemble des sommets
        graphe[sommet] = []  # on crée une clé correspond au sommet menant à une liste vide
    for arete in a:          # pour chaque arête présente dans l'ensemble a
        s1, s2 = arete         # Désempaquetage de s1 et s2 depuis le couple arete
        graphe[s1].append(s2)  # Rajout de s2 dans la liste d'adj. de s1
        graphe[s2].append(s1)  # Rajout de s1 dans la liste d'adj. de s2
 
    return graphe
 
def largeur_d_abord_v1(g:dict[int, list], s:int) -> dict:
    """Renvoie un dictionnaire contenant la distance à s et le parent de chaque sommet"""
 
    parcours = {}
 
    # on initialise tous les sommets
    for sommet in g.keys():
        parcours[sommet] = {}
        parcours[sommet]['couleur'] = BLANC
        parcours[sommet]['distance'] = INFINI
        parcours[sommet]['parent'] = None
 
    # on initialise le sommet de départ
    parcours[s]["couleur"] = GRIS
    parcours[s]["distance"] = 0
 
    # on crée la file et on y place le sommet origine
    a_traiter = collections.deque()  # on crée un nouvelle file muable
    a_traiter.append(s)              # on enfile s dans la file muable
 
    # on sort et active un sommet à la fois de la file
    while a_traiter:   # tant que la file des sommets à traiter n'est pas vide
        u = a_traiter.popleft()        # on défile le prochain sommet à traiter
        for v in g[u]:   # pour chaque sommet v dans la liste d'adjacence de u
            if parcours[v]["couleur"] == BLANC:
                parcours[v]["couleur"] = GRIS
                parcours[v]["distance"] = parcours[u]["distance"] + 1
                parcours[v]["parent"] = u
                a_traiter.append(v)
        parcours[u]["couleur"] = NOIR
 
    # on renvoie le résultat du parcours
    return parcours
 
def donner_chemin(sommet_initial, sommet_final, parcours:dict) -> list:
    """Renvoie une liste des sommets permettant d'aller de initial vers final"""
 
    reponse = []
 
    if sommet_initial in parcours.keys() and sommet_final in parcours.keys():
        sommet = sommet_final
        while sommet is not None:
            reponse.append(sommet)
            sommet = parcours[sommet]['parent']
 
    inversion = []
    while reponse:
        inversion.append(reponse.pop())
    return inversion
 
 
# Programme principal =================================================
 
if __name__ == "__main__":
 
    s = (0, 1, 2, 3, 4)                      # Ensemble s des sommets du graphe 
    a = ((0,1), (0,2), (1,3), (2,3), (3,4))  # Ensemble a des arêtes
    g = (s, a)                               # Graphe défini comme un couple
 
    graphe = creer_graphedico_no_np(g)
    print("Graphe en tant que dictionnaire :")
    print(graphe)
 
    parcours = largeur_d_abord_v1(graphe, 0)
    print("\nRésultat du parcours en largeur d'abord")
    for couple in parcours.items():
        print(couple)
 
    print("\nRecherche du chemin entre 0 et 3")
    print(donner_chemin(0, 3, parcours))

07° Expliquer comment fonctionne la fonction donner_chemin() qui permet de récupérer le chemin le plus court entre deux sommets.

4 - Plus simple

⇩ ⇧ ⤊

On peut en réalité se passer de la gestion des couleurs.

Il suffit de rajouter un tableau lié au parcours : dès qu'on découvre un sommet, on le place dans ce tableau qu'on pourrait nommé decouverts qui liste les sommets découverts.

Un sommet est BLANC s'il n'est pas dans decouverts.

Un sommet est GRIS ou NOIR s'il est dans decouverts.

Comment distinguer GRIS et NOIR ? A l'aide de la File des sommets a_traiter.

Un sommet est BLANC s'il n'est pas dans decouverts.
Un sommet est GRIS s'il est dans decouverts et a_traiter.
Un sommet est NOIR s'il est dans decouverts mais plus dans a_traiter.

08° Compléter la fonction de parcours de façon à la faire fonctionner correctement sans gestion directe de la COULEUR :

"""Implémentation du parcours en largeur pour :
 
* un graphe implémenté sous forme d'un graphe-dico  {sommet:liste d'adjacence}
* une file muable implémentée via la classe deque du module collections
    -> nouvelleFile() avec file = collections.deque()
    -> enfiler()      avec file.append(x)
    -> defiler()      avec file.popleft()
    -> lireAvant()    avec file[0]
    -> estVide()      avec file
 
Le module comporte les fonctions :
-> creer_graphedico_no_np(g:tuple) -> dict[int, list]
-> largeur_d_abord_v1(g:dict[int, list], s:int) -> dict
-> donner_chemin(sommet_initial, sommet_final, parcours:dict) -> list
 
"""
 
# Importations =================================================
 
import collections
 
 
# 2 - déclaration des fonctions ================================
 
def largeur_d_abord_v2(g:dict[int, list], s:int) -> dict:
    """Renvoie un dictionnaire contenant la distance à s et le parent de chaque sommet"""
 
    decouverts = []              # on initialise la liste des sommets découverts
    parcours = {}                # on initialise le dict des infos sur le parcours
 
    # on initialise le sommet de départ
    decouverts.append(s)         # on signale qu'on a découvert ce sommet
    parcours[s] = {}
    parcours[s]["distance"] = 0   # et qu'il est à distance 0 de lui-même
    parcours[s]["parent"] = None  # et qu'il est la racine de l'arbre de parcours
 
    # on crée la file et on y place le sommet origine
    a_traiter = ...          # on crée un nouvelle file muable illimitée en taille
    ...          # on enfile s dans la file muable
 
    # on sort et active un sommet à la fois de la file
    while a_traiter:             # tant que la file des sommets à traiter n'est pas vide
        u = ...  # on défile le prochain sommet u à traiter
        for ... in g[u]:           # pour chaque sommet v dans la liste d'adjacence de u
            if v not in ...:             # si v n'est pas encore decouvert
                ...           # dire que v est découvert
                parcours[v] = {}
                parcours[...]["distance"] = ...
                parcours[...]["parent"] = ...
                ...             # on rajoute v dans la file des sommets à traiter
        # à partir d'ici u est NOIR car dans decouvert mais plus dans a_traiter
 
    # on renvoie le résultat du parcours
    return parcours
 
def donner_chemin(sommet_initial, sommet_final, parcours:dict) -> list:
    """Renvoie une liste des sommets permettant d'aller de initial vers final"""
 
    reponse = []
 
    if sommet_initial in parcours.keys() and sommet_final in parcours.keys():
        sommet = sommet_final
        while sommet is not None:
            reponse.append(sommet)
            sommet = parcours[sommet]['parent']
 
    inversion = []
    while reponse:
        inversion.append(reponse.pop())
    return inversion
 
 
# Programme de test =================================================
 
if __name__ == "__main__":
 
    graphe_test = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3]}
 
    print("Graphe en tant que dictionnaire :")
    print(graphe_test)
 
    parcours = largeur_d_abord_v2(graphe_test, 0)
    print("\nRésultat du parcours en largeur d'abord")
    for couple in parcours.items():
        print(couple)
 
    print("\nRecherche du chemin entre 0 et 3")
    print(donner_chemin(0, 3, parcours))

Correction ?

...CORRECTION...

"""Implémentation du parcours en largeur pour :
 
* un graphe implémenté sous forme d'un graphe-dico  {sommet:liste d'adjacence}
* une file muable implémentée via la classe deque du module collections
    -> nouvelleFile() avec file = collections.deque()
    -> enfiler()      avec file.append(x)
    -> defiler()      avec file.popleft()
    -> lireAvant()    avec file[0]
    -> estVide()      avec file
 
Le module comporte les fonctions :
-> creer_graphedico_no_np(g:tuple) -> dict[int, list]
-> largeur_d_abord_v1(g:dict[int, list], s:int) -> dict
-> donner_chemin(sommet_initial, sommet_final, parcours:dict) -> list
 
"""
 
# Importations =================================================
 
import collections
 
 
# 2 - déclaration des fonctions ================================
 
def largeur_d_abord_v2(g:dict[int, list], s:int) -> dict:
    """Renvoie un dictionnaire contenant la distance à s et le parent de chaque sommet"""
 
    decouverts = []              # on initialise la liste des sommets découverts
    parcours = {}                # on initialise le dict des infos sur le parcours
 
    # on initialise le sommet de départ
    decouverts.append(s)         # on signale qu'on a découvert ce sommet
    parcours[s] = {}
    parcours[s]["distance"] = 0   # et qu'il est à distance 0 de lui-même
    parcours[s]["parent"] = None  # et qu'il est la racine de l'arbre de parcours
 
    # on crée la file et on y place le sommet origine
    a_traiter = collections.deque()          # on crée un nouvelle file muable illimitée en taille
    a_traiter.append(s)          # on enfile s dans la file muable
 
    # on sort et active un sommet à la fois de la file
    while a_traiter:             # tant que la file des sommets à traiter n'est pas vide
        u = a_traiter.popleft()  # on défile le prochain sommet u à traiter
        for v in g[u]:           # pour chaque sommet v dans la liste d'adjacence de u
            if v not in decouverts:             # si v n'est pas encore decouvert
                decouverts.append(v)            # dire que v est découvert
                parcours[v] = {}
                parcours[v]["distance"] = parcours[u]["distance"] + 1
                parcours[v]["parent"] = u
                a_traiter.append(v)             # on rajoute v dans la file des sommets à traiter
        # à partir d'ici u est NOIR car dans decouvert mais plus dans a_traiter
 
    # on renvoie le résultat du parcours
    return parcours
 
def donner_chemin(sommet_initial, sommet_final, parcours:dict) -> list:
    """Renvoie une liste des sommets permettant d'aller de initial vers final"""
 
    reponse = []
 
    if sommet_initial in parcours.keys() and sommet_final in parcours.keys():
        sommet = sommet_final
        while sommet is not None:
            reponse.append(sommet)
            sommet = parcours[sommet]['parent']
 
    inversion = []
    while reponse:
        inversion.append(reponse.pop())
    return inversion
 
 
# Programme de test =================================================
 
if __name__ == "__main__":
 
    graphe_test = {0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2, 4], 4: [3]}
 
    print("Graphe en tant que dictionnaire :")
    print(graphe_test)
 
    parcours = largeur_d_abord_v2(graphe_test, 0)
    print("\nRésultat du parcours en largeur d'abord")
    for couple in parcours.items():
        print(couple)
 
    print("\nRecherche du chemin entre 0 et 3")
    print(donner_chemin(0, 3, parcours))

09° Réaliser cette troisième version qui ne sert à rien mais qui affiche simplement le nom des sommets découverts au fur et à mesure de l'exploration. Il s'agit d'une version simplifiée de la fonction précédente. Tentez de n'utiliser que la version algorithmique au pire, sans regarder directement le code Python de la question précédente.

Inutile donc de créer un dictionnaire stockant les informations obtenues lors du parcours. C'est une fonction qui ne sert à rien.

...
 
def largeur_d_abord_v3(g:dict[int, list], s:int) -> None:
    """Affiche le numéro des sommets rencontrés lors de l'exploration"""
 
    pass
 
...

Correction ?

...CORRECTION...

...
 
def largeur_d_abord_v3(g:dict[int, list], s:int) -> None:
    """Affiche le numéro des sommets rencontrés lors de l'exploration"""
 
    decouverts = []              # on initialise la liste des sommets découverts
 
    # on initialise le sommet de départ
    decouverts.append(s)         # on signale qu'on a découvert ce sommet
 
    # on crée la file et on y place le sommet origine
    a_traiter = collections.deque()          # on crée un nouvelle file muable illimitée en taille
    a_traiter.append(s)          # on enfile s dans la file muable
 
    # on sort et active un sommet à la fois de la file
    while a_traiter:             # tant que la file des sommets à traiter n'est pas vide
        u = a_traiter.popleft()  # on défile le prochain sommet u à traiter    
        print(u)
        for v in g[u]:           # pour chaque sommet v dans la liste d'adjacence de u
            if v not in decouverts:             # si v n'est pas encore decouvert
                decouverts.append(v)            # dire que v est découvert  
                a_traiter.append(v)             # on rajoute v dans la file des sommets à traiter
        # à partir d'ici u est NOIR car dans decouvert mais plus a_traiter
 
...

10° Modifier votre graphe de façon à l'agrandir un peu. Vérifier que vos fonctions de parcours en version 1 et 2 fonctionnent encore.

Enfin, rajouter quelques sommets de façon à rendre le graphe non-connexe : il doit être composé de deux sous-graphes qui ne se peuvent pas communiquer entre eux. Question : le parcours en largeur partant d'un côté permet-il d'apprendre des choses sur l'autre côté ?

5 - FAQ

⇩ ⇧ ⤊

Et on fait comment sur un graphe pondéré ?

On applique l'algorithme de Dijkstra.

Activité publiée le 09 04 2024
Dernière modification : 09 04 2024
Auteur : ows. h.

⏪

⏫

⏩