Amaliy ish №13 Mavzu: Kruskal algoritmi. Prima algoritmi. Xoffman daraxtlari Minimal kenglikdagi daraxt. Kruskal algoritmi

Quyidagi graf berilgan bo’lsin:

Garning matritsa shaklida berilishi:
7
0 5 -1 8 -1 2 6
5 0 -1 7 4 -1 -1
-1 -1 0 -1 -1 5 4
8 7 -1 0 3 4 -1
-1 4 -1 3 0 6 -1
2 -1 5 4 6 0 7
6 -1 4 -1 -1 7 0

CPP dagi kodi:
#include
#include

using namespace std;

int main()

{
// kiruvchi ma'umotlar
int n;
cin >> n;
int g[n][n];
for(int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> g[i][j];
}
}
for(int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (g[i][j] != g[j][i]) {
cout << "ERROR " << i<<" "<exit(0);
}
}
}
const int INF = 1000000000; // "cheksiz" qiymati

// algoritm

vector used (n);
vector min_e (n, INF), sel_e (n, -1); //elementlar soni n bo'lgan vector e'lon qilish va barchasini bir xil qiymat bilan to'ldirish
min_e[0] = 0;
vector < pair > res;
long long cost = 0;
for (int i=0; iint v = -1;
for (int j=0; jif (!used[j] && (v == -1 || min_e[j] < min_e[v]))
v = j;
if (min_e[v] == INF) {
cout << "Minimal daraxt mavjud e'mas, ya'ni graf bog'lanmagan!";
exit(0);
}

used[v] = true;

if (sel_e[v] != -1) {
res.push_back (make_pair (v, sel_e[v]));
cost += min_e[v];
}
for (int to=0; toif (g[v][to] > 0 && g[v][to] < min_e[to]) {
min_e[to] = g[v][to];
sel_e[to] = v;
}
}
for (int i = 0; i < n; i++) {
cout << min_e[i] << " ";
}
cout << endl;
cout << "Minamal qoldiq daraxt qirralari summasi: " << cost << endl;
cout << "Qolgan qirralar: " << endl;
for (int i = 0; i < res.size(); i++) {
cout << res[i].first<<" "<}
}



Topshiriqlar:
Graflarda “Xasis ” algoritmlar. Kruskal va Prima algoritmlari.
Berilgan graf uchun minimal qoldiq daraxt(graf skleti) aniqlansin
1.

Bog’lanish	AB	AC	AD	BD	BF	CD	CE	CH	DE	DF	EF	EG	GF	GH
Vazni	5	2	3	4	1	5	2	7	6	8	2	4	3	6

--------------------------------------------------------------------------------------------------------------
2.

Bog’lanish	AB	AC	AD	BD	BF	CD	CE	CH	DE	DF	EF	EG	GF	GH
Vazni	2	3	8	1	5	4	6	2	7	8	5	3	6	7

3.

Bog’lanish	AB	AC	AD	BD	BF	CD	CE	CH	DE	DF	EF	EG	GF	GH
Vazni	4	2	3	6	12	5	8	7	6	12	2	9	3	6

--------------------------------------------------------------------------------------------------

4.

Bog’lanish	AB	AC	AD	BD	BF	CD	CE	CH	DE	DF	EF	EG	GF	GH
Vazni	3	5	2	4	6	5	7	8	6	9	12	4	10	11

----------------------------------------------------------------------------------------------
5.

Bog’lanish	AB	AC	AD	BD	BF	CD	CE	CH	DE	DF	EF	EG	GF	GH
Vazni	15	12	13	4	10	15	14	17	16	8	13	14	17	9

--------------------------------------------------------------------------------------------------------

6.

Bog’lanish	AB	AC	AD	BD	BF	CD	CE	CH	DE	DF	EF	EG	GF	GH
Vazni	8	2	5	4	7	5	12	8	9	8	13	15	16	10