# Dessiner les 2 graphes ci-dessous :

G1={'A':['B','F'],'B':['C','D','G'],'C': ['B','E'],'D':['B','I'],'E':['C','I'],'F':['A','G','H'],'G':['B','F','I'],'H':['F','I'],'I':['G','D','E','H']}
G2={1:[2],2:[3,4,6],3:[1,5],4:[1],5:[6],6:[2,7],7:[8,5],8:[5]}


######################################
# Parcours en largeur                #
######################################

# Primitives pour gérer une file

def creerFile():
    return []

def estVide(file):
    return file==[]

def Sommet(file):
    if estVide(file):
        return None
    else:
        return file[0]
            
def enfiler(file,elt):
    file.append(elt)
    return file

def defiler(file):
    if not estVide(file):
        return file.pop(0)
    return None

def parcoursLarg(noeud,graph):
    s = noeud
    file = creerFile()
    enfiler(file,s)
    visited = [s]
    while not estVide(file): 
        u = defiler(file)
        if  u not in visited:
            visited.append(u)
        for voisin in graph[u]:
            if voisin not in visited :
                enfiler(file,voisin)
    return visited

# Vérifier que la commande ci-dessous renvoie bien un parcours en largeur
#print(parcoursLarg('A',G1))
#print(parcoursLarg(1,G2))




# Compléter la fonction ci-dessous,
# qui renvoie un dictionnaire dont les clés sont les sommets visités
# et les valeur le sommet prédécesseur (c'est à dire le sommet parent)
# d'un graphe

def dico_largeur(start,graph):
    s=start
    file=creerFile()
    enfiler(file,s)
    visited={s : None}
    while file != []:
        u=defiler(file)
        for voisin in graph[u]:
            if voisin not in visited :
                enfiler(file,voisin)
                visited[voisin]=u
    return visited





# A partie du dictionaire obtenur par la commande :
# dico_largeur('A',G1)
# Ecrire le chemin qui méne du sommet A au sommet E.




#
# Compléter l'algorithme ci-dessous qui permet de faire automatiquement le travail de la question précedente.
# Autrement dit la fcontion prend en parametre :
# - un dictinaire des prédecesseurs
#  - un sommet de départ :  start
#  - un sommet d'arrivé ; goal
# et renvoie le chemin pour aller de start à goal
#



def chemin_final(start,goal,dico):
    '''
    param : dico est celui  des parents des sommets visités. (dictinaire des prédecesseurs)
    renvoie le chemin pour aller de start à goal
    '''
    chemin=[goal]
    tmp=goal
    while tmp != start:
        chemin.append(dico[tmp])
        tmp=dico[tmp]
    chemin.reverse()
    return chemin


#Tester les commandes :
start= 'A'
goal= 'E'
graphe = G1
dico=dico_largeur(start,graphe)
print(chemin_final(start,goal,dico))

start= 1
goal= 5
graphe = G2
dico=dico_largeur(start,graphe)
print(chemin_final(start,goal,dico))




######################################
# Parcours en profondeur                #
######################################

# Primitives pour gérer une pile

def creerPile():
    return []

def estVide(pile):
    return pile==[]

def Sommet(pile):
    if estVide(pile):
        return None
    else:
        return pile[-1]
            
def empiler(pile,elt):
    pile.append(elt)
    return pile

def depiler(pile):
    if not estVide(pile):
        return pile.pop()
    return None

def parcoursProf(noeud,graph):
    s = noeud
    file = creerPile()
    empiler(pile,s)
    visited = [s]
    while not estVide(pile):
        u = depiler(pile)
        if  u not in visited:
            visited.append(u)
        for voisin in graph[u]:
            if voisin not in visited :
                empiler(pile,voisin)
    return visited

# Vérifier que la commande ci-dessous renvoie bien un parcours en largeur
#print(parcoursProf('A',G1))
#print(parcoursProf(1,G2))




# Compléter la fonction ci-dessous,
# qui renvoie un dictionnaire dont les clés sont les sommets visités
# et les valeur le sommet prédécesseur (c'est à dire le sommet parent)
# d'un graphe

def dico_profondeur(start,graph):
    s = start
    pile = creerPile()
    enfiler(pile,s)
    visited = {s : None}
    while not estVide(pile):
        u = depiler(pile)
        for voisin in graph[u]:
            if voisin not in visited :
                empiler(pile,voisin)
                visited[voisin]=u
    return visited





# A partie du dictionaire obtenur par la commande :
# dico_profondeur('A',G1)
# Ecrire le chemin qui méne du sommet A au sommet E.










#Tester les commandes :
start= 'A'
goal= 'E'
graphe = G1
dico=dico_profondeur(start,graphe)
print(chemin_final(start,goal,dico))

start= 1
goal= 5
graphe = G2
dico=dico_profondeur(start,graphe)
print(chemin_final(start,goal,dico))