← BACK TO SIMULATOR

Graph Algorithms - C++ Core

Complexity: O(V + E)
1. Graph Representation (Adjacency List)

We use an unordered_map to store nodes and their neighbors with edge weights.

#include <iostream>
#include <unordered_map>
#include <list>

using namespace std;

class Graph {
    // adjacency list: map<node, list<pair<neighbor, weight>>>
    unordered_map<string, list<pair<string, int>>> adj;

public:
    void addEdge(string u, string v, int weight, bool directed = false) {
        adj[u].push_back({v, weight});
        if (!directed) {
            adj[v].push_back({u, weight});
        }
    }
};
Complexity: O(V + E)
2. Breadth-First Search (BFS)

BFS uses a Queue to explore neighbors level by level. Ideal for unweighted shortest paths.

#include <queue>
#include <set>

void bfs(string startNode) {
    queue<string> q;
    set<string> visited;

    q.push(startNode);
    visited.insert(startNode);

    while (!q.empty()) {
        string curr = q.front();
        q.pop();
        cout << curr << " "; 

        for (auto neighbor : adj[curr]) {
            if (visited.find(neighbor.first) == visited.end()) {
                visited.insert(neighbor.first);
                q.push(neighbor.first);
            }
        }
    }
}
Complexity: O(E log V)
3. Dijkstra's Algorithm

Finding the shortest path in a weighted graph using a Priority Queue.

#include <map>

void dijkstra(string start) {
    map<string, int> dist;
    for(auto const& [node, neighbors] : adj) dist[node] = 1e9; 
    dist[start] = 0;

    set<pair<int, string>> pq;
    pq.insert({0, start});

    while(!pq.empty()){
        auto top = *(pq.begin());
        string curr = top.second;
        int d = top.first;
        pq.erase(pq.begin());

        for(auto neighbor : adj[curr]){
            if(d + neighbor.second < dist[neighbor.first]){
                pq.erase({dist[neighbor.first], neighbor.first});
                dist[neighbor.first] = d + neighbor.second;
                pq.insert({dist[neighbor.first], neighbor.first});
            }
        }
    }
}
Complexity: O(V + E)
4. Depth-First Search (DFS)

DFS explores as far as possible along each branch before backtracking. It uses Recursion (which internally uses a Stack).

#include <set>

// Helper function for recursion
void dfsHelper(string node, set<string>& visited) {
    // Mark the current node as visited
    visited.insert(node);
    cout << node << " ";

    // Recur for all the neighbors
    for (auto neighbor : adj[node]) {
        if (visited.find(neighbor.first) == visited.end()) {
            dfsHelper(neighbor.first, visited);
        }
    }
}

void dfs(string startNode) {
    set<string> visited;
    dfsHelper(startNode, visited);
}