Parcourir un graphe

Parcours en profondeur

On revient sur le parcours en profondeur avec une pile.

Le code ci-dessous en cliquant sur « lire la suite »

Version récursive à faire pour lundi

Parcours en largeur

On obtient ce parcours en largeur avec le même algorithme mais en utilisant une file plutôt qu’une pile. A faire pour lundi


Algorithme de Dijkstra : recherche du plus court chemin dans un arbre pondéré

On explique le principe sur cet exemple, dans une version « mathématique » de l’algorithme.
Une autre version et une implémentation à venir la semaine prochaine.

Pour lundi, même travail sur ce graphe pour trouver le chemin le plus court pour aller de A à I:

Application au routage

On introduit à l’oral les deux logiques des routages avec

  • le protocole RIP (Routing Information Protocol) proche d’un parcours en largeur où l’on compte les sauts
  • le protocole OSPF (Open Shortest Path First) proche d’une recherche du plus court chemin avec l’algorithme de Dijkstra.

AU FINAL, POUR LUNDI 7 juin :
-> Depuis lundi, créer une matrice d’adjacence pour implémenter le même graphe et une liste des sommets. Répondre aux questions du TP de lundi avec cette nouvelle implémentation
-> Implémenter le parcours en largeur avec une file
-> Implémenter le parcours en profondeur en version récursive
-> Faire l’exercice « Dijkstra » sur le dernier graphe
-> Courage !


"""parcours en profondeur d'un graphe"""
from primitives import *

# clés : sommets
# valeurs : liste d'adjacence du sommet en clé
g = {'A' : ['B', 'C', 'H'],
     'B' : ['A', 'I'],
     'C' : ['A', 'D', 'E'],
     'D' : ['C', 'E'],
     'E' : ['C', 'D', 'G'],
     'F' : ['G', 'I'],
     'G' : ['E', 'F', 'H'],
     'H' : ['A', 'G', 'I'],
     'I' : ['B', 'F', 'H']}

def parcours_profondeur_pile(g, s):
    # une liste des sommets visités
    liste_marques = []
    # une pile vide
    P = creer_pile_vide()
    # On empile le sommet de départ
    empiler(P, s)
    # tant que la pile n'est pas vide
    while not est_pile_vide(P):
        # je dépile un sommet
        sommet = depiler(P)
        # je visite le sommet
        if sommet not in liste_marques:
            liste_marques.append(sommet)
        # j'empile ses voisins non visités
        for elt in g[sommet]:
            # si le voisin n'est pas visité
            if elt not in liste_marques:
                # on l'empile
                empiler(P, elt)
    # je renvoie mon parcours
    return liste_marques

print(parcours_profondeur_pile(g, 'H'))

N'hésitez-pas à poser une question, ou faire avancer le schmilblick

Entrez vos coordonnées ci-dessous ou cliquez sur une icône pour vous connecter:

Logo WordPress.com

Vous commentez à l’aide de votre compte WordPress.com. Déconnexion /  Changer )

Photo Google

Vous commentez à l’aide de votre compte Google. Déconnexion /  Changer )

Image Twitter

Vous commentez à l’aide de votre compte Twitter. Déconnexion /  Changer )

Photo Facebook

Vous commentez à l’aide de votre compte Facebook. Déconnexion /  Changer )

Connexion à %s

Ce site utilise Akismet pour réduire les indésirables. En savoir plus sur la façon dont les données de vos commentaires sont traitées.