Krushkal's vs Prim's vs Dijkstra Algorithm - Cheatsheet | Last Minute Notes

Spanning Tree

A spanning tree of a graph is a subgraph that includes all the vertices of the original graph, while ensuring it remains acyclic (contains no cycles) and connected (every pair of vertices is connected by exactly one simple path).

Mininum Spanning Tree(MST) - A minimum spanning tree (MST) of a weighted, connected graph is a spanning tree that has the smallest possible sum of edge weights among all possible spanning trees of that graph

Kruskal's Algorithm

Kruskal's algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a graph.

Working Steps:

→ Sort all edges in the graph by their weight.
→ Initialize the MST as an empty set.
→ Iterate through the sorted edges and for each edge:
 → Check if adding the edge to the MST will form a cycle using a union-find data structure.
 → Add the edge to the MST if it does not form a cycle.
→ Repeat until the MST contains $V-1$ edges, where $V$ is the number of vertices.

Pseudocode in C++:

struct Edge {
    int u, v, weight;
    bool operator<(const Edge& other) const {
        return weight < other.weight;
    }
};

int find(int parent[], int vertex) {
    if (parent[vertex] != vertex)
        parent[vertex] = find(parent, parent[vertex]);
    return parent[vertex];
}

void unionSets(int parent[], int rank[], int u, int v) {
    int rootU = find(parent, u);
    int rootV = find(parent, v);
    if (rootU != rootV) {
        if (rank[rootU] > rank[rootV])
            parent[rootV] = rootU;
        else if (rank[rootU] < rank[rootV])
            parent[rootU] = rootV;
        else {
            parent[rootV] = rootU;
            rank[rootU]++;
        }
    }
}

vector<Edge> kruskal(vector<Edge>& edges, int V) {
    sort(edges.begin(), edges.end());
    vector<Edge> MST;
    int parent[V];
    int rank[V] = {0};

    for (int i = 0; i < V; ++i)
        parent[i] = i;

    for (Edge& edge : edges) {
        if (find(parent, edge.u) != find(parent, edge.v)) {
            MST.push_back(edge);
            unionSets(parent, rank, edge.u, edge.v);
        }
    }
    return MST;
}
            

Time Complexity: $O(E \log E + E \log V)$
 → Sorting edges takes $O(E \log E)$
 → Union-find operations take $O(E \log V)$
Space Complexity: $O(E + V)$
 → Storing edges and the union-find data structure.

Use Cases:

→ Network Design: Creating efficient and cost-effective network topologies.
→ Approximation Algorithms: Providing a basis for approximation in problems like the Traveling Salesman Problem.
→ Cluster Analysis: Connecting data points with the minimum total distance in clustering algorithms.

Advantages:

→ Simplicity: Easy to understand and implement.
→ Efficiency: Works well with sparse graphs.
→ Optimal: Guarantees the minimum spanning tree.

Disadvantages:

→ Sorting Overhead: Sorting edges can be computationally expensive for dense graphs.
→ Not Suitable for Dense Graphs: Better algorithms exist for very dense graphs, such as Prim's algorithm.

Prim's Algorithm

Prim's algorithm is a greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, weighted graph.

Working Steps:

→ Choose an arbitrary starting vertex.
→ Grow the MST by iteratively adding the smallest weight edge that connects a vertex in the MST to a vertex outside the MST.
→ Repeat until all vertices are included in the MST.

Pseudocode in C++:

vector<int> prim(vector<vector<pair<int, int>>>& graph, int V) {
    vector<int> parent(V, -1);
    vector<int> key(V, INT_MAX);
    vector<bool> inMST(V, false);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    pq.push(make_pair(0, 0)); // Start from vertex 0 with key 0
    key[0] = 0;

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        inMST[u] = true;

        for (auto& neighbor : graph[u]) {
            int v = neighbor.first;
            int weight = neighbor.second;

            if (!inMST[v] && weight < key[v]) {
                parent[v] = u;
                key[v] = weight;
                pq.push(make_pair(key[v], v));
            }
        }
    }

    return parent;
}
        

Time Complexity: $O(E \log V)$
 → Priority queue operations dominate the complexity.

Space Complexity: $O(V + E)$
 → Storing the graph, priority queue, and MST data structures.

Use Cases:

→ Network Design: Creating efficient network topologies.
→ Clustering: Partitioning data points into cohesive groups.
→ Routing Algorithms: Finding the shortest path tree in broadcasting.

Advantages:

→ Efficiency: Works well with dense graphs.
→ Optimality: Guarantees the minimum spanning tree.
→ Flexibility: Can handle graphs with varying edge weights.

Disadvantages:

→ Initialization: Requires an initial vertex selection.
→ Complexity: Priority queue operations can be expensive in certain cases.

Dijkstra's Algorithm

Dijkstra's algorithm is a greedy algorithm used to find the shortest path from a source vertex to all other vertices in a weighted graph.

Working Steps:

→ Initialize distances from the source vertex to all other vertices as infinite and the distance to itself as 0.
→ Use a priority queue to always select the vertex with the smallest distance.
→ Relax edges: Update the distance to neighboring vertices if a shorter path is found through the current vertex.
→ Repeat until all vertices are processed.

Pseudocode in C++:

vector<int> dijkstra(vector<vector<pair<int, int>>>& graph, int src) {
    int V = graph.size();
    vector<int> dist(V, INT_MAX);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;

    dist[src] = 0;
    pq.push(make_pair(0, src));

    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();

        for (auto& neighbor : graph[u]) {
            int v = neighbor.first;
            int weight = neighbor.second;

            if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
                pq.push(make_pair(dist[v], v));
            }
        }
    }

    return dist;
}
        

Time Complexity: $O((V + E) \log V)$
 → Priority queue operations dominate the complexity.

Space Complexity: $O(V + E)$
 → Storing the graph, priority queue, and distances.

Use Cases:

→ Routing Protocols: Finding the shortest path in computer networks.
→ GPS Navigation: Calculating the shortest route between locations.
→ Resource Allocation: Optimizing resource utilization in distributed systems.

Advantages:

→ Efficiency: Finds shortest paths from a single source vertex.
→ Optimality: Produces correct results for graphs with non-negative weights.
→ Applicability: Widely used in real-world applications.

Disadvantages:

→ Non-negative Weights: Cannot handle negative edge weights without modification.
→ Complexity: May be inefficient for very dense graphs or large networks.