# Depth First Search Using Stack in Python

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():
1: [2, 3],
2: [4, 5],
3: [5],
4: [6],
5: [6],
6: [7],
7: []
}
print(dfs_path)

if __name__ == '__main__':
main()


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
for neighbor in graph[vertex]:
stack.append(neighbor)

• 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. Aug 2, 2020 at 4:58
• @Saurabh That is understandable. If you at all feel my explanation lacking just say and I'll amend it when possible :) Aug 2, 2020 at 5:00
• thank you for a very clear & detailed explanation :) Aug 2, 2020 at 5:06
• @Saurabh if you want to be explicit then use types. Define a new type stack as follows Stack = list. It might seem silly but it achieves the explicitness that you want ;) Jun 29, 2021 at 22:09
• @CharlieParker FWIW Stack would not be a new type, just an 'alias'. If you do type(Stack([])) you'll see the code is still just a plain list. If you want a new type you'd have to inherit from list - class Stack(list): pass or Stack = type("Stack", (list,), {}). Jun 29, 2021 at 22:29

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
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,), {}).

• Warning: NoReturn is not what you or the OP wants - SO answer. The return type should be an Iterator. Jun 29, 2021 at 22:34
• thanks! Removed that. Jun 29, 2021 at 22:35
• @Peilonrayz thanks for the update and comments! Have to admit you have a difficult name to remember for us Hispanic speaking peeps! Thanks again. Jun 30, 2021 at 12:42