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



Yüklə 295,82 Kb.
səhifə4/4
tarix14.07.2023
ölçüsü295,82 Kb.
#136559
1   2   3   4
13-amaliyot. Kruskal algoritmi. Prima algoritmi. Xoffman daraxtlari

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




Yüklə 295,82 Kb.

Dostları ilə paylaş:
1   2   3   4




Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©azkurs.org 2024
rəhbərliyinə müraciət

gir | qeydiyyatdan keç
    Ana səhifə


yükləyin