Minimal kenglikdagi daraxt Kruskal algoritmi
![MSTda 3-4 chekka qo'shing
Eslatma: MSTga kiritilgan qirralarning soni ( N – 1) ga teng bo lgani uchunʻ
algoritm shu yerda to xtaydi.
ʻ
2.3 Kruskal algoritmiga oid C++ dasturlash tilida dastur.
#include <bits/stdc++.h>
using namespace std;
class DSU {
int* parent;
int* rank;
public:
DSU(int n)
{
parent = new int[n];
rank = new int[n];
for (int i = 0; i < n; i++) {
parent[i] = -1;
rank[i] = 1;
}
12](https://docx.uz/documents/90ee38dd-4f95-483e-ba4e-8135e09fc513/page_12.png?v=1)
![}
int find(int i)
{
if (parent[i] == -1)
return i;
return parent[i] = find(parent[i]);
}
void unite(int x, int y)
{
int s1 = find(x);
int s2 = find(y);
if (s1 != s2) {
if (rank[s1] < rank[s2]) {
parent[s1] = s2;
}
else if (rank[s1] > rank[s2]) {
parent[s2] = s1;
}
else {
parent[s2] = s1;
rank[s1] += 1;
}
}
}
};
class Graph {
vector<vector<int> > edgelist;
int V;
public:
Graph(int V) { this->V = V; }
void addEdge(int x, int y, int w)
{
edgelist.push_back({ w, x, y });
}
void kruskals_mst()
{
13](https://docx.uz/documents/90ee38dd-4f95-483e-ba4e-8135e09fc513/page_13.png?v=1)
![sort(edgelist.begin(), edgelist.end());
DSU s(V);
int ans = 0;
cout << "Following are the edges in the "
"constructed MST"
<< endl;
for (auto edge : edgelist) {
int w = edge[0];
int x = edge[1];
int y = edge[2];
if (s.find(x) != s.find(y)) {
s.unite(x, y);
ans += w;
cout << x << " -- " << y << " == " << w
<< endl;
}
}
cout << "Minimum Cost Spanning Tree: " << ans;
}
};
int main()
{
Graph g(4);
g.addEdge(0, 1, 10);
g.addEdge(1, 3, 15);
g.addEdge(2, 3, 4);
g.addEdge(2, 0, 6);
g.addEdge(0, 3, 5);
g.kruskals_mst();
return 0;
}
Dasturning natijasi.
Quyida tuzilgan MSTning qirralari keltirilgan
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10
Minimal xarajat yoyilgan daraxt: 19
14](https://docx.uz/documents/90ee38dd-4f95-483e-ba4e-8135e09fc513/page_14.png?v=1)
![MSTga tanlangan chekka qo'shing, agar u hech qanday tsiklni hosil
qilmasa.
6-qadam:
MSTni qaytaring va chiqing .
Prim algoritmining tasviri:
Prim algoritmiga oid C++ dasturlash tilida dastur.
#include <bits/stdc++.h>
using namespace std;
// Number of vertices in the graph
#define V 5
// A utility function to find the vertex with
// minimum key value, from the set of vertices
// not yet included in MST
int minKey( int key[], bool mstSet[])
{
// Initialize min value
int min = INT_MAX, min_index;
for ( int v = 0; v < V; v++)
if (mstSet[v] == false && key[v] < min)
min = key[v], min_index = v;
return min_index;
}
// A utility function to print the
// constructed MST stored in parent[]
void printMST( int parent[], int graph[V][V])
16](https://docx.uz/documents/90ee38dd-4f95-483e-ba4e-8135e09fc513/page_16.png?v=1)
![{
cout << "Edge \tWeight\n";
for ( int i = 1; i < V; i++)
cout << parent[i] << " - " << i << " \t"
<< graph[i][parent[i]] << " \n";
}
// Function to construct and print MST for
// a graph represented using adjacency
// matrix representation
void primMST( int graph[V][V])
{
// Array to store constructed MST
int parent[V];
// Key values used to pick minimum weight edge in cut
int key[V];
// To represent set of vertices included in MST
bool mstSet[V];
// Initialize all keys as INFINITE
for ( int i = 0; i < V; i++)
key[i] = INT_MAX, mstSet[i] = false ;
// Always include first 1st vertex in MST.
// Make key 0 so that this vertex is picked as first
// vertex.
key[0] = 0;
// First node is always root of MST
parent[0] = -1;
// The MST will have V vertices
for ( int count = 0; count < V - 1; count++) {
// Pick the minimum key vertex from the
// set of vertices not yet included in MST
int u = minKey(key, mstSet);
// Add the picked vertex to the MST Set
mstSet[u] = true ;
// Update key value and parent index of
17](https://docx.uz/documents/90ee38dd-4f95-483e-ba4e-8135e09fc513/page_17.png?v=1)
![// the adjacent vertices of the picked vertex.
// Consider only those vertices which are not
// yet included in MST
for ( int v = 0; v < V; v++)
// graph[u][v] is non zero only for adjacent
// vertices of m mstSet[v] is false for vertices
// not yet included in MST Update the key only
// if graph[u][v] is smaller than key[v]
if (graph[u][v] && mstSet[v] == false
&& graph[u][v] < key[v])
parent[v] = u, key[v] = graph[u][v];
}
// Print the constructed MST
printMST(parent, graph);
}
// Driver's code
int main()
{
int graph[V][V] = { { 0, 2, 0, 6, 0 },
{ 2, 0, 3, 8, 5 },
{ 0, 3, 0, 0, 7 },
{ 6, 8, 0, 0, 9 },
{ 0, 5, 7, 9, 0 } };
// Print the solution
primMST(graph);
return 0;
}
// This code is contributed by rathbhupendra
Chiqish
Kenar og'irligi
0 - 1 2
1 - 2 3
0 - 3 6
1 - 4 5
18](https://docx.uz/documents/90ee38dd-4f95-483e-ba4e-8135e09fc513/page_18.png?v=1)
Minimal kenglikdagi daraxt Kruskal algoritmi