4
\$\begingroup\$

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()
\$\endgroup\$
5
\$\begingroup\$

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)
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Saurabh Aug 2 at 4:58
  • \$\begingroup\$ @Saurabh That is understandable. If you at all feel my explanation lacking just say and I'll amend it when possible :) \$\endgroup\$ – Peilonrayz Aug 2 at 5:00
  • 1
    \$\begingroup\$ thank you for a very clear & detailed explanation :) \$\endgroup\$ – Saurabh Aug 2 at 5:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.