# =============================================
# Exercice 1 : Représentation des graphes
# =============================================

# 1. Graphes donnés
sommets = [k for k in range(4)]

arcs1 = [(0,1), (1,2), (2,3), (3,0)]   # cycle
arcs2 = [(0,1), (0,2), (0,3), (1,2), (1,3), (2,3)]  # presque complet

G1 = [sommets, arcs1]
G2 = [sommets, arcs2]

# 2. Liste d'adjacence pour G1 et G2
def creer_liste_adjacence(sommets, arcs):
    """Crée la liste d'adjacence à partir d'une liste d'arcs"""
    n = len(sommets)
    adj = []
    for i in range(n):
        adj.append([])          # liste vide pour chaque sommet
    
    for u, v in arcs:
        adj[u].append(v)        # arc orienté de u vers v
    return adj


print("Liste d'adjacence G1 :", creer_liste_adjacence(sommets, arcs1))
print("Liste d'adjacence G2 :", creer_liste_adjacence(sommets, arcs2))


# =============================================
# Fonctions de conversion
# =============================================

def matrice_adjacence(G):
    """Prend G sous forme de liste d'adjacence et renvoie la matrice d'adjacence"""
    adj = G                    # G est déjà la liste d'adjacence
    n = len(adj)
    M = []
    for i in range(n):
        ligne = []
        for j in range(n):
            if j in adj[i]:
                ligne.append(1)
            else:
                ligne.append(0)
        M.append(ligne)
    return M


def liste_adjacence(M):
    """Prend une matrice d'adjacence et renvoie la liste d'adjacence"""
    n = len(M)
    adj = []
    for i in range(n):
        ligne = []
        for j in range(n):
            if M[i][j] == 1:
                ligne.append(j)
        adj.append(ligne)
    return adj


# Tests
adj_G1 = creer_liste_adjacence(sommets, arcs1)
M1 = matrice_adjacence(adj_G1)
print("\nMatrice d'adjacence G1 :")
for ligne in M1:
    print(ligne)

print("\nListe d'adjacence reconstruite :", liste_adjacence(M1))


# =============================================
# Graphe orienté / non orienté
# =============================================

def non_oriente(G):
    """Renvoie la version non-orientée du graphe G (liste d'adjacence)"""
    n = len(G)
    adj_non_or = []
    for i in range(n):
        adj_non_or.append([])
    
    for u in range(n):
        for v in G[u]:
            # On ajoute l'arc dans les deux sens
            if v not in adj_non_or[u]:
                adj_non_or[u].append(v)
            if u not in adj_non_or[v]:
                adj_non_or[v].append(u)
    return adj_non_or


def test_oriente(G):
    """Renvoie True si le graphe est orienté, False s'il est non-orienté"""
    n = len(G)
    for u in range(n):
        for v in G[u]:
            if u not in G[v]:      # si l'arc inverse n'existe pas
                return True
    return False


# =============================================
# Exercice 2 : Parcours en profondeur et en largeur
# =============================================

def parcours_profondeur(G, S_i, S_c):
    """Parcours en profondeur (DFS) - utilise une pile (dernier élément)"""
    n = len(G)
    N = []          # noir : visités
    Gr = [S_i]      # gris : à visiter (pile)
    B = []          # blanc : non vus (pas utile ici)
    
    while len(Gr) > 0:
        S = Gr.pop()                    # dernier élément = profondeur
        
        if S == S_c:
            N.append(S)
            return N                    # on peut arrêter ici
        
        if S not in N:
            N.append(S)
            # On ajoute les voisins non visités
            for voisin in G[S]:
                if voisin not in N and voisin not in Gr:
                    Gr.append(voisin)
    
    return False   # pas de chemin


def parcours_largeur(G, S_i, S_c):
    """Parcours en largeur (BFS) - utilise une file (premier élément)"""
    n = len(G)
    N = []
    Gr = [S_i]      # gris : file
    
    while len(Gr) > 0:
        S = Gr.pop(0)                   # premier élément = largeur
        
        if S == S_c:
            N.append(S)
            return N
        
        if S not in N:
            N.append(S)
            for voisin in G[S]:
                if voisin not in N and voisin not in Gr:
                    Gr.append(voisin)
    
    return False


# =============================================
# Degrés
# =============================================

def degre_s(G):
    """Renvoie la liste des degrés sortants"""
    return [len(G[i]) for i in range(len(G))]


def degre_e(G):
    """Renvoie la liste des degrés entrants"""
    n = len(G)
    deg = [0] * n
    for u in range(n):
        for v in G[u]:
            deg[v] += 1
    return deg


# =============================================
# Exercice 3 : Plus court chemin (BFS + origine)
# =============================================

def chemin(G, S_i, S_c):
    """Renvoie le plus court chemin de S_i à S_c (liste de sommets)"""
    n = len(G)
    N = []           # visités
    Gr = [S_i]
    origine = [-1] * n      # pour reconstruire le chemin
    origine[S_i] = S_i
    
    trouve = False
    while len(Gr) > 0 and not trouve:
        S = Gr.pop(0)
        
        if S == S_c:
            trouve = True
            break
        
        if S not in N:
            N.append(S)
            for voisin in G[S]:
                if voisin not in N and voisin not in Gr:
                    Gr.append(voisin)
                    origine[voisin] = S
    
    if not trouve:
        return False
    
    # Reconstruction du chemin
    c = []
    courant = S_c
    while courant != S_i:
        c.append(courant)
        courant = origine[courant]
    c.append(S_i)
    c.reverse()
    return c


# =============================================
# Exercice 4 : Labyrinthe
# =============================================

# Définition du graphe du labyrinthe (à adapter selon l'image)
# Exemple pour un petit labyrinthe 3x3 (cases 0 à 8)
# On suppose la sortie est la case 2 (en haut à droite)

G_L = [
    [1, 3],      # 0
    [0, 2, 4],   # 1
    [1],         # 2 = sortie
    [0, 4, 6],   # 3
    [1, 3, 5, 7],# 4
    [4, 8],      # 5
    [3, 7],      # 6
    [4, 6, 8],   # 7
    [5, 7]       # 8
]

def sortie(G, k):
    """Renvoie un chemin du sommet k jusqu'à la sortie (case n-1)"""
    n = len(G)
    sortie = n - 1
    return chemin(G, k, sortie)


# Tests
print("\n=== Tests Labyrinthe ===")
print("Chemin depuis 0 :", sortie(G_L, 0))
print("Chemin depuis 6 :", sortie(G_L, 6))
print("Chemin depuis 8 :", sortie(G_L, 8))