Learn how to implement depth-first search without recursion using a stack data structure. Master this essential technique for traversing graphs in a memory-efficient way.
class Graph:
def __init__(self):
self.adjacency_list = {}
def add_vertex(self, vertex):
if vertex not in self.adjacency_list:
self.adjacency_list[vertex] = []
def add_edge(self, v1, v2):
self.adjacency_list[v1].append(v2)
self.adjacency_list[v2].append(v1)
def depth_first_iterative(self, start):
stack = [start]
result = []
visited = {}
visited[start] = True
while stack:
current_vertex = stack.pop()
result.append(current_vertex)
# Visit all unvisited neighbors
for neighbor in self.adjacency_list[current_vertex]:
if not visited.get(neighbor):
visited[neighbor] = True
stack.append(neighbor)
return result
def depth_first_recursive(self, start):
result = []
visited = {}
adjacency_list = self.adjacency_list
def dfs(vertex):
if not vertex:
return
visited[vertex] = True
result.append(vertex)
for neighbor in adjacency_list[vertex]:
if not visited.get(neighbor):
dfs(neighbor)
dfs(start)
return result
// Create a graph
g = Graph()
g.add_vertex("A")
g.add_vertex("B")
g.add_vertex("C")
g.add_vertex("D")
g.add_vertex("E")
g.add_vertex("F")
g.add_edge("A", "B")
g.add_edge("A", "C")
g.add_edge("B", "D")
g.add_edge("C", "E")
g.add_edge("D", "E")
g.add_edge("D", "F")
g.add_edge("E", "F")
# The graph looks like:
# A
# / \
# B C
# | |
# D---E
# \ /
# F
print(g.depth_first_iterative("A")) # ["A", "C", "E", "F", "D", "B"]
Implement a function that finds a path between two vertices in a graph using iterative DFS.
findPathDFS(start, end) to the Graph classclass Graph:
def __init__(self):
self.adjacency_list = {}
def add_vertex(self, vertex):
if vertex not in self.adjacency_list:
self.adjacency_list[vertex] = []
def add_edge(self, v1, v2):
self.adjacency_list[v1].append(v2)
self.adjacency_list[v2].append(v1)
# Implement your solution here
def find_path_dfs(self, start, end):
# Your code here
pass # Placeholder for the new method
// Create a test graph
graph = Graph()
graph.add_vertex("A")
graph.add_vertex("B")
graph.add_vertex("C")
graph.add_vertex("D")
graph.add_vertex("E")
graph.add_vertex("F")
graph.add_edge("A", "B")
graph.add_edge("A", "C")
graph.add_edge("B", "D")
graph.add_edge("C", "E")
graph.add_edge("D", "E")
graph.add_edge("D", "F")
graph.add_edge("E", "F")
print(graph.find_path_dfs("A", "F")) # Should return a valid path, e.g., ["A", "B", "D", "F"]
print(graph.find_path_dfs("A", "G")) # Should return []
After completing this challenge, try these extensions: