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

Peilonrayz · Accepted Answer

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)

Depth First Search Using Stack in Python

One Answer

Add your own answers!

Ask a Question