kruskal 27s algorithm

1Time complexity:- O(ElogV)

1#include<bits/stdc++.h>
2
3using namespace std;
4
5int  main()
6{
7	int n = 9;
8	
9	int mat[9][9] = {
10	{100,4,100,100,100,100,100,8,100},
11	{4,100,8,100,100,100,100,100,100},
12	{100,8,100,7,100,4,100,100,2},
13	{100,100,7,100,9,14,100,100,100},
14	{100,100,100,9,100,10,100,100,100},
15	{100,100,4,14,10,100,2,100,100},
16	{100,100,100,100,100,2,100,1,6},
17	{8,100,100,100,100,100,1,100,7},
18	{100,100,2,100,100,100,6,7,100}};
19	
20	int parent[n];
21	
22	int edges[100][3];
23	int count = 0;
24	
25	for(int i=0;i<n;i++)
26		for(int j=i;j<n;j++)
27		{
28			if(mat[i][j] != 100)
29			{
30				edges[count][0] = i;
31				edges[count][1] = j;
32				edges[count++][2] = mat[i][j];	
33			}		
34		}
35
36	for(int i=0;i<count-1;i++)
37		for(int j=0;j<count-i-1;j++)
38			if(edges[j][2] > edges[j+1][2])
39				{
40					int t1=edges[j][0], t2=edges[j][1], t3=edges[j][2];
41					
42					edges[j][0] = edges[j+1][0];
43					edges[j][1] = edges[j+1][1];
44					edges[j][2] = edges[j+1][2];
45					
46					edges[j+1][0] = t1;
47					edges[j+1][1] = t2;
48					edges[j+1][2] = t3;
49				}
50				
51	int mst[n-1][2];
52	int mstVal = 0;
53	int l = 0;
54	
55	cout<<endl;
56	
57	for(int i=0;i<n;i++)
58		parent[i] = -1;
59	cout<<endl;
60				
61	for(int i=0;i<count;i++)
62	{
63		if((parent[edges[i][0]] == -1 && parent[edges[i][1]] == -1))
64		{
65			parent[edges[i][0]] = edges[i][0];
66			parent[edges[i][1]] = edges[i][0];
67			
68			mst[l][0] = edges[i][0];
69			mst[l++][1] = edges[i][1];
70			
71			mstVal += edges[i][2];
72		}
73		
74		else if((parent[edges[i][0]] == -1 && parent[edges[i][1]] != -1))
75		{
76			parent[edges[i][0]] = parent[edges[i][1]];
77			
78			mst[l][0] = edges[i][1];
79			mst[l++][1] = edges[i][0];
80			
81			mstVal += edges[i][2];
82		}
83		
84		else if((parent[edges[i][0]] != -1 && parent[edges[i][1]] == -1))
85		{
86			parent[edges[i][1]] = parent[edges[i][0]];
87			
88			mst[l][0] = edges[i][0];
89			mst[l++][1] = edges[i][1];
90			
91			mstVal += edges[i][2];
92		}
93		
94		else if(parent[edges[i][0]] != -1 && parent[edges[i][1]] != -1 && parent[edges[i][0]] != parent[edges[i][1]])
95		{
96			int p = parent[edges[i][1]];
97			for(int j=0;j<n;j++)
98				if(parent[j] == p)
99					parent[j] = parent[edges[i][0]];
100			
101			mst[l][0] = edges[i][0];
102			mst[l++][1] = edges[i][1];
103			
104			mstVal += edges[i][2];
105		}
106	}
107	
108	for(int i=0;i<l;i++)
109		cout<<mst[i][0]<<" -> "<<mst[i][1]<<endl;
110	
111	cout<<endl;
112	cout<<mstVal<<endl;
113		
114	return(0);
115}

1//MINIMUM SPANNING TREE USING KRUSHKAL ALGORITHM
2#include<bits/stdc++.h>
3using namespace std;
4struct node
5{
6    int u,v,wt;
7    node(int first,int second, int weight)
8    {
9        u=first;
10        v=second;
11        wt=weight;
12    }
13};
14bool cmp(node a,node b)
15{
16    return (a.wt<b.wt);
17}
18int findpar(int u,vector<int>&parent)
19{
20    if(u==parent[u])
21    {
22        return u;
23    }
24    return findpar(parent[u],parent);
25}
26void unionoperation(int u,int v,vector<int>&parent,vector<int>&rank)
27{
28    u=findpar(u,parent);
29    v=findpar(v,parent);
30    if(rank[u]<rank[v])
31    {
32        parent[u]=v;
33    }
34    else if(rank[v]<rank[u])
35    {
36        parent[v]=u;
37    }
38    else
39    {
40        parent[v]=u;
41        rank[u]++;
42    }
43}
44int main()
45{
46    int vertex,ed;
47    cout<<"Enter the number of vertex and edges:"<<endl;
48    cin>>vertex>>ed;
49    vector<node>edges;
50     cout<<"enter the links and weight:"<<endl;
51    for(int i=0;i<ed;i++)
52    {
53        int u,v,wt;
54        cin>>u>>v>>wt;
55        edges.push_back(node(u,v,wt));
56    }
57    sort(edges.begin(),edges.end(),cmp);
58    vector<int>parent(vertex);
59    for(int i=0;i<vertex;i++)
60    {
61        parent[i]=i;
62    }
63    vector<int>rank(vertex,0);
64    int cost=0;
65    vector<pair<int,int>>mst;
66    for(auto i:edges)
67    {
68        if(findpar(i.u,parent)!=findpar(i.v,parent))
69        {
70            cost+=i.wt;
71            mst.push_back(make_pair(i.u,i.v));
72            unionoperation(i.u,i.v,parent,rank);
73        }
74    }
75    cout<<cost<<endl;
76    for(auto i:mst)
77    {
78        cout<<i.first<<"-"<<i.second<<endl;
79    }
80    return 0;
81}
82

1#include<bits/stdc++.h> 
2using namespace std; 
3  
4
5typedef  pair<int, int> iPair; 
6  
7
8struct Graph 
9{ 
10    int V, E; 
11    vector< pair<int, iPair> > edges; 
12  
13   
14    Graph(int V, int E) 
15    { 
16        this->V = V; 
17        this->E = E; 
18    } 
19  
20    void addEdge(int u, int v, int w) 
21    { 
22        edges.push_back({w, {u, v}}); 
23    } 
24 
25  
26    int kruskalMST(); 
27}; 
28  
29
30struct DisjointSets 
31{ 
32    int *parent, *rnk; 
33    int n; 
34  
35
36    DisjointSets(int n) 
37    { 
38    
39        this->n = n; 
40        parent = new int[n+1]; 
41        rnk = new int[n+1]; 
42  
43    
44        for (int i = 0; i <= n; i++) 
45        { 
46            rnk[i] = 0; 
47  
48      
49            parent[i] = i; 
50        } 
51    } 
52 
53    int find(int u) 
54    { 
55     
56        if (u != parent[u]) 
57            parent[u] = find(parent[u]); 
58        return parent[u]; 
59    } 
60  
61 
62    void merge(int x, int y) 
63    { 
64        x = find(x), y = find(y); 
65  
66       
67        if (rnk[x] > rnk[y]) 
68            parent[y] = x; 
69        else 
70            parent[x] = y; 
71  
72        if (rnk[x] == rnk[y]) 
73            rnk[y]++; 
74    } 
75}; 
76  
77
78  
79int Graph::kruskalMST() 
80{ 
81    int mst_wt = 0; 
82  
83    sort(edges.begin(), edges.end()); 
84  
85
86    DisjointSets ds(V); 
87  
88
89    vector< pair<int, iPair> >::iterator it; 
90    for (it=edges.begin(); it!=edges.end(); it++) 
91    { 
92        int u = it->second.first; 
93        int v = it->second.second; 
94  
95        int set_u = ds.find(u); 
96        int set_v = ds.find(v); 
97  
98      
99        if (set_u != set_v) 
100        { 
101          
102            cout << u << " - " << v << endl; 
103  
104      
105            mst_wt += it->first; 
106  
107        
108            ds.merge(set_u, set_v); 
109        } 
110    } 
111  
112    return mst_wt; 
113} 
114  
115
116int main() 
117{ 
118   
119    int V = 9, E = 14; 
120    Graph g(V, E); 
121  
122   
123    g.addEdge(0, 1, 4); 
124    g.addEdge(0, 7, 8); 
125    g.addEdge(1, 2, 8); 
126    g.addEdge(1, 7, 11); 
127    g.addEdge(2, 3, 7); 
128    g.addEdge(2, 8, 2); 
129    g.addEdge(2, 5, 4); 
130    g.addEdge(3, 4, 9); 
131    g.addEdge(3, 5, 14); 
132    g.addEdge(4, 5, 10); 
133    g.addEdge(5, 6, 2); 
134    g.addEdge(6, 7, 1); 
135    g.addEdge(6, 8, 6); 
136    g.addEdge(7, 8, 7); 
137  
138    cout << "Edges of MST are \n"; 
139    int mst_wt = g.kruskalMST(); 
140  
141    cout << "\nWeight of MST is " << mst_wt; 
142  
143    return 0; 
144}