|
Kruskal algoritmi
Daraxt , Algoritm , Daraxt
Kruskal algoritmi - bu grafikni kirish sifatida qabul qiluvchi va har bir cho'qqisini o'z ichiga olgan daraxtni tashkil etuvchi, shuningdek, barcha daraxtlar orasidagi minimal og'irliklar yig'indisiga ega bo'lgan ushbu grafik qirralarining kichik to'plamini topadigan minimal kenglikdagi daraxt algoritmidir. grafik.
Tarkib
1. Kruskal algoritmi qanday ishlaydi
2. Kruskal algoritmiga misol
3. Kruskal algoritmi. Psevdokod.
4. C++ tilida Kruskal algoritmini amalga oshirish
5. Kraskal vs Prima algoritmi
ADS
Kruskal algoritmi qanday ishlaydi
U global optimalni topish umidida mahalliy optimalni topadigan "ochko'z" algoritmlar deb ataladigan algoritmlar sinfiga kiradi .
Biz eng kam og'irlikdagi qirralardan boshlaymiz va maqsadimizga erishgunimizcha qirralarni qo'shishda davom etamiz.
Kruskal algoritmini amalga oshirish bosqichlari quyidagilardan iborat:
Barcha qirralarni past og'irlikdan yuqori vazngacha tartiblang.
Eng kichik og'irlikdagi chekka oling va uni yoyilgan daraxtga qo'shing. Agar chekka qo'shilganda tsikl yaratilgan bo'lsa, bu chekkadan voz keching.
Barcha cho'qqilarga yetguncha qirralarni qo'shishni davom eting.
Kruskal algoritmiga misol
Kruskal algoritmi. Psevdokod.
Har qanday minimal kengaytmali daraxt algoritmi chekka tsikl hosil qiladimi yoki yo'qligini tekshirish atrofida aylanadi.
Buni aniqlashning eng keng tarqalgan usuli Union FInd algoritmidir . Union-Find algoritmi cho'qqilarni klasterlarga ajratadi va bizga ikkita cho'qqi bir xil klasterga tegishli yoki yo'qligini tekshirishga imkon beradi va shuning uchun chekka qo'shish sikl hosil qiladimi yoki yo'qligini hal qiladi.
KRUSKAL(G):( G ):
A = ∅
Har bir tepalik uchun v ∈ G . V :
MAKE - SET ( v )
Har bir chekka uchun ( u , v ) ∈ G . E vazn bo'yicha tartibni oshirish orqali tartiblangan ( u , v ):
agar FIND - SET ( u ) ≠ FIND - SET ( v ):
A = A ∪ {( u , v )}
UNION ( u , v )
qaytish A
C++ da Kruskal algoritmini amalga oshirish
Quyida C++ da amalga oshirish uchun kod keltirilgan. Ishimizni oson va toza qilish uchun biz standart shablon kutubxonalaridan foydalanamiz.
#include
#o'z ichiga
#include
std nom maydonidan foydalanish ;
#define chekka juft < int , int >
sinf grafigi {
xususiy :
vektor < juft < int , chekka >> G ; // grafik
vektor < juft < int , chekka >> T ; // mst
int * ota ;
int V ; // grafikdagi uchlari/tugunlar soni
ommaviy :
Grafik ( int V );
void AddWeightedEdge ( int u , int v , int w );
int find_set ( int i );
void union_set ( int u , int v );
bekor kruskal ();
bo'sh joy ( );
};
Grafik :: Grafik ( int V ) {
ota = new int [ V ];
//i 0 1 2 3 4 5
//ota-ona[i] 0 1 2 3 4 5
uchun ( int i = 0 ; i < V ; i ++)
ota [ i ] = i ;
G. _ aniq ();
T. _ aniq ();
}
void Grafik :: AddWeightedEdge ( int u , int v , int w ) {
G. _ surish_orqaga ( juftlash_ko'rsatish ( w , chekka ( u , v )));
}
int Grafik :: find_set ( int i ) {
// Agar i o'zining ota-onasi bo'lsa
agar ( i == ota [ i ])
qaytib i ;
boshqa
// Aks holda, agar i o'zining ota-onasi bo'lmasa
// Unda men uning to'plamining vakili emasman,
// shuning uchun biz uning ota-onasini rekursiv ravishda Find deb chaqiramiz
find_setni qaytarish ( ota-ona [ i ]);
}
bekor Grafik :: union_set ( int u , int v ) {
ota-ona [ u ] = ota-ona [ v ];
}
bekor Grafik :: kruskal () {
int i , uRep , vRep ;
tartiblash ( G.boshlash ( ), G.end ( ) ) ; // vaznni oshirish
uchun ( i = 0 ; i < G . hajmi (); i ++) {
uRep = find_set ( G [ i ] .ikkinchi.birinchi ) ; _
vRep = find_set ( G [ i ] .ikkinchi.soniya ) ; _
agar ( uRep != vRep ) {
T. _ orqaga surish ( G [ i ]); // daraxtga qo'shish
union_set ( uRep , vRep );
}
}
}
bekor Grafik :: chop etish () {
cout << "Edge :" << "Og'irlik" << endl ;
for ( int i = 0 ; i < T . size (); i ++) {
cout << T [ i ]. ikkinchi . birinchi << " - " << T [ i ]. ikkinchi . ikkinchi << " : "
<< T [ i ]. birinchi ;
cout << endl ;
}
}
int main () {
Grafik g ( 6 );
g . AddWeightedEdge ( 0 , 1 , 4 );
g . AddWeightedEdge ( 0 , 2 , 4 );
g . AddWeightedEdge ( 1 , 2 , 2 );
g . AddWeightedEdge ( 1 , 0 , 4 );
g . AddWeightedEdge ( 2 , 0 , 4 );
g . AddWeightedEdge ( 2 , 1 , 2 );
g . AddWeightedEdge ( 2 , 3 , 3 );
g . AddWeightedEdge ( 2 , 5 , 2 );
g . AddWeightedEdge ( 2 , 4 , 4 );
g . AddWeightedEdge ( 3 , 2 , 3 );
g . AddWeightedEdge ( 3 , 4 , 3 );
g . AddWeightedEdge ( 4 , 2 , 4 );
g . AddWeightedEdge ( 4 , 3 , 3 );
g . AddWeightedEdge ( 5 , 2 , 2 );
g . AddWeightedEdge ( 5 , 4 , 3 );
g . kruskal ();
g . chop etish ();
qaytish 0 ;
}
Dasturni ishga tushirganimizda biz quyidagi natijalarni olamiz:
Kenar: Og'irligi : Og'irligi
1-2 : 2 _ _
2-5 : 2 _ _
2-3 : 3 _ _
3-4 : 3 _ _
0 - 1 : 4
Kraskal algoritmi Primaga qarshi
Prim algoritmi MST grafigini topish uchun boshqa mantiqdan foydalanadigan yana bir mashhur minimal oraliqli daraxt algoritmidir. Prim algoritmi chekkadan boshlash o'rniga, cho'qqidan boshlanadi va barcha cho'qqilar qoplanmaguncha daraxtda bo'lmagan eng kichik og'irlikdagi qirralarni qo'shishda davom etadi.
Do'stlaringiz bilan baham: |
