C++ Implementations of Core Algorithms: DP, Graph, Sort

Posted on Nov 24, 2025 in Computers

Essential Algorithms Implemented in C++

Longest Common Subsequence (LCS)

The Longest Common Subsequence (LCS) problem is solved here using Dynamic Programming. It calculates the length and reconstructs the actual subsequence of two input strings.

#include <iostream>
#include <string>
#include <vector>
#include <algorithm> // For max function

using namespace std;

int main() {
    string X, Y;
    cout << "Enter first string: ";
    cin >> X;
    cout << "Enter second string: ";
    cin >> Y;

    int m = X.size(), n = Y.size();
    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (X[i - 1] == Y[j - 1])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
    }

    int len = dp[m][n];
    string lcs = "";
    int i = m, j = n;
    while (i > 0 && j > 0) {
        if (X[i - 1] == Y[j - 1]) {
            lcs = X[i - 1] + lcs;
            i--; j--;
        } else if (dp[i - 1][j] > dp[i][j - 1])
            i--;
        else
            j--;
    }

    cout << "\nLongest Common Subsequence: " << lcs;
    cout << "\nLength of LCS: " << len << endl;

    return 0;
}

Dijkstra’s Shortest Path Algorithm

This implementation finds the shortest path from a source vertex to all other vertices in a weighted graph using a priority queue.

#include <iostream>
#include <vector>
#include <queue>
#include <limits>

using namespace std;

int main(){
    int n, m;
    cout << "Enter vertices and edges: ";
    cin >> n >> m;

    vector<vector<pair<int, int>>> g(n);
    cout << "Enter edges (u v w):\n";
    for(int i = 0; i < m; i++){
        int u, v, w;
        cin >> u >> v >> w;
        g[u - 1].push_back({v - 1, w});
    }

    int s;
    cout << "Enter source vertex: ";
    cin >> s;
    s--;

    const int INF = 1e9;
    vector<int> d(n, INF), par(n, -1);
    d[s] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    pq.push({0, s});

    while(!pq.empty()){
        auto [du, u] = pq.top();
        pq.pop();
        if(du != d[u]) continue;

        for(auto [v, w] : g[u])
            if(d[v] > du + w){
                d[v] = du + w;
                par[v] = u;
                pq.push({d[v], v});
            }
    }

    for(int i = 0; i < n; i++){
        cout << "Vertex " << i + 1 << ": ";
        if(d[i] == INF){ 
            cout << "No path\n";
            continue;
        }
        cout << "Dist=" << d[i] << " Path: ";
        vector<int> p;
        for(int v = i; v != -1; v = par[v]) p.push_back(v);
        for(int j = p.size() - 1; j >= 0; j--)
            cout << p[j] + 1 << (j ? "->" : "");
        cout << "\n";
    }
}

Fractional Knapsack Problem (Greedy Approach)

This solution uses a Greedy approach, sorting items based on their profit-to-weight ratio using Heap Sort to maximize the total profit within the knapsack capacity.

#include <iostream>
#include <algorithm> // For swap

using namespace std;

struct ITEM {
    int id;
    float profit, weight, ratio;
};

void heapify(ITEM a[], int n, int i) {
    int largest = i, l = 2 * i + 1, r = 2 * i + 2;
    if (l < n && a[l].ratio > a[largest].ratio)
        largest = l;
    if (r < n && a[r].ratio > a[largest].ratio)
        largest = r;
    if (largest != i) {
        swap(a[i], a[largest]);
        heapify(a, n, largest);
    }
}

void heapSort(ITEM a[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(a, n, i);
    for (int i = n - 1; i > 0; i--) {
        swap(a[0], a[i]);
        heapify(a, i, 0);
    }
}

int main() {
    int n;
    cout << "Enter number of items: ";
    cin >> n;
    ITEM *a = new ITEM[n];
    
    for (int i = 0; i < n; i++) {
        cout << "Enter profit and weight of item " << i + 1 << ": ";
        cin >> a[i].profit >> a[i].weight;
        a[i].id = i + 1;
        a[i].ratio = a[i].profit / a[i].weight;
    }
    
    float capacity;
    cout << "Enter capacity of knapsack: ";
    cin >> capacity;

    heapSort(a, n); // Sort by ratio ascending
    
    float totalProfit = 0, cap = capacity;
    cout << "\nItems taken:\n";
    
    // Iterate from highest ratio (end of ascending sorted array)
    for (int i = n - 1; i >= 0 && cap > 0; i--) {
        if (a[i].weight <= cap) {
            cap -= a[i].weight;
            totalProfit += a[i].profit;
            cout << "Item " << a[i].id << " fully taken.\n";
        } else {
            totalProfit += a[i].profit * (cap / a[i].weight);
            cout << "Item " << a[i].id << " partially taken.\n";
            cap = 0;
        }
    }
    
    cout << "\nMaximum Profit: " << totalProfit << endl;
    delete[] a;
    return 0;
}

Matrix Chain Multiplication (Dynamic Programming)

This algorithm determines the optimal parenthesization of a sequence of matrices to minimize the total number of scalar multiplications required.

#include <iostream>
#include <climits> // For INT_MAX

using namespace std;

int main() {
    int n;
    cout << "Enter number of matrices: ";
    cin >> n;
    
    int p[n + 1];
    cout << "Enter dimensions (n+1 numbers): ";
    for (int i = 0; i <= n; i++) cin >> p[i];

    int m[n + 1][n + 1];
    for (int i = 1; i <= n; i++) m[i][i] = 0;

    for (int L = 2; L <= n; L++) {
        for (int i = 1; i <= n - L + 1; i++) {
            int j = i + L - 1;
            m[i][j] = INT_MAX;
            for (int k = i; k < j; k++) {
                int cost = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j];
                if (cost < m[i][j]) m[i][j] = cost;
            }
        }
    }

    cout << "Minimum number of multiplications: " << m[1][n] << endl;
    return 0;
}

Prim’s Algorithm for Minimum Spanning Tree (MST)

Prim’s algorithm is a Greedy algorithm used to find a Minimum Spanning Tree for a weighted undirected graph.

#include <iostream>
#include <climits>
using namespace std;

int main() {
    int n;
    cout << "Enter number of vertices: ";
    cin >> n;

    int graph[20][20];
    cout << "Enter adjacency matrix (use 0 for no edge):\n";
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> graph[i][j];

    int cost = 0, selected[20] = {0};
    selected[0] = 1;
    cout << "\nEdges in MST:\n";

    for (int edges = 0; edges < n - 1; edges++) {
        int min = INT_MAX, u = -1, v = -1;
        for (int i = 0; i < n; i++) {
            if (selected[i]) {
                for (int j = 0; j < n; j++) {
                    if (!selected[j] && graph[i][j] && graph[i][j] < min) {
                        min = graph[i][j];
                        u = i;
                        v = j;
                    }
                }
            }
        }
        selected[v] = 1;
        cost += min;
        cout << u + 1 << " - " << v + 1 << " : " << min << endl;
    }

    cout << "Total cost of MST: " << cost << endl;
    return 0;
}

Quicksort Implementation

Quicksort is an efficient, comparison-based sorting algorithm that uses a Divide and Conquer strategy.

#include <iostream>
#include <algorithm> // For swap

using namespace std;

int partition(int a[], int low, int high) {
    int pivot = a[high];
    int i = low - 1;

    for (int j = low; j < high; j++) {
        if (a[j] < pivot) {
            i++;
            swap(a[i], a[j]);
        }
    }
    swap(a[i + 1], a[high]);
    return i + 1;
}

void quickSort(int a[], int low, int high) {
    if (low < high) {
        int pi = partition(a, low, high);
        quickSort(a, low, pi - 1);
        quickSort(a, pi + 1, high);
    }
}

int main() {
    int n;
    cout << "Enter number of elements: ";
    cin >> n;
    int a[n];

    cout << "Enter elements: ";
    for (int i = 0; i < n; i++) cin >> a[i];

    quickSort(a, 0, n - 1);

    cout << "Sorted array: ";
    for (int i = 0; i < n; i++) cout << a[i] << " ";
    cout << endl;
    return 0;
}

Kruskal’s Algorithm for Minimum Spanning Tree (MST)

Kruskal’s algorithm uses a Greedy approach combined with a Disjoint Set Union (DSU) structure to find the MST by iteratively adding the cheapest safe edge.

#include <iostream>
#include <algorithm>
using namespace std;

struct Edge {
    int u, v, w;
};

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

void unite(int parent[], int rank[], int x, int y) {
    x = find(parent, x);
    y = find(parent, y);
    if (x != y) {
        if (rank[x] < rank[y]) parent[x] = y;
        else if (rank[x] > rank[y]) parent[y] = x;
        else { parent[y] = x; rank[x]++; }
    }
}

int main() {
    int n, e;
    cout << "Enter number of vertices: ";
    cin >> n;
    cout << "Enter number of edges: ";
    cin >> e;

    Edge edges[e];
    cout << "Enter edges (u v weight):\n";
    for (int i = 0; i < e; i++)
        cin >> edges[i].u >> edges[i].v >> edges[i].w;

    sort(edges, edges + e, [](Edge a, Edge b) { return a.w < b.w; });

    int parent[n + 1], rank[n + 1];
    for (int i = 1; i <= n; i++) {
        parent[i] = i;
        rank[i] = 0;
    }

    int cost = 0;
    cout << "\nEdges in MST:\n";
    for (int i = 0; i < e; i++) {
        int x = find(parent, edges[i].u);
        int y = find(parent, edges[i].v);
        if (x != y) {
            cout << edges[i].u << " - " << edges[i].v << " : " << edges[i].w << endl;
            cost += edges[i].w;
            unite(parent, rank, x, y);
        }
    }

    cout << "Total cost of MST: " << cost << endl;
    return 0;
}

Floyd-Warshall All-Pairs Shortest Path

The Floyd-Warshall algorithm uses Dynamic Programming to find the shortest paths between all pairs of vertices in a weighted graph.

#include <iostream>
#include <climits> // For INT_MAX

using namespace std;

int main() {
    int n;
    cout << "Enter number of vertices: ";
    cin >> n;

    int dist[20][20];
    cout << "Enter adjacency matrix (use " << INT_MAX << " for no edge):\n";
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            cin >> dist[i][j];

    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX &&
                    dist[i][k] + dist[k][j] < dist[i][j])
                    dist[i][j] = dist[i][k] + dist[k][j];

    cout << "\nShortest distance matrix:\n";
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++)
            if (dist[i][j] == INT_MAX) cout << "INF ";
            else cout << dist[i][j] << " ";
        cout << endl;
    }
    return 0;
}