Welcome to our comprehensive guide on finding the shortest path in an unweighted graph using Breadth-First Search (BFS)! šÆ
In this lesson, we'll explore:
Let's dive in!
A graph is a collection of nodes (also called vertices) and edges that connect these nodes. Each edge represents a connection between two nodes.
An unweighted graph is a specific type of graph where the edges do not have any associated weights. In other words, all edges have the same weight, usually 1.
BFS is a popular algorithm used to traverse or search through a graph, ensuring that nodes are visited in a breadthwise manner. It starts at the root node and explores all the nodes at the current depth level before moving to the next level. This is particularly useful in finding the shortest path between nodes in an unweighted graph.
Here's a simple BFS implementation in Python for an unweighted graph. We'll use an adjacency list for convenience.
def bfs(graph, start):
visited = set()
queue = [(start, [start])]
while queue:
(node, path) = queue.pop(0)
if node not in visited:
visited.add(node)
for neighbor in graph[node]:
if neighbor not in visited:
queue.append((neighbor, path + [neighbor]))
return visitedš” Pro Tip: Use a dictionary to represent the graph with nodes as keys and lists of their neighbors as values.
BFS is used in various real-world scenarios, such as:
Which of the following is a type of graph where all edges have the same weight?