Fiche d'exercices : Graphes
Important ⚠️
Consignes importantes
Pour tous les exercices :
- Dessinez les graphes pour mieux visualiser les problèmes
- Précisez si le graphe est orienté ou non orienté
- Indiquez la complexité de vos algorithmes
- Testez vos implémentations avec plusieurs exemples
- Gérez les cas particuliers (graphe vide, sommet isolé, etc.)
Découverte 🌱
Vocabulaire des graphes
Définissez les termes suivants avec des exemples :
- Sommet et Arête
- Graphe orienté vs non orienté
- Degré d'un sommet
- Chemin et Cycle
- Graphe connexe
- Graphe pondéré
Définitions :
- Sommet : nœud du graphe (ex: ville). Arête : lien entre deux sommets (ex: route)
- Orienté : arêtes avec direction (→). Non orienté : arêtes bidirectionnelles (—)
- Degré : nombre d'arêtes connectées à un sommet
- Chemin : séquence de sommets reliés. Cycle : chemin qui revient au point de départ
- Connexe : il existe un chemin entre toute paire de sommets
- Pondéré : chaque arête a un poids (distance, coût, temps...)
Exemples concrets :
- Réseau routier : villes (sommets), routes (arêtes), distances (poids)
- Réseau social : personnes (sommets), amitiés (arêtes)
- Internet : serveurs (sommets), connexions (arêtes orientées)
- Molécule : atomes (sommets), liaisons (arêtes)
Découverte 🌱
Modélisation avec des graphes
Pour chaque situation, proposez une modélisation par graphe :
- Un réseau de transport en commun
- Les prérequis entre cours universitaires
- Un tournoi de tennis
- Les pages web et leurs liens
- Un labyrinthe
Pour chaque cas, précisez : orienté/non orienté, pondéré/non pondéré, et justifiez.
Modélisations :
- Transport en commun
- Sommets : stations/arrêts
- Arêtes : liaisons directes
- Non orienté (bidirectionnel), pondéré (temps/distance)
- Prérequis de cours
- Sommets : cours
- Arêtes : relation de prérequis
- Orienté (A → B = A prérequis de B), non pondéré
- Tournoi de tennis
- Sommets : joueurs
- Arêtes : matchs joués
- Orienté (A → B = A a battu B), pondéré (score)
- Pages web
- Sommets : pages web
- Arêtes : liens hypertextes
- Orienté (lien unidirectionnel), non pondéré
- Labyrinthe
- Sommets : intersections/cases
- Arêtes : passages possibles
- Non orienté (bidirectionnel), non pondéré
Facile 🟢
Propriétés d'un graphe
Soit le graphe non orienté suivant :
A ---- B ---- C | | | D ---- E ---- F
Calculez :
- Le nombre de sommets et d'arêtes
- Le degré de chaque sommet
- La somme des degrés (que remarquez-vous ?)
- Trouvez tous les chemins de A à F
- Y a-t-il des cycles ? Lesquels ?
Analyse du graphe :
- Nombre de sommets : 6 (A, B, C, D, E, F)
Nombre d'arêtes : 7 (AB, BC, AD, BE, CF, DE, EF) - Degrés :
- deg(A) = 2 (connecté à B et D)
- deg(B) = 3 (connecté à A, C et E)
- deg(C) = 2 (connecté à B et F)
- deg(D) = 2 (connecté à A et E)
- deg(E) = 3 (connecté à B, D et F)
- deg(F) = 2 (connecté à C et E)
- Somme des degrés : 2+3+2+2+3+2 = 14
Remarque : La somme des degrés = 2 × nombre d'arêtes (14 = 2×7)
Car chaque arête contribue à 2 degrés (un pour chaque extrémité) - Chemins de A à F :
- A → B → C → F (longueur 3)
- A → B → E → F (longueur 3)
- A → D → E → F (longueur 3)
- A → D → E → B → C → F (longueur 5)
- A → B → E → D → A → B → C → F (avec cycle, longueur 7)
- Cycles :
- A → B → E → D → A (cycle de longueur 4)
- B → C → F → E → B (cycle de longueur 4)
Moyen 🟡
Implémentation avec matrice d'adjacence
Implémentez une classe GrapheMatrice utilisant une matrice d'adjacence.
Méthodes à implémenter :
__init__(nb_sommets, oriente=False)ajouter_arete(i, j, poids=1)supprimer_arete(i, j)est_adjacent(i, j)voisins(i)afficher()
class GrapheMatrice:
def __init__(self, nb_sommets, oriente=False):
"""Crée un graphe avec une matrice d'adjacence"""
self.nb_sommets = nb_sommets
self.oriente = oriente
# Matrice initialisée à 0 (pas d'arête)
self.matrice = [[0 for _ in range(nb_sommets)] for _ in range(nb_sommets)]
def ajouter_arete(self, i, j, poids=1):
"""Ajoute une arête entre les sommets i et j"""
if 0 <= i < self.nb_sommets and 0 <= j < self.nb_sommets:
self.matrice[i][j] = poids
# Si non orienté, ajouter l'arête inverse
if not self.oriente:
self.matrice[j][i] = poids
else:
raise ValueError("Indices de sommets invalides")
def supprimer_arete(self, i, j):
"""Supprime l'arête entre les sommets i et j"""
if 0 <= i < self.nb_sommets and 0 <= j < self.nb_sommets:
self.matrice[i][j] = 0
if not self.oriente:
self.matrice[j][i] = 0
else:
raise ValueError("Indices de sommets invalides")
def est_adjacent(self, i, j):
"""Vérifie si les sommets i et j sont adjacents"""
if 0 <= i < self.nb_sommets and 0 <= j < self.nb_sommets:
return self.matrice[i][j] != 0
return False
def voisins(self, i):
"""Retourne la liste des voisins du sommet i"""
if 0 <= i < self.nb_sommets:
voisins = []
for j in range(self.nb_sommets):
if self.matrice[i][j] != 0:
voisins.append((j, self.matrice[i][j]))
return voisins
return []
def degre(self, i):
"""Calcule le degré du sommet i"""
return len(self.voisins(i))
def afficher(self):
"""Affiche la matrice d'adjacence"""
print("Matrice d'adjacence:")
print(" ", end="")
for j in range(self.nb_sommets):
print(f"{j:3}", end="")
print()
for i in range(self.nb_sommets):
print(f"{i}: ", end="")
for j in range(self.nb_sommets):
print(f"{self.matrice[i][j]:3}", end="")
print()
def afficher_graphe(self):
"""Affiche le graphe sous forme de liste d'adjacence"""
print(f"Graphe {'orienté' if self.oriente else 'non orienté'}:")
for i in range(self.nb_sommets):
voisins = self.voisins(i)
if voisins:
voisins_str = ", ".join([f"{j}({p})" for j, p in voisins])
print(f" {i}: {voisins_str}")
else:
print(f" {i}: (isolé)")
# Test de l'implémentation
if __name__ == "__main__":
# Création d'un graphe non orienté à 4 sommets
g = GrapheMatrice(4, oriente=False)
# Ajout d'arêtes
g.ajouter_arete(0, 1, 5)
g.ajouter_arete(0, 2, 3)
g.ajouter_arete(1, 3, 2)
g.ajouter_arete(2, 3, 1)
# Affichage
g.afficher()
print()
g.afficher_graphe()
# Tests
print(f"\nSommets 0 et 1 adjacents: {g.est_adjacent(0, 1)}")
print(f"Voisins de 0: {g.voisins(0)}")
print(f"Degré de 0: {g.degre(0)}")Moyen 🟡
Implémentation avec liste d'adjacence
Implémentez une classe GrapheListe utilisant un dictionnaire de listes d'adjacence.
Avantage : Plus efficace en mémoire pour les graphes peu denses.
Bonus : Ajoutez une méthode pour convertir vers une matrice d'adjacence.
class GrapheListe:
def __init__(self, oriente=False):
"""Crée un graphe avec des listes d'adjacence"""
self.sommets = {} # dictionnaire : sommet -> liste des voisins
self.oriente = oriente
def ajouter_sommet(self, sommet):
"""Ajoute un sommet au graphe"""
if sommet not in self.sommets:
self.sommets[sommet] = []
def ajouter_arete(self, sommet1, sommet2, poids=1):
"""Ajoute une arête entre deux sommets"""
# S'assurer que les sommets existent
self.ajouter_sommet(sommet1)
self.ajouter_sommet(sommet2)
# Ajouter l'arête (éviter les doublons)
if not any(v == sommet2 for v, p in self.sommets[sommet1]):
self.sommets[sommet1].append((sommet2, poids))
# Si non orienté, ajouter l'arête inverse
if not self.oriente:
if not any(v == sommet1 for v, p in self.sommets[sommet2]):
self.sommets[sommet2].append((sommet1, poids))
def supprimer_arete(self, sommet1, sommet2):
"""Supprime une arête"""
if sommet1 in self.sommets:
self.sommets[sommet1] = [(v, p) for v, p in self.sommets[sommet1] if v != sommet2]
if not self.oriente and sommet2 in self.sommets:
self.sommets[sommet2] = [(v, p) for v, p in self.sommets[sommet2] if v != sommet1]
def supprimer_sommet(self, sommet):
"""Supprime un sommet et toutes ses arêtes"""
if sommet in self.sommets:
# Supprimer toutes les arêtes vers ce sommet
for s in self.sommets:
self.sommets[s] = [(v, p) for v, p in self.sommets[s] if v != sommet]
# Supprimer le sommet
del self.sommets[sommet]
def voisins(self, sommet):
"""Retourne la liste des voisins d'un sommet"""
return self.sommets.get(sommet, [])
def est_adjacent(self, sommet1, sommet2):
"""Vérifie si deux sommets sont adjacents"""
return any(voisin == sommet2 for voisin, _ in self.voisins(sommet1))
def degre(self, sommet):
"""Retourne le degré d'un sommet"""
return len(self.voisins(sommet))
def nb_sommets(self):
"""Retourne le nombre de sommets"""
return len(self.sommets)
def nb_aretes(self):
"""Retourne le nombre d'arêtes"""
total = sum(len(voisins) for voisins in self.sommets.values())
return total if self.oriente else total // 2
def liste_sommets(self):
"""Retourne la liste des sommets"""
return list(self.sommets.keys())
def afficher(self):
"""Affiche le graphe"""
print(f"Graphe {'orienté' if self.oriente else 'non orienté'}:")
for sommet, voisins in self.sommets.items():
if voisins:
voisins_str = ", ".join([f"{v}({p})" for v, p in voisins])
print(f" {sommet}: {voisins_str}")
else:
print(f" {sommet}: (isolé)")
def vers_matrice(self):
"""Convertit vers une matrice d'adjacence"""
sommets_liste = sorted(self.liste_sommets())
n = len(sommets_liste)
# Créer un mapping sommet -> index
index_map = {sommet: i for i, sommet in enumerate(sommets_liste)}
# Créer la matrice
matrice = [[0 for _ in range(n)] for _ in range(n)]
for sommet, voisins in self.sommets.items():
i = index_map[sommet]
for voisin, poids in voisins:
j = index_map[voisin]
matrice[i][j] = poids
return matrice, sommets_liste
def afficher_matrice(self):
"""Affiche la représentation matricielle"""
matrice, sommets = self.vers_matrice()
print("Matrice d'adjacence:")
print(" ", end="")
for sommet in sommets:
print(f"{sommet:3}", end="")
print()
for i, sommet in enumerate(sommets):
print(f"{sommet:3}: ", end="")
for j in range(len(sommets)):
print(f"{matrice[i][j]:3}", end="")
print()
# Test de l'implémentation
if __name__ == "__main__":
# Création d'un graphe non orienté
g = GrapheListe(oriente=False)
# Ajout d'arêtes (les sommets sont créés automatiquement)
g.ajouter_arete('A', 'B', 5)
g.ajouter_arete('A', 'C', 3)
g.ajouter_arete('B', 'D', 2)
g.ajouter_arete('C', 'D', 1)
# Affichage
g.afficher()
print(f"\nNombre de sommets: {g.nb_sommets()}")
print(f"Nombre d'arêtes: {g.nb_aretes()}")
print(f"\nVoisins de A: {g.voisins('A')}")
print(f"Degré de A: {g.degre('A')}")
print(f"A et B adjacents: {g.est_adjacent('A', 'B')}")
print("\n" + "="*40)
g.afficher_matrice()Difficile 🔴
Comparaison des représentations
Analysez et comparez les deux représentations (matrice vs liste d'adjacence) :
- Implémentez une fonction de benchmark qui mesure le temps d'exécution
- Testez sur des graphes de différentes densités (peu dense, dense)
- Comparez les opérations : ajout d'arête, vérification d'adjacence, parcours des voisins
- Analysez l'utilisation mémoire
Analyse théorique des complexités :
| Opération | Matrice d'adjacence | Liste d'adjacence |
|---|---|---|
| Espace mémoire | O(n²) | O(n + m) |
| Ajouter arête | O(1) | O(1) |
| Supprimer arête | O(1) | O(degré) |
| Vérifier adjacence | O(1) | O(degré) |
| Parcourir voisins | O(n) | O(degré) |
| Parcourir tout le graphe | O(n²) | O(n + m) |
Recommandations :
- Graphe DENSE (m ≈ n²) : Matrice d'adjacence
- Graphe PEU DENSE (m << n²) : Liste d'adjacence
- Vérifications d'adjacence fréquentes : Matrice
- Parcours de voisins fréquents : Liste
Moyen 🟡
Parcours en largeur (BFS)
Implémentez l'algorithme de parcours en largeur (Breadth-First Search).
Fonctionnalités :
- Parcours complet depuis un sommet de départ
- Calcul des distances depuis le sommet de départ
- Reconstruction du chemin le plus court
- Vérification de connexité
from collections import deque
def bfs_parcours(graphe, sommet_depart):
"""Parcours en largeur depuis un sommet de départ"""
visites = set()
file = deque([sommet_depart])
ordre_visite = []
visites.add(sommet_depart)
while file:
sommet_actuel = file.popleft()
ordre_visite.append(sommet_actuel)
# Explorer tous les voisins
for voisin, _ in graphe.voisins(sommet_actuel):
if voisin not in visites:
visites.add(voisin)
file.append(voisin)
return ordre_visite
def bfs_distances(graphe, sommet_depart):
"""Calcule les distances depuis un sommet de départ"""
distances = {sommet_depart: 0}
predecesseurs = {sommet_depart: None}
file = deque([sommet_depart])
while file:
sommet_actuel = file.popleft()
distance_actuelle = distances[sommet_actuel]
# Explorer tous les voisins
for voisin, _ in graphe.voisins(sommet_actuel):
if voisin not in distances:
distances[voisin] = distance_actuelle + 1
predecesseurs[voisin] = sommet_actuel
file.append(voisin)
return distances, predecesseurs
def chemin_plus_court(predecesseurs, sommet_depart, sommet_arrivee):
"""Reconstruit le chemin le plus court"""
if sommet_arrivee not in predecesseurs:
return None # Pas de chemin
chemin = []
sommet_actuel = sommet_arrivee
while sommet_actuel is not None:
chemin.append(sommet_actuel)
sommet_actuel = predecesseurs[sommet_actuel]
return chemin[::-1] # Inverser pour avoir le bon ordre
def est_connexe(graphe):
"""Vérifie si le graphe est connexe"""
if graphe.nb_sommets() == 0:
return True
# Prendre un sommet arbitraire
premier_sommet = next(iter(graphe.liste_sommets()))
# Faire un BFS depuis ce sommet
visites = bfs_parcours(graphe, premier_sommet)
# Le graphe est connexe si tous les sommets sont visités
return len(visites) == graphe.nb_sommets()
def composantes_connexes(graphe):
"""Trouve toutes les composantes connexes"""
tous_visites = set()
composantes = []
for sommet in graphe.liste_sommets():
if sommet not in tous_visites:
# Nouvelle composante
composante = bfs_parcours(graphe, sommet)
composantes.append(composante)
tous_visites.update(composante)
return composantes
# Test de l'implémentation
if __name__ == "__main__":
# Créer un graphe de test
g = GrapheListe(oriente=False)
# Ajouter des arêtes
g.ajouter_arete('A', 'B')
g.ajouter_arete('A', 'C')
g.ajouter_arete('B', 'D')
g.ajouter_arete('C', 'E')
g.ajouter_arete('D', 'E')
g.ajouter_arete('F', 'G') # Composante séparée
print("Graphe:")
g.afficher()
# Test du parcours BFS
print(f"\nParcours BFS depuis A: {bfs_parcours(g, 'A')}")
# Test des distances
distances, predecesseurs = bfs_distances(g, 'A')
print(f"\nDistances depuis A: {distances}")
# Test du chemin le plus court
chemin = chemin_plus_court(predecesseurs, 'A', 'E')
print(f"Chemin le plus court A → E: {chemin}")
# Test de connexité
print(f"\nGraphe connexe: {est_connexe(g)}")
# Composantes connexes
composantes = composantes_connexes(g)
print(f"Composantes connexes: {composantes}")Moyen 🟡
Parcours en profondeur (DFS)
Implémentez l'algorithme de parcours en profondeur (Depth-First Search).
Versions à implémenter :
- Version récursive
- Version itérative avec pile
- Détection de cycles
- Tri topologique (pour graphe orienté)
def dfs_recursif(graphe, sommet_depart, visites=None, ordre_visite=None):
"""Parcours en profondeur récursif"""
if visites is None:
visites = set()
if ordre_visite is None:
ordre_visite = []
visites.add(sommet_depart)
ordre_visite.append(sommet_depart)
# Explorer tous les voisins
for voisin, _ in graphe.voisins(sommet_depart):
if voisin not in visites:
dfs_recursif(graphe, voisin, visites, ordre_visite)
return ordre_visite
def dfs_iteratif(graphe, sommet_depart):
"""Parcours en profondeur itératif avec pile"""
visites = set()
pile = [sommet_depart]
ordre_visite = []
while pile:
sommet_actuel = pile.pop()
if sommet_actuel not in visites:
visites.add(sommet_actuel)
ordre_visite.append(sommet_actuel)
# Ajouter les voisins à la pile (en ordre inverse pour garder l'ordre)
voisins = [v for v, _ in graphe.voisins(sommet_actuel)]
for voisin in reversed(voisins):
if voisin not in visites:
pile.append(voisin)
return ordre_visite
def detecter_cycle_non_oriente(graphe):
"""Détecte un cycle dans un graphe non orienté"""
visites = set()
def dfs_cycle(sommet, parent):
visites.add(sommet)
for voisin, _ in graphe.voisins(sommet):
if voisin not in visites:
if dfs_cycle(voisin, sommet):
return True
elif voisin != parent:
# Arête vers un sommet déjà visité (pas le parent) = cycle
return True
return False
# Tester chaque composante connexe
for sommet in graphe.liste_sommets():
if sommet not in visites:
if dfs_cycle(sommet, None):
return True
return False
def detecter_cycle_oriente(graphe):
"""Détecte un cycle dans un graphe orienté"""
BLANC, GRIS, NOIR = 0, 1, 2
couleurs = {sommet: BLANC for sommet in graphe.liste_sommets()}
def dfs_cycle(sommet):
couleurs[sommet] = GRIS
for voisin, _ in graphe.voisins(sommet):
if couleurs[voisin] == GRIS:
# Arête vers un sommet en cours de visite = cycle
return True
elif couleurs[voisin] == BLANC and dfs_cycle(voisin):
return True
couleurs[sommet] = NOIR
return False
# Tester chaque sommet
for sommet in graphe.liste_sommets():
if couleurs[sommet] == BLANC:
if dfs_cycle(sommet):
return True
return False
def tri_topologique(graphe):
"""Tri topologique d'un graphe orienté acyclique"""
if not graphe.oriente:
raise ValueError("Le tri topologique nécessite un graphe orienté")
if detecter_cycle_oriente(graphe):
raise ValueError("Le graphe contient un cycle")
visites = set()
pile_resultat = []
def dfs_topo(sommet):
visites.add(sommet)
for voisin, _ in graphe.voisins(sommet):
if voisin not in visites:
dfs_topo(voisin)
# Ajouter le sommet à la pile après avoir visité tous ses successeurs
pile_resultat.append(sommet)
# Visiter tous les sommets
for sommet in graphe.liste_sommets():
if sommet not in visites:
dfs_topo(sommet)
# Inverser la pile pour obtenir l'ordre topologique
return pile_resultat[::-1]
def temps_decouverte_fin(graphe, sommet_depart):
"""Calcule les temps de découverte et de fin pour chaque sommet"""
temps = [0] # Utiliser une liste pour pouvoir modifier dans les fonctions imbriquées
decouverte = {}
fin = {}
visites = set()
def dfs_temps(sommet):
temps[0] += 1
decouverte[sommet] = temps[0]
visites.add(sommet)
for voisin, _ in graphe.voisins(sommet):
if voisin not in visites:
dfs_temps(voisin)
temps[0] += 1
fin[sommet] = temps[0]
dfs_temps(sommet_depart)
return decouverte, fin
# Test de l'implémentation
if __name__ == "__main__":
# Test avec graphe non orienté
g_non_oriente = GrapheListe(oriente=False)
g_non_oriente.ajouter_arete('A', 'B')
g_non_oriente.ajouter_arete('A', 'C')
g_non_oriente.ajouter_arete('B', 'D')
g_non_oriente.ajouter_arete('C', 'D')
print("Graphe non orienté:")
g_non_oriente.afficher()
print(f"\nDFS récursif depuis A: {dfs_recursif(g_non_oriente, 'A')}")
print(f"DFS itératif depuis A: {dfs_iteratif(g_non_oriente, 'A')}")
print(f"Cycle détecté: {detecter_cycle_non_oriente(g_non_oriente)}")
# Test avec graphe orienté
g_oriente = GrapheListe(oriente=True)
g_oriente.ajouter_arete('A', 'B')
g_oriente.ajouter_arete('A', 'C')
g_oriente.ajouter_arete('B', 'D')
g_oriente.ajouter_arete('C', 'D')
print("\n" + "="*40)
print("Graphe orienté:")
g_oriente.afficher()
print(f"\nCycle détecté: {detecter_cycle_oriente(g_oriente)}")
print(f"Tri topologique: {tri_topologique(g_oriente)}")
# Temps de découverte et fin
decouverte, fin = temps_decouverte_fin(g_oriente, 'A')
print(f"\nTemps de découverte: {decouverte}")
print(f"Temps de fin: {fin}")Difficile 🔴
Applications des parcours
Utilisez BFS et DFS pour résoudre des problèmes concrets :
- Labyrinthe : Trouvez le chemin le plus court de l'entrée à la sortie
- Îles : Comptez le nombre d'îles dans une grille binaire
- Coloration : Vérifiez si un graphe est bipartite
- Planification : Ordonnez des tâches avec dépendances
from collections import deque
def resoudre_labyrinthe(labyrinthe, entree, sortie):
"""Trouve le chemin le plus court dans un labyrinthe"""
lignes, colonnes = len(labyrinthe), len(labyrinthe[0])
directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] # droite, bas, gauche, haut
def est_valide(x, y):
return (0 <= x < lignes and 0 <= y < colonnes and
labyrinthe[x][y] != '#') # '#' = mur
# BFS pour trouver le chemin le plus court
file = deque([(entree, [entree])])
visites = {entree}
while file:
(x, y), chemin = file.popleft()
if (x, y) == sortie:
return chemin
for dx, dy in directions:
nx, ny = x + dx, y + dy
if est_valide(nx, ny) and (nx, ny) not in visites:
visites.add((nx, ny))
nouveau_chemin = chemin + [(nx, ny)]
file.append(((nx, ny), nouveau_chemin))
return None # Pas de chemin trouvé
def compter_iles(grille):
"""Compte le nombre d'îles dans une grille binaire"""
if not grille or not grille[0]:
return 0
lignes, colonnes = len(grille), len(grille[0])
visites = set()
nb_iles = 0
def dfs_ile(x, y):
if (x, y) in visites or x < 0 or x >= lignes or y < 0 or y >= colonnes:
return
if grille[x][y] == 0: # Eau
return
visites.add((x, y))
# Explorer les 4 directions (ou 8 avec diagonales)
for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
dfs_ile(x + dx, y + dy)
# Parcourir toute la grille
for i in range(lignes):
for j in range(colonnes):
if grille[i][j] == 1 and (i, j) not in visites:
# Nouvelle île trouvée
dfs_ile(i, j)
nb_iles += 1
return nb_iles
def est_bipartite(graphe):
"""Vérifie si un graphe est bipartite (2-coloriable)"""
couleurs = {} # 0 ou 1
def bfs_coloration(sommet_depart):
file = deque([sommet_depart])
couleurs[sommet_depart] = 0
while file:
sommet = file.popleft()
couleur_actuelle = couleurs[sommet]
for voisin, _ in graphe.voisins(sommet):
if voisin not in couleurs:
# Colorier avec la couleur opposée
couleurs[voisin] = 1 - couleur_actuelle
file.append(voisin)
elif couleurs[voisin] == couleur_actuelle:
# Conflit de couleur = pas bipartite
return False
return True
# Tester chaque composante connexe
for sommet in graphe.liste_sommets():
if sommet not in couleurs:
if not bfs_coloration(sommet):
return False
return True
def planifier_taches(taches_dependances):
"""Ordonne des tâches selon leurs dépendances"""
# Créer un graphe orienté des dépendances
graphe = GrapheListe(oriente=True)
# Ajouter toutes les tâches
for tache, deps in taches_dependances.items():
graphe.ajouter_sommet(tache)
for dep in deps:
graphe.ajouter_sommet(dep)
# dep doit être fait avant tache
graphe.ajouter_arete(dep, tache)
try:
# Tri topologique pour obtenir l'ordre
return tri_topologique(graphe)
except ValueError as e:
return f"Erreur: {e}"
# Tests des applications
if __name__ == "__main__":
# Test du labyrinthe
labyrinthe = [
['.', '.', '#', '.', '.'],
['.', '#', '#', '.', '#'],
['.', '.', '.', '.', '.'],
['#', '#', '.', '#', '.'],
['.', '.', '.', '.', '.']
]
chemin = resoudre_labyrinthe(labyrinthe, (0, 0), (4, 4))
print(f"Chemin dans le labyrinthe: {chemin}")
# Test des îles
grille_iles = [
[1, 1, 0, 0, 0],
[1, 1, 0, 0, 0],
[0, 0, 1, 0, 0],
[0, 0, 0, 1, 1]
]
nb_iles = compter_iles(grille_iles)
print(f"Nombre d'îles: {nb_iles}")
# Test de bipartition
g_bipartite = GrapheListe(oriente=False)
g_bipartite.ajouter_arete('A', 'X')
g_bipartite.ajouter_arete('A', 'Y')
g_bipartite.ajouter_arete('B', 'X')
g_bipartite.ajouter_arete('B', 'Z')
print(f"Graphe bipartite: {est_bipartite(g_bipartite)}")
# Test de planification
taches = {
'cuisiner': ['acheter', 'laver'],
'acheter': [],
'laver': ['acheter'],
'manger': ['cuisiner'],
'nettoyer': ['manger']
}
ordre = planifier_taches(taches)
print(f"Ordre des tâches: {ordre}")