Find if Path Exists in Graph

Q: Pourquoi BFS a-t-il besoin d’un tableau des sommets visités ?

Sans cela, un cycle comme 0 → 1 → 2 → 0 fait tourner la recherche indéfiniment et, même en l’absence de cycles, un nœud ayant plusieurs voisins serait mis en file une fois par voisin. Marquer chaque nœud au moment où il est mis en file garantit qu’il est traité une seule fois, ce qui borne le travail à O(n + m) .

Q: Que font la compression de chemin et l’union par taille dans une structure union-find ?

Ils gardent les arbres peu profonds pour que find reste rapide. L’union par taille place l’arbre le plus petit sous le plus grand, de sorte que la profondeur d’un nœud n’augmente que lorsque son groupe double au moins de taille, ce qui limite la profondeur à log n . La compression de chemin, ou l’aplatissement de chemin utilisé ici, raccourcit le parcours jusqu’à la racine chaque fois que tu l’effectues. Ensemble, ces techniques ramènent chaque opération à α(n) .

FacileGraphes Union-find

+10

Un graphe non orienté comporte n nœuds, numérotés de 0 à n-1. Chaque entrée [u, v] de edges relie les nœuds u et v, et tu peux parcourir une arête dans les deux sens. Renvoie true si tu peux aller de source à destination en suivant les arêtes, et false sinon. Un nœud peut toujours se rejoindre lui-même.

Fonction

validPath(n: integer, edges: integer-2d-array, source: integer, destination: integer) → boolean

ninteger: le nombre de nœuds
edgesinteger-2d-array: les arêtes, chacune étant une paire [u, v] de nœuds connectés
sourceinteger: le nœud à partir duquel vous commencez
destinationinteger: le nœud que vous souhaitez atteindre
Renvoieboolean: si un chemin quelconque relie la source et la destination

Contraintes

2 ≤ n ≤ 10⁴
1 ≤ edges.length ≤ 5000
edges[i] = [u, v] avec 0 ≤ u, v ≤ n-1 et u ≠ v
Aucune arête n’apparaît deux fois, dans un sens ou dans l’autre.
0 ≤ source, destination ≤ n-1

Exemples

Entrée: n = 6edges = [[0, 1], [1, 2], [2, 3], [4, 5]]source = 0destination = 3
Sortie: true
Explication: Le parcours 0 → 1 → 2 → 3 utilise trois arêtes, donc le nœud 3 est accessible. Les nœuds 4 et 5 forment une partie séparée dont le parcours n’a jamais besoin.

Entrée: n = 5edges = [[0, 1], [0, 2], [3, 4]]source = 2destination = 4
Sortie: false
Explication: Depuis le nœud 2, tu atteins 0 puis 1, et rien d’autre. Le nœud 4 ne touche que le nœud 3, et aucune arête ne relie {0, 1, 2} à {3, 4}, donc la réponse est false.

+16 tests cachés à la soumission

Pour aller plus loin

Supposons que les arêtes soient à sens unique : [u, v] permet de se déplacer de u à v uniquement. Laquelle des trois approches fonctionne encore, et que faut-il y changer ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

La question est de savoir si source et destination se trouvent dans la même composante connexe du graphe. La méthode lente parcourt de nouveau la liste des arêtes jusqu’à ce qu’aucun nouvel élément ne soit atteint. Un parcours en largeur sur une liste d’adjacence explore chaque nœud et chaque arête une seule fois, et la structure union-find obtient la même réponse en fusionnant les groupes au fur et à mesure qu’elle lit les arêtes, sans avoir besoin de listes de voisins.

Balayez les bords jusqu’à ce que plus rien ne change

Correcte, mais ne termine pas sur les plus gros tests

Intuition

Marquez chaque nœud que vous savez pouvoir atteindre, en commençant par source. Parcourez maintenant la liste des arêtes. Une arête avec une extrémité marquée et une extrémité non marquée signifie que vous pouvez aussi atteindre cette dernière : marquez-la. Répétez tout le parcours jusqu’à ce qu’un parcours ne marque rien de nouveau, ou que destination soit marqué.

C’est correct : un nœud situé sur un chemin de longueur k depuis source est marqué au plus tard lors du k-ième parcours, et un nœud n’est marqué que lorsqu’une arête y mène depuis un nœud marqué. Dans le premier exemple, un seul parcours dans l’ordre de la liste marque successivement 1, 2 et 3, et c’est terminé.

Le coût dépend de l’ordre des arêtes. Si le chemin est listé en partant de l’extrémité éloignée, chaque parcours ne marque qu’un nœud supplémentaire. Un chemin traversant 5001 nœuds nécessite alors 5000 parcours de 5000 arêtes, soit 2.5 × 10^7 vérifications d’arêtes, alors qu’un seul parcours d’une liste de voisins suffirait.

Algorithme

Créer reached en marquant uniquement source.
Parcourir chaque arête [u, v]. Si exactement une extrémité est marquée, marquer l’autre et noter qu’un changement a eu lieu.
Répéter le parcours tant qu’un changement a eu lieu et que destination n’est toujours pas marquée.
Renvoyer si destination est marquée.

def validPath(n, edges, source, destination):
    reached = [False] * n
    reached[source] = True
    changed = True
    while changed and not reached[destination]:
        changed = False
        for u, v in edges:
            # An edge with exactly one reached end pulls the other end in.
            if reached[u] != reached[v]:
                reached[u] = reached[v] = True
                changed = True
    return reached[destination]

Recherche en largeur

Intuition

Le parcours perd du temps à relire des arêtes dont les extrémités ont été traitées depuis longtemps. À la place, liste pour chaque nœud les nœuds auxquels il est relié. Chaque arête [u, v] figure dans les deux listes, car tu peux la parcourir dans les deux sens. Explore ensuite à partir de source : retire un nœud de la file et ajoute chacun de ses voisins que tu n’as pas encore vus.

Marque un nœud comme vu lorsque tu l’ajoutes à la file, et non lorsque tu le retires. Ainsi, aucun nœud n’entre deux fois dans la file, et la recherche se termine même si le graphe contient des cycles, comme 0 → 1 → 2 → 0. Si destination est retiré de la file, un chemin existe. Si la file se vide avant, tu as vu tous les nœuds que source peut atteindre, et destination n’en faisait pas partie.

Chaque nœud est ajouté à la file au plus une fois et chaque arête est examinée deux fois, une fois depuis chaque extrémité : la complexité temporelle est donc O(n + m) pour m arêtes. Les listes de voisins occupent un espace de O(n + m). Une file plutôt que la récursion évite qu’un chemin de 5000 nœuds ne fasse déborder la pile d’appels.

Algorithme

Construisez une liste d’adjacence : pour chaque arête [u, v], ajoutez v à la liste de u et u à la liste de v.
Marquez source comme visité et placez-le dans une file.
Retirez un nœud en tête de file. S’il s’agit de destination, renvoyez true.
Marquez et ajoutez à la file chaque voisin qui n’a pas encore été visité.
Lorsque la file est vide, renvoyez false.

from collections import deque


def validPath(n, edges, source, destination):
    # Each edge goes both ways, so list it under both of its ends.
    graph = [[] for _ in range(n)]
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    seen = [False] * n
    seen[source] = True
    queue = deque([source])
    while queue:
        node = queue.popleft()
        if node == destination:
            return True
        for nxt in graph[node]:
            if not seen[nxt]:
                # Mark on push, so no node enters the queue twice.
                seen[nxt] = True
                queue.append(nxt)
    return False

Union-find

Intuition

Tu n’as pas besoin du chemin, seulement de savoir s’il en existe un. Considère donc le graphe comme des groupes de nœuds connectés. Au départ, chaque nœud constitue son propre groupe. Une arête [u, v] indique que u et v appartiennent au même groupe : fusionne donc leurs groupes. Après avoir parcouru toutes les arêtes, source et destination sont connectés exactement lorsqu’ils appartiennent au même groupe.

Stocke chaque groupe sous forme d’arbre avec des liens parent ; la racine désigne le groupe. find(x) remonte jusqu’à la racine. Pour fusionner, place une racine sous l’autre. Dans le deuxième exemple, [0, 1] et [0, 2] forment le groupe {0, 1, 2}, et [3, 4] forme le groupe {3, 4} ; find(2) et find(4) renvoient des racines différentes, donc la réponse est false.

Deux habitudes permettent de garder les arbres plats. Place le plus petit groupe sous le plus grand, et divise par deux le chemin pendant find en reliant chaque nœud à son grand-parent. Ensemble, elles ramènent le coût de chaque opération à α(n), la fonction inverse d’Ackermann, qui reste inférieure à 5 pour toute entrée que tu rencontreras. Les arêtes sont parcourues une seule fois et seuls parent et size sont stockés : un espace de O(n), sans listes de voisins à construire.

Algorithme

Définissez parent[x] = x et size[x] = 1 pour chaque nœud.
Pour chaque arête [u, v], trouvez les racines a et b des deux extrémités.
Si elles sont différentes, rattachez la racine du plus petit groupe à l’autre et additionnez les tailles.
Renvoyez si find(source) est égal à find(destination).

def validPath(n, edges, source, destination):
    parent = list(range(n))  # every node starts as its own group
    size = [1] * n

    def find(x):
        # Walk up to the group's root, halving the path on the way.
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x

    for u, v in edges:
        a, b = find(u), find(v)
        if a != b:
            # Hang the smaller group under the larger one.
            if size[a] < size[b]:
                a, b = b, a
            parent[b] = a
            size[a] += size[b]
    return find(source) == find(destination)

Pièges et cas limites

Le graphe est petit, mais quelques détails déterminent si la recherche se termine et fournit la bonne réponse.

Ajouter chaque arête dans une seule direction. Le graphe n’est pas orienté, donc [1, 0] doit aussi permettre d’aller de 0 à 1. Une liste d’adjacence à sens unique ne prend pas en compte les chemins qui empruntent une arête à rebours.
Marquer les nœuds comme visités lorsqu’on les retire de la file plutôt que lorsqu’on les y ajoute. Un nœud entre alors dans la file une fois pour chaque voisin traité avant lui, si bien que la file peut contenir jusqu’à 2m entrées au lieu d’au plus n.
Oublier que source peut être égal à destination. La réponse est true, même si ce nœud n’a aucune arête.
Utiliser un DFS récursif sur un long chemin. Un chemin passant par 5000 nœuds correspond à 5000 appels imbriqués, ce qui dépasse la limite par défaut de 1000 de Python. Utilisez une file ou une pile explicite.
Comparer parent[source] et parent[destination] dans union-find. Seules les racines désignent un groupe ; comparez toujours find(source) et find(destination).
Oublier le décalage en Lua et en R, où les tableaux commencent à 1 : le nœud x se trouve à l’index x+1.

Questions fréquentes4

Dois-je utiliser BFS, DFS ou union-find pour vérifier si un chemin existe ?

Les trois sont linéaires ou presque. BFS et DFS peuvent s’arrêter dès qu’ils atteignent la destination et renvoyer le chemin lui-même. Union-find n’a pas besoin de liste d’adjacence, parcourt chaque arête une seule fois et excelle lorsque de nombreuses questions de connexité portent sur le même graphe, car après les fusions, chaque question ne nécessite que deux appels à find.

Quelle est la complexité temporelle de la recherche de l’existence d’un chemin dans un graphe ?

Avec BFS ou DFS, la complexité en temps et en espace est de O(n + m), pour n nœuds et m arêtes : chaque nœud est visité une fois et chaque arête est vérifiée depuis ses deux extrémités. Union-find avec union par taille et compression de chemin par division par deux coûte O(n + m·α(n)) en temps et O(n) en espace, où α croît si lentement qu’elle est une petite constante en pratique.

Pourquoi BFS a-t-il besoin d’un tableau des sommets visités ?

Sans cela, un cycle comme 0 → 1 → 2 → 0 fait tourner la recherche indéfiniment et, même en l’absence de cycles, un nœud ayant plusieurs voisins serait mis en file une fois par voisin. Marquer chaque nœud au moment où il est mis en file garantit qu’il est traité une seule fois, ce qui borne le travail à O(n + m).

Que font la compression de chemin et l’union par taille dans une structure union-find ?

Ils gardent les arbres peu profonds pour que find reste rapide. L’union par taille place l’arbre le plus petit sous le plus grand, de sorte que la profondeur d’un nœud n’augmente que lorsque son groupe double au moins de taille, ce qui limite la profondeur à log n. La compression de chemin, ou l’aplatissement de chemin utilisé ici, raccourcit le parcours jusqu’à la racine chaque fois que tu l’effectues. Ensemble, ces techniques ramènent chaque opération à α(n).

Python

def validPath(n, edges, source, destination):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Entrée

n = 6
edges = [[0, 1], [1, 2], [2, 3], [4, 5]]
source = 0
destination = 3

Attendu

true

Find if Path Exists in Graph

Fonction

Contraintes

Exemples

Indices

Solution

Balayez les bords jusqu’à ce que plus rien ne change

Recherche en largeur

Union-find

Pièges et cas limites

Questions fréquentes4

Problèmes similaires