What is a Graph Algorithm? In the field of computer science, a graph is an abstract way of representing connectivity using nodes (vertices) and edges, denoted as G = (V, E). Graph nodes are labelled from 1 to n (representing the total number of nodes), and edges connect these pairs of nodes. These connections can be unidirectional (directed) or bidirectional (undirected).
Graph algorithms solve complex problems such as finding the shortest path, analyzing network flow, and graph coloring. To understand BFS, we first need to understand that graphs are typically represented in two ways: an Adjacency Matrix or an Adjacency List.
Some popular types of graphs include:
- Tree: An acyclic graph.
- DAG: Directed Acyclic Graph.
- Bipartite Graph: Nodes are separated into two groups, S and T, such that edges exist only between groups.
What is the Breadth-First Search Algorithm?
Breadth-First Search (BFS) is a fundamental graph traversal algorithm. Unlike DFS (Depth-First Search), which dives deep into a branch, BFS explores the graph layer by layer. Starting from a source node (or starting node) S, the algorithm explores the edges to "discover" every vertex V reachable from S.
The algorithm is responsible for computing the distance from the source S to all reachable nodes. It discovers vertices in the order of their distance from the source—meaning it visits all neighbors at distance k before moving to neighbors at distance k+1.
Shortest Path: In an unweighted graph, the shortest path is defined as the path from source S to vertex V containing the smallest number of edges. BFS naturally produces this path.
The Algorithm: Logic & Coloring
Breadth-first search is named because it spreads broadly across the graph. To keep track of progress and prevent infinite loops, the algorithm colors each vertex:
- White: Undiscovered/Unvisited.
- Gray: Discovered (in the Queue) but neighbors not yet fully explored.
- Black: Fully explored.
The algorithm uses a Queue (FIFO). It starts with the root/source vertex S (colored Gray). Whenever the algorithm encounters a White vertex v while scanning the adjacency list of a Gray vertex u, vertex v is added to the tree. Here, u becomes the predecessor (parent) of v.
The Pseudocode
BFS(G, s)
1 for each vertex u in G.V - {s}
2 u.color = WHITE
3 u.d = infinity
4 u.parent = NIL
5 s.color = GRAY
6 s.d = 0
7 s.parent = NIL
8 Q = empty
9 ENQUEUE(Q, s)
10 while Q is not empty
11 u = DEQUEUE(Q)
12 for each v in G.Adj[u]
13 if v.color == WHITE
14 v.color = GRAY
15 v.d = u.d + 1
16 v.parent = u
17 ENQUEUE(Q, v)
18 u.color = BLACK
Example Working of Breadth-First Search Algorithm
The operation of BFS on an undirected graph. Tree edges are shown as shaded as they are produced by BFS. The value of u.d appears within each vertex u. The queue Q is shown at the beginning of each iteration of the while loop. Vertex distances appear below vertices in the queue.
Once all the nodes are visited, the algorithm computes the shortest path between the root node s and its linking nodes.
Python Implementation of BFS
Here is a modern Python implementation using a deque for efficient queue operations. This code prints the nodes in the order they are visited.
from collections import deque
def bfs(graph, start_node):
# Keep track of visited nodes to avoid cycles
visited = set()
queue = deque([start_node])
visited.add(start_node)
while queue:
# Dequeue the first element (FIFO)
vertex = queue.popleft()
print(vertex, end=" ")
# Loop through neighbors
for neighbor in graph[vertex]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
# Example Usage: Adjacency List
graph = {
'A': ['B', 'C'],
'B': ['D', 'E'],
'C': ['F'],
'D': [],
'E': ['F'],
'F': []
}
print("BFS Traversal:")
bfs(graph, 'A')
# Output: A B C D E F
Complexity Analysis of BFS
The efficiency of the algorithm is calculated based on the graph representation G = (V, E).
- Time Complexity: O(V + E). After initialization, each vertex is Enqueued and Dequeued at most once (O(V)). The algorithm scans the adjacency list of every vertex at most once (O(E)). Thus, total time is linear: O(V + E).
- Space Complexity: O(V). In the worst case, we might need to store all vertices in the Queue.
BFS vs. DFS: What's the Difference?
While BFS scans the graph layer-by-layer, DFS (Depth-First Search) goes as deep as possible before backtracking. Here is the comparison:
| Feature | BFS (Breadth-First) | DFS (Depth-First) |
|---|---|---|
| Data Structure | Queue (FIFO) | Stack (LIFO) or Recursion |
| Traversal Strategy | Layer by layer (Wide) | Deep path first (Deep) |
| Best Application | Shortest Path (Unweighted Graph) | Path Existence, Mazes, Cycles |
Breadth-First Search Applications
BFS is robust and provides the highest level of accuracy for specific problems. Key real-life applications include:
- Unweighted Graphs: Finding the shortest path and minimum spanning tree to visit all vertices.
- P2P Networks: Implemented to find nearest and neighboring nodes in a peer-to-peer network faster.
- Web Crawlers: Search engines use BFS to build indexes. The implementation begins from the source web page and visits all links acting as nodes.
- Navigation Systems: Neighboring locations are detected from the main location using BFS logic.
- Network Broadcasting: A broadcasted packet is guided to reach all addressed nodes efficiently.
Summary
The Breadth-First Search algorithm is a staple in computer science for graph traversal. By utilizing a Queue, it ensures we explore nodes in the order of their distance, making it the go-to choice for finding the shortest path in an unweighted graph. It is efficient with a complexity of O(V + E) and avoids infinite loops by marking visited nodes.
People are also reading:
