# solutions exercices graphes (jeudi matin)

### exercice 1 ############################################################

# 8 au total (les trouver)

### exercice 2 ############################################################

# Il y a six arcs possibles (0 → 1, 1 → 0, 1 → 2, 2 → 1, 2 → 0, 0 →
# 2), chacun pouvant être présent ou absent, soit 2^6 = 64
# possibilités au total.

### exercice 3 ############################################################

# dans la classe matrice d'adjacence
class Graphe:
    # ...
    def afficher(self):
        for s in range(self.n):
            print(s, "->", end="")
            for v in range(self.n):
                if self.adj[s][v]:
                    print("", v, end="")
            print()

### exercice 4 ############################################################
### exercice 5 ############################################################

# dans la classe dictionnaire d'adjacence
class Graphe:
    # ...
    def degre(self, s):
        return len(self.adj[s])
    def nb_arcs(self):
        n = 0
        for s in self.adj:
            n += self.degre(s)
        return n

### exercice 7 ############################################################

# sommet | ensemble
#   de   | vus
# départ | au final
# -------+--------------
#      0 | { 0, 1, 3, 2 }
#      1 | { 1, 2 }
#      2 | { 2 }
#      3 | { 3, 1, 2 }

### exercice 8 ############################################################

# sommet | dist
# départ | au final
# -------+----------
#      0 | { 0:0, 1:1, 3:1, 2:2 }
#      1 | { 1:0, 2:1 }
#      2 | { 2:0 }
#      3 | { 3:0, 1:1, 2:2 }

### exercice 9 ############################################################

def est_connexe(g):
    """le graphe est-il connexe ?
       (uniquement pour un graphe non orienté)"""
    ts = g.sommets()
    if len(ts) == 0:
        return True
    s = ts.pop()
    vus = set()
    parcours(g, vus, s)
    for s in ts:
        if s not in vus:
            return False
    return True

### exercice 10 ############################################################

def parcours_ch(g, vus, org, s):
    """parcours depuis le sommet s, en venant de org"""
    if s not in vus:
        vus[s] = org
        for v in g.voisins(s):
            parcours_ch(g, vus, s, v)

def chemin(g, u, v):
    """un chemin de u à v, le cas échéant, None sinon"""
    vus = {}
    parcours_ch(g, vus, None, u)
    if v not in vus:
        return None
    ch = []
    s = v
    while s is not None:
        ch.append(s)
        s = vus[s]
    ch.reverse()
    return ch