Breadth-First Search (BFS) in Graph
Welcome to our beginner's guide to Breadth-First Search (BFS) in Graph Theory! Graph theory is a fascinating branch of mathematics and computer science that deals with the study of graphs, which are mathematical structures used to model pairwise relations between objects.
What is Breadth-First Search (BFS)?
Breadth-First Search is an algorithm used to traverse or search through the nodes of a graph in a systematic manner. It starts at a specific node (often referred to as the "source" node) and explores all the neighboring nodes at the present depth level before moving on to the nodes at the next depth level.
Imagine you're exploring a maze. BFS would systematically explore all the paths starting from your current location before moving on to the paths further away.
How does BFS Work?
BFS employs a simple strategy of exploring nodes level by level. It utilizes a data structure called a queue to keep track of the nodes that need to be visited. The algorithm proceeds as follows:
- Start with the source node and enqueue it into the queue.
- Mark the source node as visited.
- While the queue is not empty:
- Dequeue a node from the front of the queue.
- Visit the dequeued node.
- Enqueue all unvisited neighboring nodes of the dequeued node.
- Mark each neighboring node as visited.
- Repeat steps 3-4 until the queue is empty.
Example of BFS with Visited Tracking
Let's explore Breadth-First Search (BFS) using a simple graph:
A
/ \
B - C
/ \ \
D - E - F
In this graph:
- A is connected to B and C.
- B is connected to A, D, and E.
- C is connected to A and F.
- D is connected to B and E.
- E is connected to B, D, and F.
- F is connected to C and E.
We will perform a BFS traversal starting from node A.
Step-by-Step Traversal:
- Begin at Node A (Source):
- Enqueue A into the queue.
- Mark A as visited.
- Queue: [A], Visited: [A]
- Visit A, enqueue its unvisited neighbors B and C.
- Dequeue A. Queue: [B, C], Visited: [A]
- Visit B, enqueue its unvisited neighbors D and E.
- Dequeue B. Queue: [C, D, E], Visited: [A, B]
- Visit C, enqueue its unvisited neighbor F.
- Dequeue C. Queue: [D, E, F], Visited: [A, B, C]
- Visit D. No new neighbors to enqueue.
- Dequeue D. Queue: [E, F], Visited: [A, B, C, D]
- Visit E. No new neighbors to enqueue.
- Dequeue E. Queue: [F], Visited: [A, B, C, D, E]
- Visit F. No new neighbors to enqueue.
- Dequeue F. Queue is now empty, indicating the end of the traversal.
A --> Level 0
/ \
B - C --> Level 1
/ \ \
D - E - F --> Level 2
A
/ \
B - C
/ \ \
D - E - F
A
/ \
B - C
/ \ \
D - E - F
A
/ \
B - C
/ \ \
D - E - F
A
/ \
B - C
/ \ \
D - E - F
A
/ \
B - C
/ \ \
D - E - F
Output Result: Nodes visited in BFS order: A, B, C, D, E, F
Time Complexity:
The time complexity of BFS is O(V + E), where V is the number of vertices and E is the number of edges in the graph.
Space Complexity:
The space complexity of BFS, in the worst-case scenario, is O(V), where V is the number of vertices.
This example clearly demonstrates the BFS algorithm's level-by-level traversal through a graph, visiting all reachable nodes systematically.
Implementing BFS Code
Now, let's take a look at how we can implement Breadth-First Search in code. We'll provide examples in several programming languages to help you get started:
package codeKatha;
import java.util.*;
public class BFS {
public void breadthFirstSearch(Graph graph, Node source) {
Queue<Node> queue = new LinkedList<>();
Set<Node> visited = new HashSet<>();
queue.add(source);
visited.add(source);
while (!queue.isEmpty()) {
Node current = queue.poll();
System.out.println(current);
for (Node neighbor : graph.getNeighbors(current)) {
if (!visited.contains(neighbor)) {
visited.add(neighbor);
queue.add(neighbor);
}
}
}
}
}
#include <iostream>
#include <queue>
#include <unordered_set>
#include "Graph.h"
void BFS(Graph& graph, Node& source) {
std::queue<Node> queue;
std::unordered_set<Node> visited;
queue.push(source);
visited.insert(source);
while (!queue.empty()) {
Node current = queue.front();
queue.pop();
std::cout << current << std::endl;
for (Node neighbor : graph.getNeighbors(current)) {
if (visited.find(neighbor) == visited.end()) {
visited.insert(neighbor);
queue.push(neighbor);
}
}
}
}
class BFS:
def breadth_first_search(self, graph, source):
queue = []
visited = set()
queue.append(source)
visited.add(source)
while queue:
current = queue.pop(0)
print(current)
for neighbor in graph.get_neighbors(current):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
class BFS {
breadthFirstSearch(graph, source) {
let queue = [];
let visited = new Set();
queue.push(source);
visited.add(source);
while (queue.length > 0) {
let current = queue.shift();
console.log(current);
for (let neighbor of graph.getNeighbors(current)) {
if (!visited.has(neighbor)) {
visited.add(neighbor);
queue.push(neighbor);
}
}
}
}
}
Graph: Concept and Important Algorithms
1. Basics of Graph Data Structure2. Breadth-First Search (BFS) in Graph
3. Depth-First Search (DFS) in Graph
4. Topological Sort in Graph
5. Union-Find Algorithm in Graph
6. Prim's Algorithm in Graph
7. Dijkstra's Algorithm in Graph
8. Kruskal's Algorithm in Graph
Congratulations! You've now learned the basics of Breadth-First Search in graph theory. Feel free to experiment with the provided code examples and explore further applications of BFS in your projects.
Comments
Post a Comment