Krushkal's.cpp

#include <iostream>
#include <vector>

using namespace std;

// Structure to store an edge
struct Edge {
    int src;
    int dest;
    int weight;
};

// Manually sort edges using Bubble Sort
void bubbleSort(vector<Edge> &edges) {
    int n = edges.size();
    for (int i = 0; i < n - 1; i++) {
        for (int j = 0; j < n - i - 1; j++) {
            if (edges[j].weight > edges[j + 1].weight) {
                // Swap edges[j] and edges[j+1]
                Edge temp = edges[j];
                edges[j] = edges[j + 1];
                edges[j + 1] = temp;
            }
        }
    }
}

//we iterate through all edges and apply the find-union algorithm
// Function to find the parent of a node
int findParent(int parent[], int node) {
    while (parent[node] != node)
        node = parent[node];
    return node;
}

// Function to perform union of two sets
void unionSets(int parent[], int u, int v) {
    int parentU = findParent(parent, u);
    int parentV = findParent(parent, v);
    parent[parentU] = parentV;
}

// Kruskal's algorithm using manual sorting
void kruskal(int V, vector<Edge> &edges) {
    bubbleSort(edges); // Step 1: Manually sort the edges

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

    vector<Edge> mst;

    for (int i = 0; i < edges.size(); i++) {
        int u = edges[i].src;
        int v = edges[i].dest;

        int parentU = findParent(parent, u);
        int parentV = findParent(parent, v);

        if (parentU != parentV) {
            mst.push_back(edges[i]);
            unionSets(parent, u, v);
        }
    }

    // Output the MST
    cout << "Edges in the Minimum Spanning Tree:\n";
    for (int i = 0; i < mst.size(); i++) {
        cout << mst[i].src << " - " << mst[i].dest << " : " << mst[i].weight << endl;
    }
}
void addEdges(vector<vector<int>> &arr)
{
    int connection, edges;
    int weight = 0;
    int Size = arr.size();
    for (int i = 0; i < Size; i++)
    {
        cout << "Enter no of edges connected to " << i << " :";
        cin >> edges;
        for (size_t j = 0; j < edges; j++)
        {
            cout << "Enter Edge: ";
            cin >> connection;
            cout<<"Enter Edge weight: ";
            cin>> weight;
            arr[i][connection] = weight;
        }
    }
}
void createEdgeArray(vector<vector<int>> &arr,vector<Edge>&edges){
    int size = arr.size();
    int weight = 0;
    for (int i = 0; i < size; i++)
    {
        for (size_t j = 0; j < size; j++)
        {
            weight = arr[i][j];
            if (arr[i][j] != 0)
            {
                Edge edge;
                edge.src = i;
                edge.dest = j;
                edge.weight = weight;
                edges.push_back(edge);
            }
            
        }
    }
}
int main() {
    int V;
    cout << "Enter number of Vertices: ";
    cin >> V;
    // Initialize 2d-matrix vector of vectors with 0
    vector<vector<int>> arr(V, vector<int>(V, 0));
    vector<Edge> edges;
    addEdges(arr);
    createEdgeArray(arr,edges);
    
    for (int i = 0; i < V; i++)
    {
        Edge edge = edges[i];
        cout<<"{"<< edge.src<<", "<<edge.dest<<", "<<edge.weight<<"}"<<endl;
    }
    
    kruskal(V, edges);

    return 0;
}