Implémentation des graphes

Nous avons vu dans le cours sur les graphes, deux façons de représenter un graphe : par matrice d'adjacence ou par liste d'adjacence. Nous allons utiliser ces deux implémentations ici.

Matrice d'adjacence

Nous utiliserons le même graphe que le précédent :

1) Créez en Python la matrice d'adjacence de ce graphe.

graphe = [[0,1,1,0,0,0,0,0,0],
          [1,0,0,1,1,0,0,0,0],
          [1,0,0,0,1,1,1,0,0],
          [0,1,0,0,0,0,0,1,0],
          [0,1,1,0,0,0,0,1,0],
          [0,0,1,0,0,0,0,0,1],
          [0,0,1,0,0,0,0,0,1],
          [0,0,0,1,1,0,0,0,1],
          [0,0,0,0,0,1,1,1,0]]

2) (Dificile) Proposez une fonction matrice_largeur permettant de parcourir en largeur ce graphe. On utilisera une liste pour enregistrer les nœuds visités.

def matrice_largeur(graphe):
    alpha = "ABCDEFGHI" # Pour faire correspondre l'indice à la lettre
    visite = [0] # On commence par le nœud A (indice 0)
    f = [0] # On commence par le nœud A (indice 0)
    n = len(graphe) # taille de la matrice
    while f != []:
        x = f.pop(0)
        print(alpha[x]) # On affiche la lettre
        for i in range(n): # On parcourt les nœuds
            if graphe[x][i] == 1 and i not in visite: # Si le nœud est adjacent à x et est non visité
                visite.append(i) # On l'ajoute à visite
                f.append(i) # On l'ajoute à la liste des nœuds à visiter

3) (Plus dificile) Proposez une fonction matrice_profondeur permettant de parcourir en profondeur ce graphe.

def matrice_profondeur(graphe, indice, visite): # visite doit etre une liste vide
    alpha = "ABCDEFGHI" # Pour faire correspondre l'indice à la lettre
    n = len(graphe) # taille de la matrice
    visite.append(indice)
    print(alpha[indice]) # On affiche le nœud
    for i in range(n): # On parcourt les nœuds
        if graphe[indice][i] == 1 and i not in visite: # Si le nœud est adjacent à indice et est non visité
            matrice_profondeur(graphe,i,visite)

Liste d'adjacence

Nous utiliserons ici le même graphe que précédement.

4) Créez en Python les listes d'adjacence de ce graphe. (On utilisera un tableau à deux dimensions)

5) (Dificile) Proposez une fonction listes_largeur permettant de parcourir en largeur ce graphe. On utilisera une liste pour enregistrer les nœuds visités.

6) (Plus dificile) Proposez une fonction listes_profondeur permettant de parcourir en profondeur ce graphe.