Matrice d'Adjacence → Liste d'Adjacence
Algorithmique classique
Enonce
Convertir une matrice d'adjacence (0/1) en dictionnaire de listes d'adjacence. Les sommets sont numérotés de 0 à n-1.
Signature attendue
def matrice_vers_liste(M: list) -> dict:Exemple
matrice_vers_liste([[0,1,1,0],[1,0,0,1],[1,0,0,1],[0,1,1,0]])→{0: [1, 2], 1: [0, 3], 2: [0, 3], 3: [1, 2]}
📖 Rappel de cours
La matrice porte un 1 en (i, j) s'il existe une arête ; la liste d'adjacence associe à chaque sommet la liste de ses voisins. On passe de l'une à l'autre en parcourant.
⚠ Le piège : La matrice occupe n² cases quel que soit le nombre d'arêtes, la liste seulement n + m. Sur un graphe creux — le cas courant — la liste gagne largement.
← Exercices Python pour la prépa — CPGE scientifique et ECG
Exercices du meme theme
- Nombre de Noeuds d'un Arbre
- Recherche dans un ABR
- Arbre Binaire Miroir
- Parcours en Profondeur (DFS)
- Parcours en Largeur (BFS)
- Degré des Sommets
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.