Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- using namespace std;
- class Edge
- {
- public:
- int src, dest, weight;
- };
- class Graph
- {
- public:
- int V, E;
- Edge* edge;
- };
- //Graph* createGraph(int V, int E)
- //{
- // Graph* graph = new Graph;
- // graph->V = V;
- // graph->E = E;
- // graph->edge = new Edge[E];
- //
- // return graph;
- //}
- class subset
- {
- public:
- int parent;
- int rank;
- };
- int find(subset subsets[], int i)
- {
- if (subsets[i].parent != i)
- subsets[i].parent = find(subsets, subsets[i].parent);
- return subsets[i].parent;
- }
- void Union(subset subsets[], int x, int y)
- {
- int xroot = find(subsets, x);
- int yroot = find(subsets, y);
- if (subsets[xroot].rank < subsets[yroot].rank)
- subsets[xroot].parent = yroot;
- else if (subsets[xroot].rank > subsets[yroot].rank)
- subsets[yroot].parent = xroot;
- else
- {
- subsets[yroot].parent = xroot;
- subsets[xroot].rank++;
- }
- }
- int myComp(const void* a, const void* b)
- {
- Edge* a1 = (Edge*)a;
- Edge* b1 = (Edge*)b;
- return a1->weight > b1->weight;
- }
- void KruskalMST(Graph* graph)
- {
- int V = graph->V;
- Edge result[V]; // Tnis will store the resultant MST
- int e = 0; // An index variable, used for result[]
- int i = 0; // An index variable, used for sorted edges
- qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);
- subset *subsets = new subset[( V * sizeof(subset) )];
- for (int v = 0; v < V; ++v)
- {
- subsets[v].parent = v;
- subsets[v].rank = 0;
- }
- while (e < V - 1 && i < graph->E)
- {
- Edge next_edge = graph->edge[i++];
- int x = find(subsets, next_edge.src);
- int y = find(subsets, next_edge.dest);
- if (x != y)
- {
- result[e++] = next_edge;
- Union(subsets, x, y);
- }
- }
- int sum = 0;
- cout<<"Following are the edges in the constructed MST\n";
- for (i = 0; i < e; ++i)
- cout<<result[i].src<<" -- "<<result[i].dest<<" == "<<result[i].weight<<endl;
- for(i =0; i<e; i++)
- sum += result[i].weight;
- cout<<endl<<"Total cost = "<< sum;
- return;
- }
- int main()
- {
- freopen("input.txt","r",stdin);
- Graph* g=new Graph();
- cin>>g->V>>g->E;
- g->edge = new Edge[g->E];
- int i=0;
- while(i<g->E)
- {
- cin>>g->edge[i].src;
- cin>>g->edge[i].dest;
- cin>>g->edge[i].weight;
- i++;
- }
- KruskalMST(g);
- return 0;
- }
Add Comment
Please, Sign In to add comment