Home | Projects | Notes > Data Structures & Algorithms > Breadth-First Search (BFS)

Breadth-First Search (BFS)

Breadth-First Search (BFS)

• The BFS algorithm systematically explores a graph or tree level-by-level, ensuring that nodes at the same depth are visited before moving on to deeper levels.

• This property makes BFS particularly useful for finding the shortest path between nodes in unweighted graphs or to explore all nodes in a connected component of a graph.

Algorithm

1. Initialize a queue (FIFO) data structure to keep track of nodes to be visited. Enqueue the starting node into the queue.

2. Initialize a set or array to keep track of visited nodes to avoid revisiting them. Mark the starting node as visited.

3. While the queue is not empty:

   1. Dequeue a node from the front of the queue.

   2. Process the node (print its value, perform some operation, etc.)

   3. Enqueue all unvisited neighbors of the current node into the queue and mark them as visited.

4. Continue the process until the queue becomes empty, meaning all nodes have been visited.

Pseudo-code

xxxxxxxxxx
15
1
BFS(Graph, startNode)
2
    queue = new Queue()
3
    visited = new Set()
4
    
5
    queue.euqueue(startNode)
6
    visited.add(startNode)
7
    
8
    while queue is not empty:
9
        currentNode = queue.dequeue()
10
        process(currentNode)    // Process the node (e.g., print its value)
11
        
12
        for each neighbor in neighbors of currentNode:
13
            if neighbor is not in visited:
14
                queue.enqueue(neighbor)
15
                visited.add(neighbor)

In this algorithm,

• Graph represents the graph or data structure you're traversing

• startNode is the initial node from which you want to start the traversal

• neighbors of currentNode refers to the neighboring nodes of the current node that are connected by edges.

Code (C++)

xxxxxxxxxx
69
1
#include <iostream>
2
#include <vector>
3
#include <queue>
4
#include <unordered_set>
5

6
class Graph
7
{
8
public:
9
    Graph(int numNodes);
10
    void addEdge(int from, int to);
11
    void BFS(int startNode);
12

13
private:
14
    std::vector<std::vector<int>> adjacencyList;
15
};
16

17
Graph::Graph(int numNodes)
18
{
19
    adjacencyList.resize(numNodes);
20
}
21

22
void Graph::addEdge(int from, int to)
23
{
24
    adjacencyList[from].push_back(to);
25
}
26

27
void Graph::BFS(int startNode)
28
{
29
    std::queue<int> queue;
30
    std::unordered_set<int> visited;
31

32
    queue.push(startNode);
33
    visited.insert(startNode);
34

35
    while (!queue.empty())
36
    {
37
        int currentNode = queue.front();
38
        queue.pop();
39

40
        std::cout << currentNode << " ";    // Process the node
41

42
        for (int neighbor : adjacencyList[currentNode])
43
        {
44
            if (visited.find(neighbor) == visited.end())
45
            {
46
                queue.push(neighbor);
47
                visited.insert(neighbor);
48
            }
49
        }
50
    }
51

52
    std::cout << std::endl;
53
}
54

55
int main(int argc, char *argv[])
56
{
57
    Graph graph(6);
58

59
    graph.addEdge(0, 1);
60
    graph.addEdge(0, 2);
61
    graph.addEdge(1, 3);
62
    graph.addEdge(2, 4);
63
    graph.addEdge(3, 5);
64

65
    std::cout << "BFS traversal starting from node 0: ";
66
    graph.BFS(0);
67

68
    return 0;
69
}

xxxxxxxxxx
1
1
BFS traversal starting from node 0: 0 1 2 3 4 5 

Code (C)

xxxxxxxxxx
88
1
#include <stdio.h>
2
#include <stdlib.h>
3

4
typedef struct Node_
5
{
6
    int data;
7
    struct Node_ *next;
8
} Node;
9

10
typedef struct Graph_
11
{
12
    int numNodes;
13
    Node **adjacencyList;
14
} Graph;
15

16
Node *createNode(int data)
17
{
18
    Node *newNode = (Node *)malloc(sizeof(Node));
19
    newNode->data = data;
20
    newNode->next = NULL;
21
    return newNode;
22
}
23

24
Graph *createGraph(int numNodes)
25
{
26
    Graph *graph = (Graph *)malloc(sizeof(Graph));
27
    graph->numNodes = numNodes;
28
    graph->adjacencyList = (Node **)malloc(numNodes * sizeof(Node*));
29
    for (int i = 0; i < numNodes; ++i)
30
    {
31
        graph->adjacencyList[i] = NULL;
32
    }
33

34
    return graph;
35
}
36

37
void addEdge(Graph *graph, int from, int to)
38
{
39
    Node *newNode = createNode(to);
40
    newNode->next = graph->adjacencyList[from];
41
    graph->adjacencyList[from] = newNode;
42
}
43

44
void BFS(Graph *graph, int startNode)
45
{
46
    int *visited = (int *)calloc(graph->numNodes, sizeof(int));
47
    Node *queue[graph->numNodes];
48
    int front = 0; int rear = 0;
49

50
    queue[rear++] = createNode(startNode);
51
    visited[startNode] = 1;
52

53
    while (front < rear)
54
    {
55
        Node *currNode = queue[front++];
56
        printf("%d ", currNode->data);  // Process the node
57

58
        Node *neighbor = graph->adjacencyList[currNode->data];
59
        while (neighbor)
60
        {
61
            if (!visited[neighbor->data])
62
            {
63
                queue[rear++] = createNode(neighbor->data);
64
                visited[neighbor->data] = 1;
65
            }
66
            neighbor = neighbor->next;
67
        }
68
    }
69

70
    printf("\n");
71
    free(visited);
72
}
73

74
int main(int argc, char *argv[])
75
{
76
    Graph *graph = createGraph(6);
77

78
    addEdge(graph, 0, 1);
79
    addEdge(graph, 0, 2);
80
    addEdge(graph, 1, 3);
81
    addEdge(graph, 2, 4);
82
    addEdge(graph, 3, 5);
83

84
    printf("BFS traversal starting from 0: ");
85
    BFS(graph, 0);
86

87
    return 0;
88
}

xxxxxxxxxx
1
1
BFS traversal starting from 0: 0 2 1 4 3 5 

The order of traversal in BFS can vary depending on the order in which neighbors are added to the queue. Both orders are correct as long as they follow the BFS traversal rules.

In the output "0 2 1 4 3 5", the BFS algorithm is traversing the graph layer by layer, but the order of adding neighbors to the queue might be slightly different. For example, in this case, after visiting node 0, the algorithm enqueues nodes 1 and 2. Node 2 is dequeued before node 1, which is why you see node 2 being visited before node 1.

So, the BFS algorithm is still correctly traversing the graph, but the order of neighbors' processing might differ based on implementation details such as the queue's behavior and order of enqueuing nodes. Both "0 1 2 3 4 5" and "0 2 1 4 3 5" are valid BFS traversal orders for the given graph and its edges.