Tester l'existence d'un chemin

Il suffit de lancer un parcours (BFS ou DFS) à partir de $u$ et de vérifier si $v$ est atteint.

from collections import deque

def existe_chemin(G, u, v):
    if u == v:
        return True
    visites = {u}
    file = deque([u])
    while file:
        courant = file.popleft()
        for voisin in G[courant]:
            if voisin == v:
                return True
            if voisin not in visites:
                visites.add(voisin)
                file.append(voisin)
    return False

G = {0: [1], 1: [0, 2], 2: [1], 3: [4], 4: [3]}
print(existe_chemin(G, 0, 2))   # True
print(existe_chemin(G, 0, 3))   # False (composantes distinctes)

La complexité est $O(n+m)$.