Graph Breadth-First Search
Overview
We already know a lot about graphs. At first they seem intimidating but they are actually a lot of fun! And now it's time to have even more fun by learning to traverse/search them.
There are two main ways to traverse graphs - BFS (Breadth First Search) and DFS (Depth First Search). In this section, we are going to learn BFS.
The name 'breadth' is very descriptive - it literally means from side to side.
At first glance in the animation, I think it's very clear that the traversal is from side to side and when one side is fully visited, we move one level down and traverse again from side to side. So when you hear 'BFS' / 'Breadth First Search', immediately think of side to side traversal.
The worst time and space complexities are as follows:
Worst-case time complexity: O(V + E)
Worst-case space complexity: O(V)
Now let's get into the main steps of BFS.
First we need to initialize it with a source vertex.
It's the point from which the traversal should start so we have to directly mark it as visited and (important!) enqueue it to a new empty queue (if in doubt about queue, go back to the Queue section in Linear Data Structures).
Then we dequeue it from the queue and start 'exploring' it (exploring means finding its neighboring vertices). Then we visit those neighboring and enqueue them. Then we repeat - dequeue the first item in the queue, explore its neighbors and visit them.
If you take a few looks at the animation (and pausing and rewinding it), I'm confident that you will see the pattern. In short, it's - visit, enqueue, dequeue, find neighbors, repeat.
Okay, now we know what BFS is and how it works. But why do we need it?
The answer is - for everything!
We already know some places where graphs are used - social networks, maps, any types of networks, web crawling, games and what not.
In all of these, we need to be able to somehow traverse these graphs and BFS is one of the main ways to do so. For example, in any types of maps/navigation, where a graph represents cities and paths that connect them - BFS can be used to find the shortest path between two cities (because it traverses level by level and won't skip a vertex on the current level).
Code
# Adjacency List (see Graph Representation section)
graph = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'E'],
'D': ['B', 'F'],
'E': ['C', 'F'],
'F': ['D', 'E']
}
# Breadth-First Search function
def BFS(graph, start_node):
queue = []
visited = set()
queue.append(start_node)
visited.add(start_node)
while queue:
current_node = queue.pop(0)
print(current_node, end=' ')
for neighbor in graph[current_node]:
if neighbor not in visited:
queue.append(neighbor)
visited.add(neighbor)
# Starting BFS from node 'A'
BFS(graph, 'A')
// Adjacency List (see Graph Representation section)
const graph = {
A: ['B', 'C'],
B: ['A', 'D'],
C: ['A', 'E'],
D: ['B', 'F'],
E: ['C', 'F'],
F: ['D', 'E'],
};
function BFS(graph, startNode) {
const queue = [];
const visited = new Set();
queue.push(startNode);
visited.add(startNode);
while (queue.length > 0) {
const currentNode = queue.shift();
for (const neighbor of graph[currentNode]) {
if (!visited.has(neighbor)) {
queue.push(neighbor);
visited.add(neighbor);
}
}
}
}
BFS(graph, 'A');
import java.util.*;
public class BreadthFirstSearch {
// Adjacency List (see Graph Representation section)
static Map<String, List<String>> graph = new HashMap<>();
static {
graph.put("A", Arrays.asList("B", "C"));
graph.put("B", Arrays.asList("A", "D"));
graph.put("C", Arrays.asList("A", "E"));
graph.put("D", Arrays.asList("B", "F"));
graph.put("E", Arrays.asList("C", "F"));
graph.put("F", Arrays.asList("D", "E"));
}
// Breadth-First Search function
public static void BFS(Map<String, List<String>> graph, String startNode) {
Queue<String> queue = new LinkedList<>();
Set<String> visited = new HashSet<>();
queue.add(startNode);
visited.add(startNode);
while (!queue.isEmpty()) {
String currentNode = queue.poll();
System.out.print(currentNode + " ");
for (String neighbor : graph.get(currentNode)) {
if (!visited.contains(neighbor)) {
queue.add(neighbor);
visited.add(neighbor);
}
}
}
}
public static void main(String[] args) {
// Starting BFS from node 'A'
BFS(graph, "A");
}
}
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// Adjacency List (see Graph Representation section)
typedef struct Node {
char data;
struct Node* next;
} Node;
typedef struct Graph {
int numVertices;
Node** adjLists;
} Graph;
Graph* createGraph(int numVertices) {
Graph* graph = (Graph*)malloc(sizeof(Graph));
graph->numVertices = numVertices;
graph->adjLists = (Node**)malloc(numVertices * sizeof(Node*));
for (int i = 0; i < numVertices; i++) {
graph->adjLists[i] = NULL;
}
return graph;
}
void addEdge(Graph* graph, char src, char dest) {
int srcIndex = src - 'A';
int destIndex = dest - 'A';
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = dest;
newNode->next = graph->adjLists[srcIndex];
graph->adjLists[srcIndex] = newNode;
newNode = (Node*)malloc(sizeof(Node));
newNode->data = src;
newNode->next = graph->adjLists[destIndex];
graph->adjLists[destIndex] = newNode;
}
void BFS(Graph* graph, char startNode) {
bool* visited = (bool*)malloc(graph->numVertices * sizeof(bool));
for (int i = 0; i < graph->numVertices; i++) {
visited[i] = false;
}
int startNodeIndex = startNode - 'A';
visited[startNodeIndex] = true;
char queue[graph->numVertices];
int front = 0, rear = 0;
queue[rear++] = startNode;
while (front != rear) {
char currentNode = queue[front++];
printf("%c ", currentNode);
int currentNodeIndex = currentNode - 'A';
Node* temp = graph->adjLists[currentNodeIndex];
while (temp != NULL) {
int adjNodeIndex = temp->data - 'A';
if (!visited[adjNodeIndex]) {
visited[adjNodeIndex] = true;
queue[rear++] = temp->data;
}
temp = temp->next;
}
}
free(visited);
}
void freeGraph(Graph* graph) {
for (int i = 0; i < graph->numVertices; i++) {
Node* current = graph->adjLists[i];
while (current != NULL) {
Node* temp = current;
current = current->next;
free(temp);
}
}
free(graph->adjLists);
free(graph);
}
int main() {
Graph* graph = createGraph(6);
addEdge(graph, 'A', 'C');
addEdge(graph, 'A', 'B');
addEdge(graph, 'B', 'D');
addEdge(graph, 'C', 'E');
addEdge(graph, 'D', 'F');
addEdge(graph, 'E', 'F');
BFS(graph, 'A');
freeGraph(graph);
return 0;
}
<?php
class Graph
{
public $numVertices;
public $adjLists;
public function __construct($numVertices)
{
$this->numVertices = $numVertices;
$this->adjLists = array_fill(0, $numVertices, array());
}
public function addEdge($src, $dest)
{
$srcIndex = ord($src) - ord('A');
$destIndex = ord($dest) - ord('A');
array_push($this->adjLists[$srcIndex], $dest);
array_push($this->adjLists[$destIndex], $src);
}
public function BFS($startNode)
{
$visited = array_fill(0, $this->numVertices, false);
$startNodeIndex = ord($startNode) - ord('A');
$visited[$startNodeIndex] = true;
$queue = array($startNode);
while (!empty($queue)) {
$currentNode = array_shift($queue);
echo $currentNode . " ";
$currentNodeIndex = ord($currentNode) - ord('A');
foreach ($this->adjLists[$currentNodeIndex] as $neighbor) {
$neighborIndex = ord($neighbor) - ord('A');
if (!$visited[$neighborIndex]) {
$visited[$neighborIndex] = true;
array_push($queue, $neighbor);
}
}
}
}
}
$graph = new Graph(6);
$graph->addEdge('A', 'B');
$graph->addEdge('A', 'C');
$graph->addEdge('B', 'D');
$graph->addEdge('C', 'E');
$graph->addEdge('D', 'F');
$graph->addEdge('E', 'F');
$graph->BFS('A');
?>