Matrice et listes d'adjacence
Représenter un graphe en machine : matrice d'adjacence, listes d'adjacence, liste d'arêtes, matrice d'incidence, coût mémoire et coût des opérations, puissances de la matrice.
- 23 cartes
- 4 thèmes
- Gratuit
Le programme, thème par thème
Le poids de chaque thème suit celui que lui donne l'examen.
- Notions
- Questions
- Ranger et relier
- Les chiffres
Quelques cartes du deck
Matrice d'adjacence : de quoi s'agit-il ?
Voir la réponse
Tableau carré n × n dont la case (i, j) vaut 1 s'il y a une arête (ou un arc) de i vers j, et 0 sinon.
Elle donne la réponse à « i et j sont-ils voisins ? » en une lecture de case. Pour un graphe pondéré, la case porte le poids à la place du 1.
Qu'affiche ce programme ?
```python
aretes = [("A","B"),("A","C"),("C","B")]
adj = {"A": [], "B": [], "C": []}
for u, v in aretes:
adj[u].append(v)
print(adj)`{'A': ['B', 'C'], 'B': [], 'C': ['B']}{'A': ['B', 'C'], 'B': ['A', 'C'], 'C': ['A', 'B']}{'A': ['B', 'C'], 'B': ['A'], 'C': ['A', 'B']}{'A': ['B', 'C'], 'B': ['C'], 'C': []}
Voir la réponse
{'A': ['B', 'C'], 'B': [], 'C': ['B']}Le code n'ajoute que
và la liste deu: chaque couple devient un arc orienté. Pour un graphe non orienté, il faudrait aussiadj[v].append(u); sans cette ligne, B reste sans successeur.Une matrice d'adjacence occupe … cases, alors que des listes d'adjacence occupent ….
Voir la réponse
Une matrice d'adjacence occupe O(n²) cases, alors que des listes d'adjacence occupent O(n + m).
La matrice réserve une case pour chaque paire possible, existante ou non ; les listes ne gardent que les m arêtes réelles.
Listes d'adjacence : de quoi s'agit-il ?
Voir la réponse
Tableau qui associe à chaque sommet la liste de ses voisins (ou de ses successeurs, si les arcs sont orientés).
Elle ne garde que les liaisons qui existent : la mémoire est en O(n + m) et un parcours lit chaque liste une fois.