#include - Samarqand davlat universiteti o. R. Yusupov, I. Q. Ximmatov, E. Sh. Eshonqulov

{0, 9, 75, 0, 0}, {9, 0, 95, 19, 42}, {75, 95, 0, 51, 66}, {0, 19, 51, 0, 31}, {0, 42, 66, 31, 0} int selected[V]; // dastlab false qiymatini berish memset (selected, false, sizeof (selected)); // qirra va ogʻirlikni chop etish cout cout while (no_edge int min = INF; if (!selected[j] G[i][j]) { if (min > G[i][j]) { min = G[i][j]; x = i; y = j; } } cout selected[y] = true; no_edge++; } return 0; } Mavzu yuzasidan savollar16-§. Minimal yoʻlni topish masalasi |
Samarqand davlat universiteti o. R. Yusupov, I. Q. Ximmatov, E. Sh. EshonqulovBog'liq ALGORITMLAR VA MA‟LUMOTLAR STRUKTURALARIBu sahifa navigatsiya:
- {0, 9, 75, 0, 0}, {9, 0, 95, 19, 42}, {75, 95, 0, 51, 66}, {0, 19, 51, 0, 31}, {0, 42, 66, 31, 0}
- int selected[V]; // dastlab false qiymatini berish memset (selected, false, sizeof (selected));
- // qirra va ogʻirlikni chop etish cout cout while (no_edge int min = INF;
- if (!selected[j] G[i][j]) { if (min > G[i][j]) { min = G[i][j]; x = i; y = j; } }
- cout selected[y] = true; no_edge++; } return 0; } Mavzu yuzasidan savollar
- 16-§. Minimal yoʻlni topish masalasi
#include
#include
using namespace std;
#define INF 9999999
// grafdagi uchlar soni
#define V 5
//Qo'shnilik matritsasini ifodalash uchun
//5x5 o'lchamdagi ikki o'lchamli massivni yaratish
int G[V][V] = {
{0, 9, 75, 0, 0},
{9, 0, 95, 19, 42},
{75, 95, 0, 51, 66},
{0, 19, 51, 0, 31},
{0, 42, 66, 31, 0}
180
};
int main () {
int no_edge; // qirralar soni
// tanlangan uchni kuzatish uchun massiv yaratish
int selected[V];
// dastlab false qiymatini berish
memset (selected, false, sizeof (selected));
// qiralar soniga 0 ni berish
no_edge = 0;
selected[0] = true;
int x; // qator raqami
int y; // ustun raqami
// qirra va ogʻirlikni chop etish
cout << "Qirra" << " : " << "Masofasi";
cout << endl;
while (no_edge < V - 1) {
int min = INF;
x = 0;
y = 0;
for (int i = 0; i < V; i++) {
if (selected[i]) {
for (int j = 0; j < V; j++) {
if (!selected[j] && G[i][j]) {
if (min > G[i][j]) {
min = G[i][j];
x = i;
y = j;
}
}
}
}
}
181
cout << x << " - " << y << " : " << G[x][y];
cout << endl;
selected[y] = true;
no_edge++;
}
return 0;
}
Mavzu yuzasidan savollar:
1.
Eng kichik uzunlikdagi daraxt nima?
2.
Prima algoritmining murakkabligini baholang.
3.
Kruskal algoritmining murakkabligini baholang.
16-§. Minimal yoʻlni topish masalasi
Amaliyotda uchraydigan ko‗plab masalalarda marshrut uzunligi
maksimallashtirilishi yoki minimallashtirilishi talab etiladi. Shunday
masalalardan biriga, aniqrogʻi, kommivoyajer masalasiga Gamilton
graflari bilan shugʻullanganda duch kelamiz.
)
,
(
U
V
G
oriyentirlangan graf berilgan bo‗lsin, bu yerda
}
,...,
2
,
1
{
m
V
.
G
grafning biror
V
s
uchidan boshqa
V
t
uchiga boruvchi yo‗llar
orasida uzunligi eng kichik bo‗lganini topish masalasi bilan
shugʻullanamiz. Bu masalani
minimal uzunlikka ega yo„l haqidagi
masala
deb ataymiz. Quyida bu masalaning umumlashmasi hisoblangan
masalani qarab, uni ham o‗sha nom bilan ataymiz.
Grafdagi
)
,
(
j
i
yoyning uzunligini
ij
c
bilan belgilab,
m
j
i
c
C
ij
,
1
,
),
(
,
matritsa berilgan deb hisoblaymiz. Yuqorida ta‘kidlaganlarimizga ko‗ra,
C
matritsaning
ij
c
elementlari orasida manfiylari yoki nolga tenglari ham
bo‗lishlari mumkin. Agar grafda biror
i
uchdan chiqib
j
uchga kirruvchi
yoy mavjud bo‗lmasa, u holda bu yoyning uzunligini cheksiz katta deb
qabul qilamiz (
ij
c
). Bundan tashqari,
G
grafda umumiy uzunligi
182
manfiy bo‗lgan sikl mavjud emas deb hisoblaymiz, chunki aks holda
uzunligi eng kichik bo‗lgan yo‗l mavjud emas
5
.
Minimal uzunlikka ega yo‗l haqidagi masalani hal etish usullari
orasida Deykstra
6
tomonidan taklif etilgan algoritm ko‗p qo‗llaniladi.
Quyida grafning 1 belgili uchidan chiqib (bu uchni manba deb qabul
qilamiz) grafdagi ixtiyoriy
k
uchgacha (bu uchni oxirgi uch deb
hisoblaymiz) eng qisqa uzunlikka ega yo‗lni topish imkonini beruvchi
|
| |