Scribd
Upload
22 views2 pages

BFS and DFS Algorithms in Python

The document provides implementations of two graph traversal algorithms: Breadth-First Search (BFS) and Depth-First Search (DFS) using an iterative approach. Both algorithms utilize data structures (queue for BFS and stack for DFS) to explore nodes in a graph, starting from a specified node. Example usage is included for both algorithms, demonstrating their expected outputs.

Uploaded by

guthayaswanth
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
22 views2 pages

BFS and DFS Algorithms in Python

The document provides implementations of two graph traversal algorithms: Breadth-First Search (BFS) and Depth-First Search (DFS) using an iterative approach. Both algorithms utilize data structures (queue for BFS and stack for DFS) to explore nodes in a graph, starting from a specified node. Example usage is included for both algorithms, demonstrating their expected outputs.

Uploaded by

guthayaswanth
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 2

from collections import deque

def bfs(graph, start):


visited = set() # Track visited nodes
queue = deque([start]) # Use a queue to explore nodes level by level
result = [] # Store the order of the nodes

while queue:
node = [Link]() # Dequeue a node
if node not in visited:
[Link](node) # Mark node as visited
[Link](node) # Record the node in the result
# Add only unvisited neighbors to the queue
for neighbor in graph[node]:
if neighbor not in visited:
[Link](neighbor)

return result

# Example usage
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}

print(bfs(graph, 'A')) # Expected output: ['A', 'B', 'C', 'D', 'E', 'F']

#BFS CODE
def dfs_iterative(graph, start):
visited = set() # Track visited nodes
stack = [start] # Use a stack for LIFO order
result = [] # Store the order of the nodes

while stack:
node = [Link]() # Pop a node from the stack
if node not in visited:
[Link](node) # Mark node as visited
[Link](node) # Record the node in the result
# Add neighbors in reverse order to maintain correct DFS order
for neighbor in reversed(graph[node]):
if neighbor not in visited:
[Link](neighbor)

return result

# Example usage
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}

print(dfs_iterative(graph, 'A')) # Expected output: ['A', 'B', 'D', 'E',


'F', 'C']

#DFS CODE

You might also like