# Return path between graph nodes using depth-first search

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()

new_vert = Vertex(id)
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]

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)
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()

self.neighbours[to] = weight

• The elements of a graph are usually called nodes, which are connected by edges. Vertex is something I associate with "a point" in computer graphics. Might be just me though. – I'll add comments tomorrow Nov 19 '16 at 21:07
• @I'lladdcommentstomorrow I see your point. Do you think Node would be a better name for Vertex? – cycloidistic Nov 19 '16 at 21:35
• Vertex seems quite normal to me. – kraskevich Nov 19 '16 at 21:36
• @cycloidistic no, not a better name, just one I have seen being used in this context more often. This was just a comment fyi. – I'll add comments tomorrow Nov 19 '16 at 22:00
• @I'lladdcommentstomorrow Ok. Makes sense. I think I'll use Node from now on to minimise the chance someone might be a bit confused. – cycloidistic Nov 19 '16 at 22:11

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:

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.
• @cycloidistic Yes, I would make a separate function/method (in the same class as the dfs method) for reconstructing the path given the dict of parents, the destination and the source node. One can break the while loop when the destination is popped, but it's not necessary. We can keep iterating until the stack is empty and then check if the destination is in the seen set. – kraskevich Nov 19 '16 at 22:26