Welcome to our session on Graph Algorithms Implementation. A large proportion of real-world problems, from social networking to routing applications, can be represented by graphs. Understanding and implementing graph algorithms is thus a key skill to have in your programming toolkit. In this lesson, we introduce and explore one of the most fundamental graph traversal algorithms — the Breadth-First Search (BFS).

A graph consists of nodes connected by edges. An adjacency list is a way of representing a graph as a collection of lists. In an adjacency list, each vertex u in the graph has a list that contains all of the vertices v that are adjacent to u. Here's a breakdown of how it works:

• Vertices: Each vertex in the graph has a corresponding list.
• Edges: If there is an edge between vertices u and v, then vertex v will appear in the list for vertex u, and vice versa for an undirected graph.

For example:

Plain text
Copy to clipboard
10 -> {1, 2}
21 -> {0}
32 -> {0, 3}
43 -> {2}

corresponds to this graph:

Plain text
Copy to clipboard
1   0
2  / \ 
3 1   2 - 3

The Graph class we will use is:

C++
Copy to clipboard
1#include <set>
2#include <map>
3
4class Graph {
5public:
6    Graph() {}
7
8    void addEdge(int u, int v) {
9        adjList[u].insert(v);
10        adjList[v].insert(u); // Assuming an undirected graph
11    }
12
13    const std::map<int, std::set<int>>& getAdjList() const {
14        return adjList;
15    }
16private:
17    std::map<int, std::set<int>> adjList;
18};

You can represent the adjacency list using a std::map<int, std::set<int>> for better efficiency with lookups and insertions. Here, the keys of the map represent vertices, and the values (which are set<int>) represent the set of adjacent vertices.

Let's take a sneak peek at the BFS algorithm. Given a graph and a starting vertex, BFS systematically explores the edges of the graph, visiting all neighbors of a vertex before moving on to the next level. It does this by managing a queue of vertices yet to be explored and consistently visiting all vertices adjacent to the current one before moving on.

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle. It means that the first element added to the queue will be the first one to be removed.

For this graph:

Plain text
Copy to clipboard
1       0
2      / \
3     1   2
4    / \   \
5   3   4   5

Running BFS starting at node 0 will visit: 0 -> 1 -> 2 -> 3 -> 4 -> 5

The algorithm for BFS is:

1. Initialization:

   • Start with an initial node (start).
   • Mark start as visited.
   • Initialize a queue with start

2. Traversal:

   • While the queue is not empty:
     • Dequeue the front node from the queue.
     • Add all its unvisited neighbors to the queue.
     • Mark each of these neighbors as visited to avoid processing them again.
     • Add the dequeued node to the result list.

3. Completion:

   • The algorithm completes when the queue is empty, meaning all nodes that can be reached from the starting node have been visited in level-order fashion.

Here's the implementation of this BFS algorithm:

C++
Copy to clipboard
1#include <queue>
2#include <iostream>
3
4std::vector<int> bfs(const Graph& graph, int start) {
5
6    std::set<int> visited;
7    std::queue<int> queue;
8    std::vector<int> result;
9    
10    queue.push(start);
11
12    while (!queue.empty()) {
13        int node = queue.front();
14        queue.pop();
15
16        if (visited.find(node) == visited.end()) {
17            visited.insert(node);
18            result.push_back(node);
19            for (int neighbor : graph.getAdjList().at(node)) {
20                if (visited.find(neighbor) == visited.end()) {
21                    queue.push(neighbor);
22                }
23            }
24        }
25    }
26
27    return result;
28}
29
30int main() {
31    Graph graph;
32    graph.addEdge(0, 1);
33    graph.addEdge(0, 2);
34    graph.addEdge(1, 3);
35    graph.addEdge(1, 4);
36    graph.addEdge(2, 5);
37    
38    std::vector<int> traversal = bfs(graph, 0);
39    for (int node : traversal) {
40        std::cout << node << " "; // Output: 0 1 2 3 4 5
41    }
42    return 0;
43}

As we delve into this session, we will understand the mechanics behind BFS. Our study will include the concepts of traversal, the queue data structure's usefulness in BFS, and how to handle discovery and the processing of nodes while ensuring all operations are handled efficiently using C++ data structures like std::queue and std::set. Equipped with these fundamentals, we'll practice on a variety of problems calling for BFS to perform node-level searches or find connected components in a graph. Let's dive in and uncover the power of graph algorithms!