Graphes (2)

Flash / TP

Implémentez ce graphe avec un dictionnaire dont les clés sont les sommets et les valeurs les listes d’adjacence de ces sommets

Écrire des fonctions pour :

  1. Rajouter un sommet K
  2. Rajouter une arête:
    • entre A et E
    • entre B et C
    • entre K et H
    • entre K et B
    • entre K et F
  3. Supprimer l’arête entre A et C
  4. Supprimer le sommet I (et toutes les arêtes de sommet I)

Les codes ci-dessous en cliquant sur « lire la suite »

POUR LUNDI 7 juin :
Dans un autre fichier, créer la matrice d’adjacence pour implémenter le même graphe et une liste des sommets. Répondre aux mêmes questions avec cette nouvelle implémentation pour vendredi lundi.


Suite du cours : parcours en profondeur

  • version itérative avec une pile, sera repris vendredi

"""Une implémentation de graphe par dictionnaire
et listes d'adjacence pour chaque sommet"""

# 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 ajouter_sommet(g, s):
    """
    ajoute le sommet s au graphe g
    @param g: dict
    @param s: string
    @return: None
    """
    g[s] = []

ajouter_sommet(g, 'K')
# print(g)

def ajouter_arete(g, s1, s2):
    """
    ajoute une arête dans g liant s1 à s2
    @param g: dict
    @param s1: string
    @param s2: string
    @return: None
    """

    g[s1].append(s2)
    g[s2].append(s1)

ajouter_arete(g, 'A','E')
# print(g['A'])
# print(g['E'])
ajouter_arete(g, 'B','C')
ajouter_arete(g, 'H','K')
ajouter_arete(g, 'B','K')
ajouter_arete(g, 'K', 'F')

def supprimer_arete(g, s1, s2):
    """
    supprime une arête dans g liant s1 à s2
    @param g: dict
    @param s1: string
    @param s2: string
    @return: None
    """

    g[s1].remove(s2)
    g[s2].remove(s1)

print('C' in g['A']) # True
print('A' in g['C']) # True
supprimer_arete(g, 'A', 'C')
print('C' in g['A']) # False
print('A' in g['C']) # False

def supprimer_sommet(g, s):
    """
    Supprime s et toutes ses arêtes de g
    @param g: dict
    @param s: string
    @return: None
    """
    # suppression des arêtes
    for e in g[s]:
        # pour chaque sommet e
        # on enlève s de la liste
        g[e].remove(s)

    # suppression du sommet
    del g[s]

print(g)
supprimer_sommet(g, 'I')
print(g)

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.