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

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 

Download 4,61 Mb.