Copie profonde de graphe

#133 Clone Graph

Bonjour 👋

Cette semaine on se retrouvait pour le problème #133 Clone Graph. L’énoncé est clair: réaliser la copie profonde d’un graphe.

Le graphe est représenté via une liste d'adjacence. Chaque nœud possède deux attributs; un entier représentant sa valeur et la liste de ses voisins.

class Node {
     public int val;
     public List<Node> neighbors;
}

L’énoncé précise que l’on aura pas plus de 100 nœuds à traiter et les graphes proposés sont connexe (fully connected).

---

Intuition

Pour faire la copie profonde, on a besoin de parcourir l‘ensemble des nœuds du graphe.

• Pour ça, on peut s’y prendre de deux façons: Parcours en largeur (BFS) ou en profondeur (DFS).

• On a également besoin d’une structure de données pour suivre les nœuds visités. La difficulté dans ce problème est de s’assurer que l’on visite chaque nœud une seule fois. Une table de hachage est adaptée pour tenir à jour une équivalence ancien nœud -> nouveau nœud.

Implémentation

L’implémentation de Vincent avec la DFS tient en une dizaine de lignes en Python ¹

class Solution:

    def cloneGraph(self, node: 'Node') -> 'Node':
        visited = dict()

        def dfs(n:'Node') -> 'Node':
            if n in visited: return visited[n]
            new_node = Node(n.val)
            visited[n] = new_node
            for nei in n.neighbors:
                new_node.neighbors.append(dfs(nei))
            return new_node

        return dfs(node)

Pour l’implémentation via une BFS, on a besoin d’une file (queue) supplémentaire pour suivre les noeuds à visiter. Ce n’est pas nécessaire avec la DFS qui utilise une pile implicite correspondant à la pile des appels (call stack) de la fonction DFS.

Analyse de la complexité

• En temps d’exécution, parcourir le graphe coûte O(V + E), avec V le nombre de nœuds (Vertex) et E le nombre d’arcs (Edge) dans le graphe. Pour chaque itération de la DFS, on a une opération de lecture et possiblement d’insertion dans un dictionaire qui coûte O(1) chacune.
  La complexité sur le runtime est donc de O(1) * O(V + E) = O(V + E).

• En mémoire, on a besoin d’un dictionnaire pour maintenir un mapping pour chaque noeud du graphe d’origine vers son homologue dans le graphe cloné, soit un coût de O(V).

Le condensée de la session avec walkthrough du code est disponible sur Youtube 👇

Prochaine session

Ce samedi 8 mai, on marque une pause dans notre cycle graphe pour s’attaquer à un challenge: le Weekly Contest 239 🏆

Le format d’un contest?

• 📚Quatre exercices avec une difficulté crescendo.
  Un facile, deux mediums et un difficile.

• ❓Des sujets variés.
  C’est une bonne occasion de faire autre chose que du parcours de graphe et de prendre le pouls sur d’autre types d’exos.

• ⏱ Prévoir 1h30 dans son agenda.

On se dit à samedi prochain, 09:30am sur notre Twitch LeetGrindFr 😉

Mots-clés de la session

graphe, copie profonde, bfs, dfs

Photo de thumbnail de Francesco Ungaro de Pexels

1. Voir ce tread du discuss de la question Leetcode 133 pour une implémentation de la BFS.