Graph Theory with C++

Graph theory is essential in computer science, powering applications like social networks, maps, and compilers. C++ is an excellent language for graph algorithms due to its speed and control over memory. Here's a quick guide to get started.

1. Representing Graphs

Use adjacency lists for most graph problems:

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n = 5; // number of nodes
    vector<vector<int>> adj(n);

    // add edges
    adj[0].push_back(1);
    adj[1].push_back(2);
    adj[2].push_back(3);
    adj[3].push_back(4);

    // print adjacency list
    for (int i = 0; i < n; i++) {
        cout << "Node " << i << ": ";
        for (int neighbor : adj[i])
            cout << neighbor << " ";
        cout << endl;
    }
}

2. Graph Traversal

Depth-First Search (DFS):

void dfs(int node, vector<vector<int>>& adj, vector<bool>& visited) {
    visited[node] = true;
    for (int neighbor : adj[node]) {
        if (!visited[neighbor])
            dfs(neighbor, adj, visited);
    }
}

Breadth-First Search (BFS):

#include <bits/stdc++.h>
using namespace std;

void bfs(int start, vector<vector<int>>& adj) {
    vector<bool> visited(adj.size(), false);
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int node = q.front();
        q.pop();
        for (int neighbor : adj[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

3. Practice Algorithms

• Dijkstra’s algorithm (shortest paths)
• Union-Find (for disjoint sets)
• Topological sort (DAGs)
• Floyd-Warshall (all-pairs shortest paths)