Scribd Logo
Upload

Welcome to Scribd!

  • 2 views

    exp 5 and 17

    Uploaded by

    loginsforvarun

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd

    exp 5 and 17

    Uploaded by

    loginsforvarun
    2 views3 pages

    Copyright

    © © All Rights Reserved

    Available Formats

    PDF, TXT or read online from Scribd

    Did you find this document useful?

    Is this content inappropriate?

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    2 views3 pages

    exp 5 and 17

    Uploaded by

    loginsforvarun

    Copyright:

    © All Rights Reserved
    Download as PDF, TXT or read online from Scribd
    Download as pdf or txt
    You are on page 1of 3

    Program No: 17

    Objective: Find Minimum Cost Spanning Tree of a given connected undirected graph using
    Kruskal's algorithm. Use Union-Findalgorithms in your program.

    Algorithm:
    1. Sort edges by weight in ascending order.
    2. Initialize Union-Find data structure.
    3. Iterate through sorted edges:
    4. If endpoints are in different sets, add edge to the result.
    5. Union the sets of the endpoints.
    6. Output edges in the result as the Minimum Cost Spanning Tree.

    Program:
    #include <iostream>
    #include <vector>
    #include <algorithm>
    using namespace std;
    class UnionFind {
    private:
    vector<int> parent, rank;
    public:
    UnionFind(int n) {
    parent.resize(n);
    rank.resize(n, 0);
    for (int i = 0; i < n; ++i)
    parent[i] = i;
    }
    int find(int u) {
    if (parent[u] != u)
    parent[u] = find(parent[u]);
    return parent[u];
    }
    void unite(int u, int v) {
    int rootU = find(u);
    int rootV = find(v);

    if (rootU != rootV) {
    if (rank[rootU] < rank[rootV])
    parent[rootU] = rootV;
    else if (rank[rootU] > rank[rootV])
    parent[rootV] = rootU;
    else {
    parent[rootU] = rootV;
    rank[rootV]++;
    }
    }}
    };
    struct Edge {
    int src, dest, weight;
    };
    bool compareEdges(const Edge& a, const Edge& b) {
    return a.weight < b.weight;
    }
    class KruskalsAlgorithm {
    private:
    int vertices;
    vector<Edge> edges;
    public:
    KruskalsAlgorithm(int v) : vertices(v) {}
    void addEdge(int src, int dest, int weight) {
    edges.push_back({src, dest, weight});
    }
    void findMinimumSpanningTree() {
    sort(edges.begin(), edges.end(), compareEdges);
    UnionFind unionFind(vertices);
    cout << "Minimum Cost Spanning Tree Edges:\n";
    for (const Edge& edge : edges) {
    int rootSrc = unionFind.find(edge.src);
    int rootDest = unionFind.find(edge.dest);
    if (rootSrc != rootDest) {
    cout << edge.src << " - " << edge.dest << " (" << edge.weight << ")\n";
    unionFind.unite(rootSrc, rootDest);
    }
    }
    }
    };
    int main() {
    KruskalsAlgorithm kruskalsAlgorithm(4);
    kruskalsAlgorithm.addEdge(0, 1, 10);
    kruskalsAlgorithm.addEdge(0, 2, 6);
    kruskalsAlgorithm.addEdge(0, 3, 5);
    kruskalsAlgorithm.addEdge(1, 3, 15);
    kruskalsAlgorithm.addEdge(2, 3, 4);
    kruskalsAlgorithm.findMinimumSpanningTree();
    return 0;
    }

    Output:
    Program No: 5
    Objective Write a program to selection sort.
    :

    Algorithm
    1. Iterate through the array.
    2. Find the minimum element in the unsorted part.
    3. Swap it with the first element of the unsorted part.
    4. Move the boundary between sorted and unsorted parts.
    5. Repeat until the entire array is sorted.
    Program:
     #include <iostream>
     #include <vector>
     using namespace std;
     void selectionSort(vector<int>& arr) {
     int n = arr.size();
     for (int i = 0; i < n - 1; ++i) {
     int minIndex = i;
     for (int j = i + 1; j < n; ++j) {
     if (arr[j] < arr[minIndex])
     minIndex = j;
     }
     swap(arr[i], arr[minIndex]);
     }
     }
     void printArray(const vector<int>& arr) {
     for (int num : arr) {
     cout << num << " ";
     }
     cout << endl;
     }
     int main() {
     vector<int> arr = {64, 25, 12, 22, 11};
     cout << "Original Array: ";
     printArray(arr);
     selectionSort(arr);
     cout << "Sorted Array: ";
     printArray(arr);
     return 0;
     }
    Output:

    You might also like