Unit 5: Graph Algorithms

Learning Objectives

• Implement the Bellman-Ford algorithm for shortest paths
• Master Union-Find data structure with path compression
• Apply Kruskal's algorithm for minimum spanning trees
• Understand graph algorithm optimizations and applications
• Analyze time and space complexity of graph algorithms

1. Bellman-Ford Algorithm

The Bellman-Ford algorithm finds shortest paths from a source vertex to all other vertices in a weighted graph, even with negative edge weights.

Bellman-Ford Implementation

#include 
#include 
#include 

struct Edge {
    int from, to, weight;
    
    Edge(int f, int t, int w) : from(f), to(t), weight(w) {}
};

class BellmanFord {
private:
    int vertices;
    std::vector edges;
    
public:
    BellmanFord(int v) : vertices(v) {}
    
    void addEdge(int from, int to, int weight) {
        edges.emplace_back(from, to, weight);
    }
    
    std::vector shortestPath(int source) {
        std::vector distance(vertices, INT_MAX);
        distance[source] = 0;
        
        // Relax edges V-1 times
        for (int i = 0; i < vertices - 1; i++) {
            bool updated = false;
            
            for (const Edge& edge : edges) {
                if (distance[edge.from] != INT_MAX && 
                    distance[edge.from] + edge.weight < distance[edge.to]) {
                    distance[edge.to] = distance[edge.from] + edge.weight;
                    updated = true;
                }
            }
            
            // Early termination if no updates
            if (!updated) break;
        }
        
        // Check for negative cycles
        for (const Edge& edge : edges) {
            if (distance[edge.from] != INT_MAX && 
                distance[edge.from] + edge.weight < distance[edge.to]) {
                std::cout << "Graph contains negative cycle!" << std::endl;
                return std::vector(); // Empty vector indicates negative cycle
            }
        }
        
        return distance;
    }
    
    bool hasNegativeCycle(int source) {
        std::vector distance(vertices, INT_MAX);
        distance[source] = 0;
        
        // Relax edges V-1 times
        for (int i = 0; i < vertices - 1; i++) {
            for (const Edge& edge : edges) {
                if (distance[edge.from] != INT_MAX && 
                    distance[edge.from] + edge.weight < distance[edge.to]) {
                    distance[edge.to] = distance[edge.from] + edge.weight;
                }
            }
        }
        
        // Check for negative cycles
        for (const Edge& edge : edges) {
            if (distance[edge.from] != INT_MAX && 
                distance[edge.from] + edge.weight < distance[edge.to]) {
                return true;
            }
        }
        
        return false;
    }
    
    void displayResult(const std::vector& distances, int source) {
        std::cout << "Shortest distances from vertex " << source << ":" << std::endl;
        for (int i = 0; i < vertices; i++) {
            std::cout << "Vertex " << i << ": ";
            if (distances[i] == INT_MAX) {
                std::cout << "∞" << std::endl;
            } else {
                std::cout << distances[i] << std::endl;
            }
        }
    }
};

2. Union-Find Data Structure

Union-Find (Disjoint Set Union) efficiently manages a collection of disjoint sets with union and find operations.

Union-Find Implementation

#include 
#include 

class UnionFind {
private:
    std::vector parent;
    std::vector rank;
    int components;
    
public:
    UnionFind(int n) : parent(n), rank(n, 0), components(n) {
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }
    
    // Find with path compression
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // Path compression
        }
        return parent[x];
    }
    
    // Union by rank
    bool unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        
        if (rootX == rootY) {
            return false; // Already in same set
        }
        
        // Union by rank
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        
        components--;
        return true;
    }
    
    bool connected(int x, int y) {
        return find(x) == find(y);
    }
    
    int getComponents() const {
        return components;
    }
    
    void displaySets() {
        std::cout << "Current sets:" << std::endl;
        for (int i = 0; i < parent.size(); i++) {
            std::cout << "Element " << i << " -> Root " << find(i) << std::endl;
        }
        std::cout << "Number of components: " << components << std::endl;
    }
};

3. Kruskal's Algorithm

Kruskal's algorithm finds the minimum spanning tree by sorting edges and using Union-Find to avoid cycles.

Kruskal's Implementation

#include 
#include 
#include 

struct KruskalEdge {
    int from, to, weight;
    
    KruskalEdge(int f, int t, int w) : from(f), to(t), weight(w) {}
    
    bool operator<(const KruskalEdge& other) const {
        return weight < other.weight;
    }
};

class KruskalMST {
private:
    int vertices;
    std::vector edges;
    
public:
    KruskalMST(int v) : vertices(v) {}
    
    void addEdge(int from, int to, int weight) {
        edges.emplace_back(from, to, weight);
    }
    
    std::vector findMST() {
        std::vector result;
        
        // Sort edges by weight
        std::sort(edges.begin(), edges.end());
        
        // Initialize Union-Find
        UnionFind uf(vertices);
        
        for (const KruskalEdge& edge : edges) {
            // If edge doesn't create cycle, add to MST
            if (uf.unite(edge.from, edge.to)) {
                result.push_back(edge);
                
                // Stop when we have V-1 edges
                if (result.size() == vertices - 1) {
                    break;
                }
            }
        }
        
        return result;
    }
    
    int getMSTWeight() {
        std::vector mst = findMST();
        int totalWeight = 0;
        
        for (const KruskalEdge& edge : mst) {
            totalWeight += edge.weight;
        }
        
        return totalWeight;
    }
    
    void displayMST() {
        std::vector mst = findMST();
        
        std::cout << "Minimum Spanning Tree edges:" << std::endl;
        int totalWeight = 0;
        
        for (const KruskalEdge& edge : mst) {
            std::cout << edge.from << " -- " << edge.to 
                     << " (weight: " << edge.weight << ")" << std::endl;
            totalWeight += edge.weight;
        }
        
        std::cout << "Total MST weight: " << totalWeight << std::endl;
    }
    
    // Advanced: Kruskal with custom comparator
    template
    std::vector findMSTCustom(Comparator comp) {
        std::vector result;
        std::vector sortedEdges = edges;
        
        std::sort(sortedEdges.begin(), sortedEdges.end(), comp);
        
        UnionFind uf(vertices);
        
        for (const KruskalEdge& edge : sortedEdges) {
            if (uf.unite(edge.from, edge.to)) {
                result.push_back(edge);
                if (result.size() == vertices - 1) {
                    break;
                }
            }
        }
        
        return result;
    }
};

4. Applications and Optimizations

Real-World Applications

Advanced Graph Algorithms

#include 
#include 
#include 
#include 

class AdvancedGraphAlgorithms {
public:
    // Johnson's Algorithm: All-pairs shortest paths
    static std::vector> johnsonsAlgorithm(
        const std::vector>>& graph) {
        
        int n = graph.size();
        
        // Add new vertex connected to all vertices with weight 0
        std::vector edges;
        for (int u = 0; u < n; u++) {
            edges.emplace_back(n, u, 0); // From new vertex to u
            for (const auto& [v, weight] : graph[u]) {
                edges.emplace_back(u, v, weight);
            }
        }
        
        // Run Bellman-Ford from new vertex
        BellmanFord bf(n + 1);
        for (const Edge& e : edges) {
            bf.addEdge(e.from, e.to, e.weight);
        }
        
        std::vector h = bf.shortestPath(n);
        if (h.empty()) return {}; // Negative cycle
        
        // Reweight edges
        std::vector>> reweighted(n);
        for (int u = 0; u < n; u++) {
            for (const auto& [v, weight] : graph[u]) {
                int newWeight = weight + h[u] - h[v];
                reweighted[u].emplace_back(v, newWeight);
            }
        }
        
        // Run Dijkstra from each vertex
        std::vector> distances(n, std::vector(n, INT_MAX));
        
        for (int source = 0; source < n; source++) {
            distances[source] = dijkstra(reweighted, source);
            
            // Restore original weights
            for (int target = 0; target < n; target++) {
                if (distances[source][target] != INT_MAX) {
                    distances[source][target] += h[target] - h[source];
                }
            }
        }
        
        return distances;
    }
    
private:
    static std::vector dijkstra(
        const std::vector>>& graph, int source) {
        
        int n = graph.size();
        std::vector dist(n, INT_MAX);
        std::priority_queue, 
                          std::vector>, 
                          std::greater<>> pq;
        
        dist[source] = 0;
        pq.emplace(0, source);
        
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            
            if (d > dist[u]) continue;
            
            for (const auto& [v, weight] : graph[u]) {
                if (dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    pq.emplace(dist[v], v);
                }
            }
        }
        
        return dist;
    }
    
public:
    // Borůvka's Algorithm: Alternative MST algorithm
    static std::vector boruvkaMST(
        const std::vector& edges, int vertices) {
        
        std::vector result;
        UnionFind uf(vertices);
        
        while (uf.getComponents() > 1) {
            std::vector cheapest(vertices, -1);
            
            // Find cheapest edge for each component
            for (int i = 0; i < edges.size(); i++) {
                int rootU = uf.find(edges[i].from);
                int rootV = uf.find(edges[i].to);
                
                if (rootU != rootV) {
                    if (cheapest[rootU] == -1 || 
                        edges[i].weight < edges[cheapest[rootU]].weight) {
                        cheapest[rootU] = i;
                    }
                    
                    if (cheapest[rootV] == -1 || 
                        edges[i].weight < edges[cheapest[rootV]].weight) {
                        cheapest[rootV] = i;
                    }
                }
            }
            
            // Add cheapest edges to MST
            for (int i = 0; i < vertices; i++) {
                if (cheapest[i] != -1) {
                    const KruskalEdge& edge = edges[cheapest[i]];
                    if (uf.unite(edge.from, edge.to)) {
                        result.push_back(edge);
                    }
                }
            }
        }
        
        return result;
    }
};

5. Performance Analysis

6. Complete Example Program

#include 

int main() {
    std::cout << "=== Unit 5: Graph Algorithms Demo ===" << std::endl;
    
    // Bellman-Ford Demo
    std::cout << "\n--- Bellman-Ford Algorithm ---" << std::endl;
    BellmanFord graph(5);
    
    // Add edges (from, to, weight)
    graph.addEdge(0, 1, -1);
    graph.addEdge(0, 2, 4);
    graph.addEdge(1, 2, 3);
    graph.addEdge(1, 3, 2);
    graph.addEdge(1, 4, 2);
    graph.addEdge(3, 2, 5);
    graph.addEdge(3, 1, 1);
    graph.addEdge(4, 3, -3);
    
    std::vector distances = graph.shortestPath(0);
    if (!distances.empty()) {
        graph.displayResult(distances, 0);
    }
    
    // Union-Find Demo
    std::cout << "\n--- Union-Find Demo ---" << std::endl;
    UnionFind uf(8);
    
    std::cout << "Initial components: " << uf.getComponents() << std::endl;
    
    uf.unite(0, 1);
    uf.unite(2, 3);
    uf.unite(4, 5);
    uf.unite(1, 3);
    
    std::cout << "After unions: " << uf.getComponents() << " components" << std::endl;
    std::cout << "Are 0 and 3 connected? " << (uf.connected(0, 3) ? "Yes" : "No") << std::endl;
    std::cout << "Are 4 and 6 connected? " << (uf.connected(4, 6) ? "Yes" : "No") << std::endl;
    
    // Kruskal's MST Demo
    std::cout << "\n--- Kruskal's MST Demo ---" << std::endl;
    KruskalMST mst(6);
    
    mst.addEdge(0, 1, 4);
    mst.addEdge(0, 2, 4);
    mst.addEdge(1, 2, 2);
    mst.addEdge(1, 0, 4);
    mst.addEdge(2, 0, 4);
    mst.addEdge(2, 1, 2);
    mst.addEdge(2, 3, 3);
    mst.addEdge(2, 5, 2);
    mst.addEdge(2, 4, 4);
    mst.addEdge(3, 2, 3);
    mst.addEdge(3, 4, 3);
    mst.addEdge(4, 2, 4);
    mst.addEdge(4, 3, 3);
    mst.addEdge(5, 2, 2);
    mst.addEdge(5, 4, 3);
    
    mst.displayMST();
    
    return 0;
}