Arbre couvrant⚓︎
On considère un graphe fini, connexe, non orienté, représenté par une liste d'adjacence. Cette liste d'adjacence est constituée de listes qui en Python peuvent être regroupées dans un dictionnaire ou un tableau. Chacune des listes contient les voisins d'un sommet. Dans ce exercice, on utilisera un dictionnaire.
On suppose les \(n\) sommets numérotés de \(0\) à \(n-1\).
On appelle graphe partiel d'un graphe \(G\), un graphe obtenu en supprimant certaines arêtes du graphe \(G\). Un graphe partiel contient les mêmes sommets que le graphe \(G\).
On définit ici un arbre comme un graphe fini, connexe, non orienté, sans cycle.
L'objectif est d'obtenir un arbre couvrant d'un graphe \(G\), c'est-à-dire un arbre qui est un graphe partiel de \(G\). Il y a plusieurs possibilités.
Exemple
De gauche à droite:
-
un graphe représenté par le dictionnaire
g = {0: [1, 2, 3], 1: [0, 4, 5], 2: [0, 3, 4], 3: [0, 2, 4], 4: [1, 2, 3, 5], 5: [1, 4, 6], 6: [5]}. -
le même graphe avec en rouge les arêtes qui sont conservées.
-
l'arbre obtenu représenté par le dictionnaire
{0: [1, 2, 3], 1: [0, 4, 5], 2: [0], 3: [0], 4: [1], 5: [1, 6], 6: [5]}.
Il s'agit d'un arbre parmi plusieurs possibles. Par exemple, on aurait pu supprimer l'arête entre les sommets 0 et 3 et garder à la place l'arête entre les sommets 2 et 3.
Question
Compléter le code de la fonction arbre_couvrant qui prend en paramètre un dictionnaire représentant un graphe (supposé fini, connexe, non orienté) et renvoie un dictionnaire représentant un arbre couvrant.
Pour chaque dictionnaire, les clés sont les sommets, (chaque sommet est représenté par son numéro), et chaque valeur associée à une clé est la liste des voisins du sommet.
On utilisera un parcours en largeur.
On pourra utiliser une file
Pour représenter une file, on peut se servir de la fonction deque qui est déjà importée depuis le module collections.
On crée une file vide avec l'instruction file = deque().
Pour insérer un élément elt dans une file, on écrit file.append(elt). Pour défiler un élément d'une file non vide et l'affecter, on écrit elt = file.popleft().
On obtient la longueur d'une file avec la fonction len.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)