Depth First Search Using Stack in Python

Question

I have implemented a depth first search using a stack (in a separate class). Any suggestions please on improvements for the below code:

class Stack:
 """(LIFO) queuing policy implemented using python list."""
 def __init__(self):
 self.list = []
 def push(self, item):
 """Push 'item' onto the stack."""
 self.list.append(item)
 def pop(self):
 """Pop the most recently pushed item from the stack."""
 return self.list.pop()
 def top(self):
 """Return the last element."""
 return self.list[-1]
 def is_empty(self):
 """Returns true if the stack is empty."""
 return len(self.list) == 0
def depth_first_search(graph, start):
 stack = Stack()
 stack.push(start)
 path = []
 while not stack.is_empty():
 vertex = stack.pop()
 if vertex in path:
 continue
 path.append(vertex)
 for neighbor in graph[vertex]:
 stack.push(neighbor)
 return path
def main():
 adjacency_matrix = {
 1: [2, 3],
 2: [4, 5],
 3: [5],
 4: [6],
 5: [6],
 6: [7],
 7: []
 }
 dfs_path = depth_first_search(adjacency_matrix, 1)
 print(dfs_path)
if __name__ == '__main__':
 main()

Answer 1

Lists in Python are already stacks. It would be better if you used a raw list as people are more familiar with lists then a custom Stack class.

When using a plain Python list the while loop can take advantage of lists being truthy if they have items. This allows you to do while stack: instead.

I would prefer this to be a generator function as we likely won't need the entire DFS path. path can then be a set for \$O(1)\$ lookup rather than a list with \$O(n)\$ lookup. ("if vertex in path:")

def depth_first_search(graph, start):
 stack = [start]
 visited = set()
 while stack:
 vertex = stack.pop()
 if vertex in visited:
 continue
 yield vertex
 visited.add(vertex)
 for neighbor in graph[vertex]:
 stack.append(neighbor)

• Saurabh: Small clarification: the reason I've used a separate Stack class is because DFS uses stack. Although python lists are essentially stacks, I though it would be better if I'm explicit about it.

Answer 2

Since Saurabh mentioned he wanted to be explicit:

from typing import Any 
Stack = list[Any]
def depth_first_search(graph, start) -> Iterator:
 stack : Stack = [start]
 visited = set()
 while stack:
 vertex = stack.pop()
 if vertex in visited:
 continue
 yield vertex
 visited.add(vertex)
 for neighbor in graph[vertex]:
 stack.append(neighbor)

though it might look superficial I think it is really nice to have Stack explicitly telling the user that the current list with start is a Stack. So we get double explicitness from the type definition and the initialization of your stack - with no user defined stacks.

---

Edit:

Comment from Peilonrayz:

if you want a new type you'd have to inherit from list - class Stack(list): pass or Stack = type("Stack", (list,), {}).