#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Wed Mar 29 18:01:50 2023

@author: vincentleprince
"""


# Matrice servant d'exemple dans le 1 :
M = [[0, 1,1,0,0,0,0,0,0,0 ],
             [1,0,1, 1,1,0,0,0,0,0],
             [1,1,0,1,0,1,0,0,0,0],
             [0,1,1,0,1,1,1,0,0,0],
            [0,1,0,1,0,1,1,1,0,0],
            [0,0,1,1,1,0,1,0,0,1],
             [0,0,0,1,1,1,0,0,1,0],
             [0, 0,0,0,1,0,0,0,1,0 ],
             [0, 0,0,0,0,0,1,1,0,0 ],
             [0, 0,0,0,0,1,0,0,0,0 ]]


# Matrice servant d'exemple pour les parcours :
M1 = [[0,1,1,0,0,0,0],
      [1,0,0,1,0,0,0],
      [1,0,0,0,0,0,1],
      [0,1,0,0,1,1,0],
      [0,0,0,1,0,0,0],
      [0,0,0,1,0,0,0],
      [0,0,1,0,0,0,0] ]
      



def parcours_prof(M,sommet):
    n = len(M)
    pile = [sommet]
    etats_sommets = [0 for s in range(n)]
    etats_sommets[sommet] = 1  # 0 pour les sommets non encore traiées
                               # 1 pour les sommets dans la pile
                               # 2 pour les sommets visités 
    ordre_sommets_visites = []
    liste_peres = [-1 for s in range(n)] # pour reconstituer un chemin
    while .....   :
        s = pile.pop()
        ordre_sommets_visites.append(....
        etats_sommets[s] = ....
        for t in range(n): 
            if M[s][t]==...  and etats_sommets[t] == ... :
                # mise à jour de pile et etats_sommets (et liste_peres)
                ...
                ...
                ...
                
    return ordre_sommets_visites ,liste_peres

# tests : 
print(parcours_prof(M,0)) 

print(parcours_prof(M1,0)) 

def chemin_prof(M,sommet1,sommet2):
    liste_peres = ...
    s = sommet2
    cheminS1S2 = [s]
    # A compléter
    
    
    return cheminS1S2

print(chemin_prof(M,0,7))


    


# parcours en largeur
    
def parcours_larg(M,sommet):
    # A compléter

print(parcours_larg(M,0)) 

print(parcours_larg(M1,0)) 

def parcours_larg_dist(M,sommet):
    # A compléter
    
print(parcours_larg_dist(M,0)) 

print(parcours_larg_dist(M1,0))     

# fonction récursive pour le parcours en profondeur:
    
def parcours_prof_rec(M,sommet):
    n = len(M)
    etats_sommets = [0 for s in range(n)] # passe à 1 lorsqu'un
                                          # sommet est visité
    liste_peres = [-1 for s in range(n)]
    ordre_sommets_visites = []
    def aux(s):
        etats_sommets[s] = 1
        ordre_sommets_visites.append(s)
        #print("visite du sommet " + str(sommet)) # pour constater l'ordre des appels
        for t in range(n): 
            if ....  :
                ....   # mise à jour de liste_peres
                  
                ....   # appel récursif
                
    aux(sommet)
    return ordre_sommets_visites , liste_peres
                
 
# tests : 
print(parcours_prof_rec(M1,0))  
print(parcours_prof(M1,0))   
# remarque : on n'obtient pas exactement les mêmes réponses   
#            du fait des choix différents qui peuvent être faits 
#            dans le choix de l'ordre dans lequel on traite les successeurs.



print(parcours_prof_rec(M1,0))  
print(parcours_prof(M1,0))