Scribd
Upload
2 views3 pages

DFS and BFS Algorithms in Python

The document contains a Python program that implements Depth-First Search (DFS) using an adjacency matrix and Breadth-First Search (BFS) using an adjacency list. It provides a menu for users to choose between DFS and BFS traversals starting from location 'A'. The program continues to prompt the user until they choose to exit.

Uploaded by

meerampatel2006
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
2 views3 pages

DFS and BFS Algorithms in Python

The document contains a Python program that implements Depth-First Search (DFS) using an adjacency matrix and Breadth-First Search (BFS) using an adjacency list. It provides a menu for users to choose between DFS and BFS traversals starting from location 'A'. The program continues to prompt the user until they choose to exit.

Uploaded by

meerampatel2006
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

ASSIGNMENT NO.

-- 7

from collections import deque

locations = ['A', 'B', 'C', 'D']

locations_index = {name: idx for idx, name in enumerate(locations)}

# ----- DFS using Adjacency Matrix -----

adj_matrix = [

[0, 1, 1, 0],

[1, 0, 0, 1],

[1, 0, 0, 1],

[0, 1, 1, 0]

def dfs_matrix(start):

visited = [False] * len(locations)

result = []

def dfs(node):

visited[node] = True

[Link](locations[node])

for neighbour in range(len(adj_matrix)):

if adj_matrix[node][neighbour] == 1 and not visited[neighbour]:

dfs(neighbour)

dfs(locations_index[start])

return result

# ----- BFS using Adjacency List -----

adj_list = {

'A': ['B', 'C'],

'B': ['A', 'D'],

'C': ['A', 'D'],


ASSIGNMENT NO. -- 7
'D': ['B', 'C']

def bfs_list(start):

visited = set([start])

queue = deque([start])

result = []

while queue:

node = [Link]()

[Link](node)

for neighbour in adj_list[node]:

if neighbour not in visited:

[Link](neighbour)

[Link](neighbour)

return result

# ----- Menu -----

def menu():

while True:

print("\nMenu")

print("1. DFS")

print("2. BFS")

print("3. Exit")

choice = input("Enter your choice: ")

if choice == '1':

start_location = 'A'

dfs_result = dfs_matrix(start_location)

print("DFS Traversal (using adjacency matrix):", dfs_result)

elif choice == '2':


ASSIGNMENT NO. -- 7
start_location = 'A'

bfs_result = bfs_list(start_location)

print("BFS Traversal (using adjacency list):", bfs_result)

elif choice == '3':

print("Exiting...")

break

else:

print("Invalid choice, try again!")

# Run program

menu()

You might also like