#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Thu Mar 26 08:33:17 2026

@author: pjoulaud
"""

import random

class Pile:
    """ classe Pile
    création d’une instance Pile avec une liste
    """
    def __init__(self):
        self.L = []
    def vide(self):
        return self.L == []
    def depiler(self):
        assert not self.vide(),"Pile vide"
        return self.L.pop()
    def sommet(self):
        assert not self.vide(),"Pile vide"
        return self.L[-1]
    def empiler(self,x):
        self.L.append(x)

G = dict()
G['a'] = ['b','c']
G['b'] = ['a','d','e']
G['c'] = ['a','d']
G['d'] = ['b','c','e']
G['e'] = ['b','d','f','g']
G['f'] = ['e','g']
G['g'] = ['e','f','h']
G['h'] = ['g']

def voisins(G,sommet):
    return G[sommet]

def dfs(graphe:dict, depart:str)->list:
    """
    Fonction qui implémente l' algorithme DFS
    Parameters
    ----------
    graphe : dict
        Dictionnaire d' adjacence d' un graphe
    depart : str
        Sommet de départ pour l' algo BFS
    Returns
    -------
    list
        Liste de tous les sommets visités

    """
    s_visites = []
    s_fermes = []
    p = Pile()
    s_visites.append(depart)
    p.empiler(depart)
    while not p.vide():
        tmp = p.sommet()
        nouveaux_voisins=[y for y in voisins(G,tmp) if y not in s_visites]
        if nouveaux_voisins != []:
            v=random.choice(nouveaux_voisins)
            s_visites.append(v)
            p.empiler(v)
        else :
            s_fermes.append(tmp)
            tmp = p.depiler()
    return s_fermes
arbre_couvrant = dfs(G, 'b')
print(arbre_couvrant)