Introduction
Breadth First Search (BFS) is a graph traversal algorithm that traverses the graph in a breadth-ward motion. In other words, it explores all the vertices at the same level before moving on to the vertices at the next level. BFS is often used to find the shortest path between two nodes in an unweighted graph, as it guarantees that the first path found is one of the shortest paths.
BFS starts from a source vertex and visits all its adjacent vertices, then visits all the adjacent vertices of these visited vertices, until all the vertices are visited. BFS uses a queue data structure to keep track of the visited vertices and their adjacent vertices. In this blog post we’ll dive into understanding Breadth First Search and how to implement it in Python!
What is BFS?
BFS or Breadth First Search is a graph traversal algorithm that explores all the vertices of a graph in breadth-first order, i.e., it visits all the vertices at the same level before moving to the next level. This means that BFS starts at the root node (or any arbitrary node) and explores all its neighbors first, then moves to the next level of nodes until all the nodes in the graph have been visited.
BFS is commonly used to find the shortest path between two nodes in an unweighted graph. It can also be used for other applications such as finding connected components, detecting cycles, and testing bipartiteness.
To implement BFS in Python, we typically use a queue data structure to keep track of the nodes that need to be explored. We start by adding the root node to the queue and marking it as visited. Then we enter a loop where we dequeue a node from the queue and explore its neighbors by adding them to the queue if they haven’t been visited yet.
Here’s an example implementation of BFS in Python:
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
visited.add(vertex)
print(vertex)
queue.extend(graph[vertex] - visited)
# Example usage
graph = {
'A': set(['B', 'C']),
'B': set(['A', 'D', 'E']),
'C': set(['A', 'F']),
'D': set(['B']),
'E': set(['B', 'F']),
'F': set(['C', 'E'])
}
bfs(graph, 'A')
In this example, we use a dictionary to represent an undirected graph where each key is a vertex and its value is a set of neighboring vertices. The `bfs` function takes as input the graph and a starting vertex, and outputs the nodes visited in BFS order. We use a set to keep track of the visited nodes and a deque to implement the queue. The `queue.extend` method adds all the unvisited neighbors of the current node to the end of the queue.
How does BFS work?
BFS, or Breadth First Search, is a graph traversal algorithm that starts at the root node and explores all the neighboring nodes at the present depth level before moving on to explore the nodes at the next depth level. In simpler terms, BFS visits all the nodes at the same level before moving down to the next level.
The algorithm works by keeping track of all the visited nodes in a queue. We begin by adding the starting node to the queue and marking it as visited. Then, while there are still nodes in the queue, we dequeue the first node in the queue and add all its unvisited neighbors to the end of the queue. We mark these neighbors as visited and continue this process until we have visited all reachable nodes.
BFS is commonly used for traversing trees or graphs that are not too deep, as it requires storing all visited nodes in memory. However, BFS guarantees that it will find the shortest path between two nodes if one exists.
Let’s take a look at a simple implementation of BFS in Python:
from collections import deque
def bfs(graph, start):
visited = set()
queue = deque([start])
while queue:
vertex = queue.popleft()
if vertex not in visited:
visited.add(vertex)
print(vertex)
queue.extend(graph[vertex] - visited)
# Example usage
graph = {
'A': set(['B', 'C']),
'B': set(['A', 'D', 'E']),
'C': set(['A', 'F']),
'D': set(['B']),
'E': set(['B', 'F']),
'F': set(['C', 'E'])
}
bfs(graph, 'A')
In this example, we define a simple undirected graph using a dictionary with sets as values. We then call our `bfs` function with this graph and starting node ‘A’. The function uses a set to keep track of visited nodes and a deque to store the nodes to be visited. We then loop through the queue, dequeueing the first node and adding its unvisited neighbors to the end of the queue. We print each visited node as we go.
BFS Algorithm
BFS (Breadth First Search) is a graph traversal algorithm that visits all the vertices of a graph in breadth-first order, i.e., it visits all the vertices at the same level before moving on to the next level. BFS uses a queue data structure to keep track of the nodes that need to be visited.
The implementation of BFS can be broken down into the following steps:
Step 1: Enqueue the starting node
The first step is to enqueue the starting node into a queue data structure. This node is marked as visited so that it’s not revisited later.
Step 2: Dequeue a node and mark it as visited
In this step, we dequeue a node from the queue and mark it as visited. We then process this node.
Step 3: Enqueue all adjacent nodes of the dequeued node that are not yet visited
We then enqueue all the adjacent nodes of the dequeued node that have not been visited yet. These nodes are added to the end of the queue.
Step 4: Repeat steps 2-3 until the queue is empty
We repeat steps 2 and 3 until there are no more nodes left in the queue. This means that we have visited all the nodes in the graph.
Here’s an example implementation of BFS in Python:
def bfs(graph, start):
queue = [start]
visited = set([start])
while queue:
vertex = queue.pop(0)
print(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
queue.append(neighbor)
visited.add(neighbor)
In this implementation, `graph` is a dictionary representing an adjacency list of the graph, where each key represents a vertex and its value is a list of its adjacent vertices. `start` is the starting vertex from which we want to traverse the graph.
We start by initializing a queue with the starting vertex and marking it as visited. We then enter a loop that dequeues a vertex from the queue, prints it, and adds its unvisited neighbors to the end of the queue. This process continues until there are no more vertices left in the queue.
Overall, BFS is a simple but powerful algorithm for traversing graphs in breadth-first order. It has many applications in computer science, such as finding the shortest path between two nodes and detecting cycles in a graph.
BFS Implementation in Python
In this section, we will cover the implementation of a Breadth-First Search algorithm in Python. The BFS algorithm is used for searching a graph or tree data structure. It starts at the root node and explores all the nodes at the current depth before moving on to the next level.
Creating the Graph
Before we can implement the BFS algorithm, we need to create a graph to search. In this example, we will use a dictionary to represent our graph. Each key in the dictionary will represent a node, and its value will be a list of adjacent nodes.
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F', 'G'],
'D': [],
'E': ['F'],
'F': [],
'G': []
}
This graph has seven nodes labeled A through G. Node A has two adjacent nodes B and C, node B has two adjacent nodes D and E, and so on.
BFS Function Implementation
Now that we have our graph, let’s implement the BFS algorithm to search it. The BFS function takes two arguments: the graph and the starting node.
def bfs(graph, start):
visited = [] # List to keep track of visited nodes
queue = [start] # Initialize a queue
while queue:
node = queue.pop(0)
if node not in visited:
visited.append(node)
neighbours = graph[node]
for neighbour in neighbours:
queue.append(neighbour)
return visited
The BFS function initializes an empty list to keep track of visited nodes and a queue containing only the starting node. It then enters into a loop that continues until there are no more nodes left in the queue.
In each iteration of the loop, the function removes the first node from the queue and checks if it has already been visited. If not, it adds it to the visited list and gets all its adjacent nodes. It then adds these adjacent nodes to the end of the queue.
Testing the BFS Function
Now that we have implemented our BFS function, let’s test it on our graph by searching for all nodes starting from node A.
print(bfs(graph, 'A'))
This should output:
[‘A’, ‘B’, ‘C’, ‘D’, ‘E’, ‘F’, ‘G’]
This means that we have successfully searched all seven nodes in our graph starting from node A using the BFS algorithm.
Conclusion
In conclusion, the Breadth First Search algorithm is a popular and powerful technique for traversing graphs in a breadth-first manner. It is widely used in various fields such as network routing, social network analysis, and web crawling.
In this tutorial, we have covered the basic concepts of the BFS algorithm and provided an implementation in Python. We started by defining the problem statement and discussing the key features of BFS. We then walked through the step-by-step process of implementing BFS using a queue data structure.
We also highlighted some important use cases where BFS can be applied, such as finding the shortest path between two nodes in a graph or detecting cycles in a graph.
Overall, BFS is a fundamental algorithm that every programmer should be familiar with. With its simple yet effective approach to traversing graphs, it is a valuable tool for solving a wide range of problems. By mastering this algorithm, you’ll be well on your way to becoming a proficient Python programmer.
Interested in learning more? Check out our Introduction to Python course!
Your FREE Guide to Become a Data Scientist
Discover the path to becoming a data scientist with our comprehensive FREE guide! Unlock your potential in this in-demand field and access valuable resources to kickstart your journey.
Don’t wait, download now and transform your career!
