Return path between graph nodes using depth-first search

Question

This code is meant to implement a Graph class which has a method that returns a path between 2 nodes using depth-first search.

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

from queue import PriorityQueue
from copy import deepcopy

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

    def add_vert(self, id):
        new_vert = Vertex(id)
        self.verts.add(new_vert)
        return new_vert

    def get_vert(self, id):
        for vert in self.verts:
            if vert.id == id:
                return vert
        return None

    def dfs(self, start, end):
        path_stack = []
        visited = set()
        path_stack.append([start])

        while path_stack:
            cur_path = path_stack.pop()
            last = cur_path[-1]
            visited.add(last)

            if last != end:
                path_stack = self.push_paths_in_order(path_stack, cur_path, visited)
            else:
                return cur_path
        return None

    def push_paths_in_order(self, path_stack, cur_path, visited):
        last = cur_path[-1]
        queue = PriorityQueue()

        for neighbour in last.neighbours:
            if neighbour not in visited:
                    # make queue like max heap so that we can push
                    # paths to path_stack in increasing order
                    dist_to_neighbour = last.neighbours[neighbour] * -1
                    queue.put((dist_to_neighbour, neighbour))

        while not queue.empty():
            new_path = deepcopy(cur_path)
            next_vert = queue.get(0)[1]
            new_path.append(next_vert)
            path_stack.append(new_path)
        return path_stack


class Vertex:
    def __init__(self, id):
        self.id = id
        self.neighbours = dict()

    def add_neighbour(self, to, weight):
        self.neighbours[to] = weight

Answer 1

1. The algorithm you've implemented is not a depth-first search. I'm not sure what it does exactly. It uses a priority queue for some reason (a depth-first search doesn't need a priority queue). It also stores the entire path in the stack and copies every time it discovers a new vertex, which makes it time and space inefficient (your's implementation needs O(n^2) space and time even on a sparse graph (for instance, a tree), while a correct implementation is always linear in number of vertices and edges).

2. A standard depth-first search goes like this:

   stack = [start_vertex]
   parent = empty dict
   seen = set(start_vertex)
   while not stack.empty():
        v = stack.pop()
        for u in neighbors of v:
             if not u in seen:
                 seen.add(u)
                 stack.push(u)
                 parent[u] = v
   

   The code is much simpler and more efficient. To find the path itself, we can just iterate starting from the destination vertex and going to the current vertex's parent until we reach the start vertex. This way, it requires a linear amount of time and space.

3. The code itself is rather obscure, in my opinion. Why do we multiply something by -1 here: last.neighbors[neighbor] * -1 (probably you do it to "reverse" the order, but it's not that clear when you read it for the first time)? The fact that neightbors[v] is actually a weight of the edge is also confusing (I would expect to see something like distance or weight in the name of the variable if it stores the length of the edge). By the way, depth-first search works with unweighted graph, so I don't see the point of storing the weights, anyway.