Return a path between graph nodes using depth-first search redo I previously attempted to implement a Graph class which has a method that returns a path between 2 nodes using depth-first search. This is my latest attempt at this (using the feedback I got from last time).

I'm doing this to improve my style and to improve my knowledge of fundamental algorithms/data structures for an upcoming coding interview.

class Graph:
    def __init__(self):
        self.nodes = set()

    def add_node(self, id):
        new_node = Node(id)
        self.nodes.add(new_node)
        return new_node

    def get_node(self, id):
        for node in self.nodes:
            if node.id == id:
                return node
        return None

    def dfs(self, start, end):
        stack = [start]
        parents = {}
        seen = set([start])

        while stack:
            cur_node = stack.pop()
            if cur_node is not end:
                for neighbour in cur_node.neighbours:
                    if neighbour not in seen:
                        seen.add(neighbour)
                        stack.append(neighbour)
                        parents[neighbour] = cur_node
            else:
                path = self.get_path(start, cur_node, parents)
                return path
        return None

    def get_path(self, start, end, parents):
        stack = [end]
        cur_node = end
        while cur_node is not start:
            cur_node = parents[cur_node]
            stack.append(cur_node)

        path = []
        while stack:
            cur_node = stack.pop()
            path.append(cur_node)
        return path

class Node:
    def __init__(self, id):
        self.id = id
        self.neighbours = {}

    def add_neighbour(self, to, weight):
        self.neighbours[to] = weight
Honestly your code is pretty good.

There are however two things that I would change:


self.nodes to be a dictionary rather than a set. This allows you to remove the need for get_node, and changes it to \$O(1)\$ from \$O(n)\$.
In get_path you pop from one stack and append to another. Instead of doing this manually I'd use the built-in list slicing notation, stack[::-1].