Scribd
Upload
12 views8 pages

Python DFS and BFS Implementation

The document outlines a programming task to implement Depth First Search (DFS) and Breadth First Search (BFS) algorithms using Python. It provides detailed descriptions of how both algorithms work, along with sample code for creating a graph, adding vertices and edges, and executing the search algorithms. The conclusion states that the implementation of both BFS and DFS was successfully completed.

Uploaded by

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

Python DFS and BFS Implementation

The document outlines a programming task to implement Depth First Search (DFS) and Breadth First Search (BFS) algorithms using Python. It provides detailed descriptions of how both algorithms work, along with sample code for creating a graph, adding vertices and edges, and executing the search algorithms. The conclusion states that the implementation of both BFS and DFS was successfully completed.

Uploaded by

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

Artificial Intelligence & Expert Systems Lab Roll No :234G1A0564

Task 1:
Write a program to implement DFS and BFS.
AIM: Implementing Depth First Search (DFS) and Breadth First Search (BFS) using
Python Programming.

Description: DFS is usually implemented using a Stack or by the use of recursion


(which utilizes the call stack), while BFS is usually implemented using a Queue.

How it works:

DFS:
1. Start DFS traversal on a vertex.
2. Do a recursive DFS traversal on each of the adjacent vertices as long as they are
not already visited.

BFS:

3. Put the starting vertex into the queue.


4. For each vertex taken from the queue, visit the vertex, then put all unvisited
adjacent vertices into the queue.
5. Continue as long as there are vertices in the queue.

Program for DFS:

class Graph:
def __init__(self, size):
self.adj_matrix = [[0] * size for _ in range(size)]
[Link] = size
self.vertex_data = [''] * size

def add_edge(self, u, v):


if 0 <= u < [Link] and 0 <= v < [Link]:
self.adj_matrix[u][v] = 1
self.adj_matrix[v][u] = 1

def add_vertex_data(self, vertex, data):


if 0 <= vertex < [Link]:
self.vertex_data[vertex] = data

def print_graph(self):
print("Adjacency Matrix:")
for row in self.adj_matrix:
print(' '.join(map(str, row)))
print("\nVertex Data:")
for vertex, data in enumerate(self.vertex_data):
print(f"Vertex {vertex}: {data}")

Department Of Computer Science And Engineering 1


Artificial Intelligence & Expert Systems Lab Roll No :234G1A0564

def dfs_util(self, v, visited):


visited[v] = True
print(self.vertex_data[v], end=' ')

for i in range([Link]):
if self.adj_matrix[v][i] == 1 and not visited[i]:
self.dfs_util(i, visited)

def dfs(self, start_vertex_data):


visited = [False] * [Link]
start_vertex = self.vertex_data.index(start_vertex_data)
self.dfs_util(start_vertex, visited)

g = Graph(7)

g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')

g.add_edge(3, 0) # D-A
g.add_edge(0, 2) # A-C
g.add_edge(0, 3) # A-D
g.add_edge(0, 4) # A-E
g.add_edge(4, 2) # E-C
g.add_edge(2, 5) # C-F
g.add_edge(2, 1) # C-B
g.add_edge(2, 6) # C-G
g.add_edge(1, 5) # B-F

g.print_graph()

print("\nDepth First Search starting from vertex D:")


[Link]('D')

Department Of Computer Science And Engineering 2


Artificial Intelligence & Expert Systems Lab Roll No :234G1A0564

Output:

Program for BFS:

class Graph:

def __init__(self, size):

self.adj_matrix = [[0] * size for _ in range(size)]

[Link]=size

self.vertex_data = [''] * size

def add_edge(self, u, v):

if 0 <= u < [Link] and 0 <= v < [Link]:

self.adj_matrix[u][v] = 1

self.adj_matrix[v][u] = 1

def add_vertex_data(self, vertex, data):

Department Of Computer Science And Engineering 3


Artificial Intelligence & Expert Systems Lab Roll No :234G1A0564

if 0 <= vertex < [Link]:

self.vertex_data[vertex] = data

def print_graph(self):

print("Adjacency Matrix:")

for row in self.adj_matrix:

print(' '.join(map(str, row)))

print("\nVertex Data:")

for vertex, data in enumerate(self.vertex_data):

print(f"Vertex {vertex}: {data}")

def bfs(self, start_vertex_data):

queue = [self.vertex_data.index(start_vertex_data)]

visited = [False] * [Link]

visited[queue[0]] = True

while queue:

current_vertex = [Link](0)

print(self.vertex_data[current_vertex], end=' ')

for i in range([Link]):

if self.adj_matrix[current_vertex][i] == 1 and not visited[i]:

[Link](i)

visited[i] = True

g = Graph(7)

g.add_vertex_data(0, 'A')

g.add_vertex_data(1, 'B')

g.add_vertex_data(2, 'C')

g.add_vertex_data(3, 'D')

g.add_vertex_data(4, 'E')

g.add_vertex_data(5, 'F')

g.add_vertex_data(6, 'G')

g.add_edge(3, 0) # D - A

Department Of Computer Science And Engineering 4


Artificial Intelligence & Expert Systems Lab Roll No :234G1A0564

g.add_edge(0, 2) # A - C

g.add_edge(0, 3) # A - D

g.add_edge(0, 4) # A - E

g.add_edge(4, 2) # E - C

g.add_edge(2, 5) # C - F

g.add_edge(2, 1) # C - B

g.add_edge(2, 6) # C - G

g.add_edge(1, 5) # B - F

g.print_graph()

print("\nBreadth First Search starting from vertex D:")

[Link]('D')

Output:

Department Of Computer Science And Engineering 5


Artificial Intelligence & Expert Systems Lab Roll No :234G1A0564

Code for both BFS and DFS traversal :

class Graph:

def __init__(self, size):


self.adj_matrix = [[0] * size for _ in range(size)]
[Link] = size
self.vertex_data = [''] * size

def add_edge(self, u, v):


if 0 <= u < [Link] and 0 <= v < [Link]:
self.adj_matrix[u][v] = 1
#self.adj_matrix[v][u] = 1

def add_vertex_data(self, vertex, data):


if 0 <= vertex < [Link]:
self.vertex_data[vertex] = data

def print_graph(self):
print("Adjacency Matrix:")
for row in self.adj_matrix:
print(' '.join(map(str, row)))
print("\nVertex Data:")
for vertex, data in enumerate(self.vertex_data):
print(f"Vertex {vertex}: {data}")

def dfs_util(self, v, visited):


visited[v] = True
print(self.vertex_data[v], end=' ')

for i in range([Link]):
if self.adj_matrix[v][i] == 1 and not visited[i]:
self.dfs_util(i, visited)

def dfs(self, start_vertex_data):


visited = [False] * [Link]

start_vertex = self.vertex_data.index(start_vertex_data)
self.dfs_util(start_vertex, visited)

def bfs(self, start_vertex_data):

Department Of Computer Science And Engineering 6


Artificial Intelligence & Expert Systems Lab Roll No :234G1A0564

queue = [self.vertex_data.index(start_vertex_data)]
visited = [False] * [Link]
visited[queue[0]] = True

while queue:
current_vertex = [Link](0)
print(self.vertex_data[current_vertex], end=' ')

for i in range([Link]):
if self.adj_matrix[current_vertex][i] == 1 and not visited[i]:
[Link](i)
visited[i] = True

g = Graph(7)

g.add_vertex_data(0, 'A')
g.add_vertex_data(1, 'B')
g.add_vertex_data(2, 'C')
g.add_vertex_data(3, 'D')
g.add_vertex_data(4, 'E')
g.add_vertex_data(5, 'F')
g.add_vertex_data(6, 'G')

g.add_edge(3, 0) # D -> A
g.add_edge(3, 4) # D -> E
g.add_edge(4, 0) # E -> A
g.add_edge(0, 2) # A -> C
g.add_edge(2, 5) # C -> F
g.add_edge(2, 6) # C -> G
g.add_edge(5, 1) # F -> B
g.add_edge(1, 2) # B -> C

g.print_graph()

print("\nDepth First Search starting from vertex D:")


[Link]('D')

print("\n\nBreadth First Search starting from vertex D:")


[Link]('D')

Department Of Computer Science And Engineering 7


Artificial Intelligence & Expert Systems Lab Roll No :234G1A0564

Output:

Conclusion :
Thus,I have successfully implemented BFS and DFS by using
Python Programming.

Department Of Computer Science And Engineering 8

Common questions

Powered by AI

The adjacency matrix implementation results in O(V^2) complexity for both DFS and BFS, since every vertex pair might be checked for an edge presence. While BFS inherently processes every vertex and edge once, achieving O(V + E) typical complexity in a list representation, the matrix's structural limitations force higher constant-time operations. Thus, computational overhead is a direct consequence, necessitating careful method choice depending on graph density and traversal needs .

Enhancements could include using an adjacency list instead of a matrix to handle sparse graphs more efficiently, which reduces space complexity to O(V + E). Incorporating iterative deepening DFS can prevent stack overflow issues in deep graphs. Additionally, applying heuristics or weight-based traversal algorithms like A* for more efficient pathfinding in specific cases might be beneficial. Implementing parallelization techniques could also optimize BFS for large datasets by distributing the processing of nodes at the same level .

A fixed-size adjacency matrix can lead to excessive memory usage in sparse graphs and imposes a limit on the number of vertices based on initial size allocation. It inefficiently stores empty spaces for non-existent edges. These limitations can be addressed by using dynamic data structures, such as adjacency lists, which grow as needed, thus optimizing memory usage. Alternatively, compressed sparse row (CSR) or column formats can be employed for further efficiency .

DFS is implemented using a Stack or recursion to explore vertices as deep as possible before backtracking, whereas BFS uses a Queue to explore all neighbors of a vertex before moving on to the next level. In the provided implementation, DFS is done by recursively visiting adjacent unvisited vertices, while BFS involves visiting a vertex, enqueuing all its unvisited neighbors, and continuing until there are no more vertices in the queue .

DFS is preferred in scenarios requiring exhaustive path exploration, like solving mazes or puzzles, due to its ability to explore deeper paths first. Conversely, BFS is advantageous in shortest-path scenarios, such as networking problems, because it explores all nodes at the present 'depth' before moving on. The implementation reflects this by using recursion for DFS, suitable for deeper exploration, and a queue for BFS to ensure all vertices at one level are visited before the next .

Using an adjacency matrix provides a straightforward method for representing the presence or absence of edges between any two vertices, making it easy to implement DFS and BFS by checking connections in constant time. However, it requires O(n^2) space, which can be inefficient for sparse graphs. The matrix's dense representation allows for quick edge checks between any node pairs but can lead to excessive memory usage and inefficiencies in terms of traversal through non-existent edges (zero entries).

The graph implementation uses an adjacency matrix to represent edges and a list to store vertex data, allowing each vertex to hold specific information. In both DFS and BFS, the `vertex_data` list is leveraged to print the data of each vertex as it is visited. This ensures that the traversal not only tracks vertex connections but also outputs relevant data for each one .

Vertex data is stored in a list aligned with vertex indices, which allows direct data access during traversal operations like DFS and BFS. This uniform structure facilitates easy data handling and output during traversal operations, providing a simple lookup mechanism for real-world cases requiring attribute access with minimal overhead. However, fixed indices and data handling might lack flexibility in dynamically changing graph scenarios .

The document's implementation of BFS and DFS aims to provide a clear understanding of fundamental graph traversal techniques, demonstrating both adjacency matrix usage and traversal method differences. The goals of easy execution, visualization, and data management were addressed by printing adjacency matrices and vertex data, indicating robust practices in representing and exploring graph data, though at the cost of space efficiency typical of adjacency matrices .

In the DFS implementation, recursion implicitly uses the call stack to manage state, pushing function calls for each recursive visit to a node and popping them as nodes are backtracked. This can lead to stack overflow in very deep or infinite graphs due to excessive recursion depth. To counter this, iterative implementations using explicit stacks can prevent stack overflow and offer better control over stack usage .

You might also like