#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Tue May 14 17:24:32 2024

@author: phjo
"""

L1 = [[1, 2], [6], [3, 4], [], [7, 8], [1], [], [], [6]]
D1 = {0: [1, 2], 1: [6], 2: [3, 4], 3: [], 4: [7, 8], 5: [1], 6: [], 7: [], 8: [6]}
L2 = [[1,3],[0,2,4],[1,5],[0,4,6],[1,3,5,7],[2,4,8],[3,7],[4,6,8],[5,7]]
D2 = {0: [1,3], 1: [0,2,4], 2:[1,5], 3: [0,4,6], 4:[1,3,5,7], 5: [2,4,8],\
      6: [3,7], 7:[4,6,8], 8:[5,7]}

from collections import deque


def BFS(LA, s):
    L = []
    vus = [s]
    Q = deque()
    Q.append(s)
    while len(Q) > 0:
        s1 = Q.popleft()
        L.append(s1)
        for s2 in LA[s1]:
            if s2 not in vus:
                Q.append(s2)
                vus.append(s2)
    return L



def DFS(LA, s):
    L, vus = [], []
    p = [s]
    while len(p) > 0:
        s1 = p.pop()
        if s1 not in vus:
            L.append(s1)
            vus.append(s1)
            for s2 in LA[s1]:
                if s2 not in vus:
                    p.append(s2)
    return L


############

def chargeMots(nom_fichier):
    f = open(nom_fichier)
    listeMots = []
    for l in f:
        listeMots.append(l.strip('\n'))
    return listeMots
    

def sontVoisins(mot1, mot2):
    # votre code ici
    pass

def creeGraphe(listeMots):
    """ retourne une liste d'adjacence sous la forme d'un dictionnaire """
    n = len(listeMots)
    graphe = {mot: [] for mot in listeMots}
    # votre code ici
    
    
    return graphe