NSI Terminale
def dict_vers_matrice(g: dict)->list[list]:
"""
Fonction qui renvoie la matrice d'adjacence du graphe
Entrée :
G = le Graphe
Sortie :
liste de listes implémentant la matrice d'adjacence )
"""
sommets = [s for s in g.keys()] # récupération de la liste des sommets ( clés du dictionnaire )
# création de la matrice avec tous ses éléments à 0
# la matrice a autant de lignes/de colonnes qu'il y a de sommets dans le dictionnaire
adjacence = [[0 for j in range(len(g))] for i in range(len(g))]
for i in range(len(adjacence)): # pour chaque ligne de la matrice,
id1 = sommets[i] # id du sommet correspondant à la ligne 'i' dans le tableau 'sommets'
for j in range(len(adjacence[0])): # pour chacune des colonne de la matrice,
id2 = sommets[j] # id du sommet correspondant à la colonne 'j'
if id2 in g[id1]: # si 'j' est dans la liste des voisins de 'i' ...
adjacence[i][j] = 1 # ...on met 1 dans la case [î][j] de la matrice ( sinon, on laisse 0 )
return adjacence
from graphviz import Digraph
def dessine_graphe(g):
d = Digraph() # graphe orienté par défaut, fait apparaître les flèches
for sommet, voisins in g.items(): # parcours du dictionnaire des listes d'adjacences du graphe ( par clé ET valeur )
for voisin in voisins: # parcours des voisins du sommet
if isinstance(voisin, tuple): # graphe pondéré ?
d.edge(sommet , voisin[0], label = voisin[1]) # création d'un arc entre les deux sommets avec label = poids
else:
d.edge(sommet , voisin) # création d'un arc entre les deux sommets, sans label
d.view() # affichage du graphe