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)

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