Graph Algorithms Implementation Using C++

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:

0 -> {1, 2}
1 -> {0}
2 -> {0, 3}
3 -> {2}

corresponds to this graph:

   0
  / \ 
 1   2 - 3

The Graph class we will use is:

#include <set>
#include <map>

class Graph {
public:
    Graph() {}

    void addEdge(int u, int v) {
        adjList[u].insert(v);
        adjList[v].insert(u); // Assuming an undirected graph
    }

    const std::map<int, std::set<int>>& getAdjList() const {
        return adjList;
    }
private:
    std::map<int, std::set<int>> adjList;
};

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:

       0
      / \
     1   2
    / \   \
   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:

#include <queue>
#include <iostream>

std::vector<int> bfs(const Graph& graph, int start) {

    std::set<int> visited;
    std::queue<int> queue;
    std::vector<int> result;
    
    queue.push(start);

    while (!queue.empty()) {
        int node = queue.front();
        queue.pop();

        if (visited.find(node) == visited.end()) {
            visited.insert(node);
            result.push_back(node);
            for (int neighbor : graph.getAdjList().at(node)) {
                if (visited.find(neighbor) == visited.end()) {
                    queue.push(neighbor);
                }
            }
        }
    }

    return result;
}

int main() {
    Graph graph;
    graph.addEdge(0, 1);
    graph.addEdge(0, 2);
    graph.addEdge(1, 3);
    graph.addEdge(1, 4);
    graph.addEdge(2, 5);
    
    std::vector<int> traversal = bfs(graph, 0);
    for (int node : traversal) {
        std::cout << node << " "; // Output: 0 1 2 3 4 5
    }
    return 0;
}