Code Review Asked on February 23, 2021
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()
Lists in Python are already stacks. It would be better if you used a raw list
as people are more familiar with list
s 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)
Correct answer by Peilonrayz on February 23, 2021
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP