🎓 Top 15 Udemy Courses (80-90% Discount): My Udemy Courses - Ramesh Fadatare — All my Udemy courses are real-time and project oriented courses.
▶️ Subscribe to My YouTube Channel (178K+ subscribers): Java Guides on YouTube
▶️ For AI, ChatGPT, Web, Tech, and Generative AI, subscribe to another channel: Ramesh Fadatare on YouTube
1. Introduction
The Breadth-First Search (BFS) is another fundamental algorithm used to explore nodes and edges of a graph. It visits nodes level by level. Starting from a source node, BFS explores all of its neighbors at the present depth before moving on to nodes at the next depth level.
2. Program Overview
In this program, we will:
1. Create a representation for a graph using an adjacency list.
2. Implement the BFS algorithm to traverse through the graph and print each vertex.
3. Code Program
class Graph:
def __init__(self):
# Dictionary to store the adjacency list of the graph
self.graph = dict()
def add_edge(self, u, v):
# Add an edge to the adjacency list
if u not in self.graph:
self.graph[u] = []
self.graph[u].append(v)
def bfs(self, start_vertex):
# Mark the source node as visited and enqueue it
visited = set()
queue = [start_vertex]
while queue:
# Dequeue a vertex from the queue and print it
vertex = queue.pop(0)
if vertex not in visited:
print(vertex, end=" ")
visited.add(vertex)
# Enqueue all adjacent vertices of the dequeued vertex
for neighbour in self.graph[vertex]:
if neighbour not in visited:
queue.append(neighbour)
# Create a sample graph and add edges
g = Graph()
g.add_edge(0, 1)
g.add_edge(0, 2)
g.add_edge(1, 2)
g.add_edge(2, 0)
g.add_edge(2, 3)
g.add_edge(3, 3)
# Perform BFS from vertex 2
print("BFS starting from vertex 2:")
g.bfs(2)
Output:
BFS starting from vertex 2: 2 0 3 1
4. Step By Step Explanation
1. The Graph class initializes an empty graph using a dictionary to represent the adjacency list.
2. The add_edge method allows us to add edges to the graph.
3. The bfs method performs a breadth-first traversal of the graph. It uses a set visited to track the visited vertices and a queue to maintain the BFS traversal order.
4. In the sample provided, we created a graph with 4 vertices and executed BFS starting from vertex 2. The output displays the order in which nodes are visited following BFS.
My Top and Bestseller Udemy Courses. The sale is going on with a 70 - 80% discount. The discount coupon has been added to each course below:
Build REST APIs with Spring Boot 4, Spring Security 7, and JWT
![[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25](https://img-c.udemycdn.com/course/750x422/6852721_b512_2.jpg "[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25")
[NEW] Learn Apache Maven with IntelliJ IDEA and Java 25
ChatGPT + Generative AI + Prompt Engineering for Beginners
Spring 7 and Spring Boot 4 for Beginners (Includes 8 Projects)
Available in Udemy for Business
Building Real-Time REST APIs with Spring Boot - Blog App
Available in Udemy for Business
Building Microservices with Spring Boot and Spring Cloud
Available in Udemy for Business
Java Full-Stack Developer Course with Spring Boot and React JS
Available in Udemy for Business
Build 5 Spring Boot Projects with Java: Line-by-Line Coding
Testing Spring Boot Application with JUnit and Mockito
Available in Udemy for Business
Spring Boot Thymeleaf Real-Time Web Application - Blog App
Available in Udemy for Business
Master Spring Data JPA with Hibernate
Available in Udemy for Business
Spring Boot + Apache Kafka Course - The Practical Guide
Available in Udemy for Business
Comments
Post a Comment
Leave Comment