Scribd
Upload
10 views3 pages

BFS and DFS Python Code Examples

The document contains Python code for implementing Breadth-First Search (BFS) and Depth-First Search (DFS) algorithms on a user-defined graph. It includes functions for taking input to create the graph and for executing the search algorithms, returning the results accordingly. The BFS function searches for a goal node, while the DFS function provides the traversal order of the graph.

Uploaded by

laibatahir1272
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
10 views3 pages

BFS and DFS Python Code Examples

The document contains Python code for implementing Breadth-First Search (BFS) and Depth-First Search (DFS) algorithms on a user-defined graph. It includes functions for taking input to create the graph and for executing the search algorithms, returning the results accordingly. The BFS function searches for a goal node, while the DFS function provides the traversal order of the graph.

Uploaded by

laibatahir1272
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

BFS Python code

from collections import deque

def breadth_first_search (graph, start, goal):


# Initialize the frontier (queue) and reached set
frontier = deque([start])
reached = {start}

while frontier:
node = frontier. popleft () # Remove the first element (FIFO)

# Check if goal is found


if node == goal:
return f"Goal {goal} found!"

# Explore neighbors
for child in graph. get(node, []):
if child not in reached:
reached. add(child)
frontier. append(child)
return "Goal not found."

# Taking user input for the graph


graph = {}
num_nodes = int (input("Enter the number of nodes: "))

for _ in range(num_nodes):
node = input ("Enter node: ")
neighbors = input (f"Enter neighbors of {node} (comma-separated): ").split (',')
graph[node] = [[Link]() for neighbor in neighbors if [Link]()]

# Taking input for start and goal


start = input ("Enter the start node: ")
goal = input ("Enter the goal node: ")

# Running BFS
result = breadth_first_search(graph, start, goal)
print(result)

DFS Python code


def dfs_iterative(graph, start):
stack = [start]
discovered = set()
traversal_order = [] # To store the DFS traversal order

while stack:
v = [Link]()
if v not in discovered:
traversal_order.append(v)
[Link](v)
for w in reversed([Link](v, [])): # Reverse to maintain order
if w not in discovered:
[Link](w)

return traversal_order
# Function to take input and display output
def main():
# Taking input for the graph
num_nodes = int(input("Enter the number of nodes: "))
num_edges = int(input("Enter the number of edges: "))

graph = {}
print("Enter the edges (format: u v, where u and v are connected nodes):")
for _ in range(num_edges):
u, v = map(int, input().split())
if u not in graph:
graph[u] = []
if v not in graph:
graph[v] = []
graph[u].append(v)
graph[v].append(u) # Assuming an undirected graph

start_node = int(input("Enter the starting node: "))

# Running DFS and displaying output


print("\nDFS Traversal Order:")
traversal = dfs_iterative(graph, start_node)
print(" -> ".join(map(str, traversal)))
main()

You might also like