5-amaliy mashg’ulot Ishdan maqsad

Graflarni ko‘rikdan o‘tkazish
Grafni ko‘rikdan o‘tkazish (Graph traversal) – bu berilgan tugundan boshlab barcha tugunlarni ko‘rib chiqish prosedurasidir.
Ikkita usuli mavjud:
Tubiga qarab(Depth-First Search – DFS)
Eniga qarab(Breadth-First Search – BFS)
Bu usullar berilgan V tugundan boshlab bironta konteynerni qo‘llagan xolda barcha tugunlarni ko‘rib chiqadi.
Tubiga qarab ko‘rishda stek qo‘llaniladi.
Eniga qarab ko‘rishda navbat ishlatiladi.
Graflarda qisqa yo’lni aniqlash algoritmlari
Quyida tasvirlangan graf uchun minimal narxli daraxt skeletini qurish usullaridan Kruskal usuli yordamida yechilsin va dasturini tuzilsin.

Kruskal algoritmining bajaralishi quyidagicha amalaga oshiriladi.

Quyida Kruskal algoritmidan foydalangan holda MSTni topish bo'yicha qadamlar keltirilgan

1. 
   Barcha qirralarni vaznining o’sish tartibida saralash.
   
2. 
   Eng kichik tugunni tanlang. Hozirgacha shakllangan daraxt bilan sikl hosil qiladimi yoki yo'qligini tekshirib ko'ring. Agar sikl shakllanmagan bo'lsa, ushbu tugunni kiriting. Boshqalari, tashlab yuboring.
   
3. 
   Yopilgan daraxtda (V-1) qirralar bo'lguncha # 2-bosqichni takrorlang.
   

STL yordamida Kruskal algoritmini amalga oshirishda biz uchun foydali bo'lgan ba'zi bir muhim fikrlar.

1. 
   Grafadagi barcha qirralardan iborat qirralarning vektoridan foydalaning va vektorning har bir elementi uchta parametrni o'z ichiga oladi: manba, manzil va manba va manzil orasidagi tugun narxi.
   

vector
> > edges;

2. 
   Bu erda tashqi juftlikda (ya'ni juftlik >) birinchi element tugun narxiga to'g'ri keladi, ikkinchi element o'zi juft bo'lib, u tugunning ikkita tepasini o'z ichiga oladi.
   
3. 
   Qirralarni o’sish tartibda saralash uchun ichki std :: sort dan foydalaning ; 
   
4. 
   Birlashma topish algoritmidan foydalanamiz, agar u joriy tugun MSTga qo'shilsa, sikl hosil qiladimi. Agar ha rad etsa, uni qo'shib qo'ying (birlashma).
   

Ushbu algoritm O (M log N + N2) vaqtda bajariladi. Qirralarni saralash uchun O(M logN) ta operasiya kerak bo’ladi. Tugun u yoki bu qism daraxtga tegishli bo‘lsa, tree_id massiv yordamida saqlanadi, bu massivda har bir tugun uchun u tegishli bo‘lgan daraxt nomeri saqlanadi. Har bir qirra uchun O(1) vaqtda uning tugunlari turli daraxtlarga tegishli ekanligini aniqlanadi. Nihoyat, ikkita daraxtni birlashtirish O (N) vaqtda bajariladi. Birlashtirish operatori O(N) o‘tishda bajarilishini hisobga olsak, O (M log N + N2) kelib chiqadi.

Dastur ko‘rinishi quyidagicha bo’ladi:
#include
using namespace std;
typedef pair iPair;
struct Graph
{
int V, E;
vector< pair > edges;
// Constructor
Graph(int V, int E)
{
this->V = V;
this->E = E;
}
void addEdge(int u, int v, int w)
{
edges.push_back({w, {u, v}});
}
int kruskalMST();
};
// To represent Disjoint Sets
struct DisjointSets
{
int *parent, *rnk;
int n;
DisjointSets(int n)
{
// Allocate memory