top of page
Caută
  • Poza scriitoruluioanaunciuleanu

Kruskal’s Minimum Spanning Tree Algorithm in C++



A spanning tree is a subgraph of an existing graph that is a tree and connects all the nodes. There can be many spanning trees in a graph. Kruskal’s algorithm finds the minimum spanning tree, whose sum of weights of edges is minimum. You have to start by picking one by one the smallest weight between two nodes, that doesn’t create a cycle, and go on until all the nodes are included.



// Kruskal's Minimum Spanning Tree Algorithm

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

#define edgePair pair<int,int>

class Graph
{
    private:
        vector<pair<int, edgePair>> MyGraph;
        vector<pair<int, edgePair>> minSpanTree;
        int *parent;
        int nodes;
    public:
        Graph(int nodes);
        void AddWeightToEdge(int firstNode, int secondNode, int weight);
        int findSet(int i);
        void unionSet(int i, int j);
        void kruskalMinSpanTree();
        void printMinSpanTree();
};

Graph::Graph(int nodes)
{
    parent = new int[nodes];
    for (int i = 0; i < nodes; i++)
    {
        parent[i] = i;
    }
    MyGraph.clear();
    minSpanTree.clear();
}

void Graph::AddWeightToEdge(int firstNode, int secondNode, int weight)
{
    MyGraph.push_back(make_pair(weight, edgePair(firstNode, secondNode)));
}

int Graph::findSet(int i)
{
    if (i == parent[i])
    {
        return i;
    }
    else
    {
       return findSet(parent[i]);
    }
}

void Graph::unionSet(int i, int j)
{
    parent[i] = parent[j];
}

void Graph::kruskalMinSpanTree()
{
    int i, firstValue, secondValue;
    sort(MyGraph.begin(), MyGraph.end());
    for (i = 0; i < MyGraph.size(); i++)
    {
        firstValue = findSet(MyGraph[i].second.first);
        secondValue = findSet(MyGraph[i].second.second);
        if (firstValue != secondValue)
        {
            minSpanTree.push_back(MyGraph[i]);
            unionSet(firstValue, secondValue);
        }
    }
}

void Graph::printMinSpanTree()
{
    cout << "Node" << "\tWeight" << endl;
    for (int i = 0; i < minSpanTree.size(); i++)
    {
        char firstNode =  minSpanTree[i].second.first + 65;
        char secondNode = minSpanTree[i].second.second + 65;
        cout << firstNode << " - " << secondNode << ": " << minSpanTree[i].first;
        cout << endl;
    }
}
int main()
{
    int numberOfNodes = 5;
    Graph myGraph(numberOfNodes);
    myGraph.AddWeightToEdge(0, 1, 1);
    myGraph.AddWeightToEdge(0, 4, 4);
    myGraph.AddWeightToEdge(1, 0, 1);
    myGraph.AddWeightToEdge(1, 2, 7);
    myGraph.AddWeightToEdge(1, 4, 3);
    myGraph.AddWeightToEdge(2, 1, 7);
    myGraph.AddWeightToEdge(2, 3, 9);
    myGraph.AddWeightToEdge(2, 4, 5);
    myGraph.AddWeightToEdge(3, 2, 9);
    myGraph.AddWeightToEdge(3, 4, 2);
    myGraph.AddWeightToEdge(4, 0, 4);
    myGraph.AddWeightToEdge(4, 1, 3);
    myGraph.AddWeightToEdge(4, 2, 5);
    myGraph.AddWeightToEdge(4, 3, 2);
    myGraph.kruskalMinSpanTree();
    myGraph.printMinSpanTree();
    return 0;
}

Node    Weight
A - B: 1
D - E: 2
B - E: 3
C - E: 5

112 afișări0 comentarii

Postări recente

Afișează-le pe toate

Weighted Job Scheduling in JAVA

You receive a list of jobs that have three elements: start time, finish time and profit. You have to schedule the jobs with no overlapping, in order to obtain the maximum profit. Solution: 1. static

Tiling Problem in JAVA

You can use a board that is 2 x n size. The tiles are of size 2 x 1. Count the number of ways to tile the board. Tiles can be placed vertically 2 x 1 or horizontally as 1 x 2. Solution: 1. static

bottom of page