Graflarni tasvirlash usullari Graflarni kompyuterda ifodalash, ya’ni xotirada tashkil etish mumkin va uning ba’zi usullari:
Qo‘shma matrisa ;
Munosabat matrisasi;
Qo‘shnilik ro‘yxati;
Qirralar ro‘yxati.
G grafning qo‘shma matrisasi bu n o‘lchamli A kvadrat matrisa bo‘lib, YO‘NALTIRILMAGAN GRAF UChUN: Aij = 1 agar i va j tugunlar yoylar bilan birlashtirilgan bo‘lsa
Aij = 0 agar i va j tugunlar birlashtirilmagan bo‘lsa
G grafning munosabat matrisasi bu n satr(tugunlar) va m ustunlar(qirralar) dan tashkil topgan V matrisa bo‘lib, unda:
YO‘NALTIRILMAGAN GRAF UChUN: Bij = 1 agar i tugun j qirra bilan to‘qnashgan bo‘lsa
Bij = 0 agar i tugun j qirra bilan to‘qnashmagan bo‘lsa
YO‘NALTIRILGAN GRAF UChUN : Bij = -1 agar i tugun j yoyning boshi bo‘lsa
Bij = 0 agar i tugun j yoy bilan to‘qnashmagan bo‘lsa
Bij = 1 agar i tugun j yoyning oxiri bo‘lsa
Qo‘shnilik ro‘yxati (qo‘shni tugunlar) (adjacency list) – bu A[n] massiv bo‘lib, A[i] xar bir elementi i tugun bilan qo‘shni uzellar ro‘yxatini o‘zida saqlaydi.
Yoylar ro‘yxati (edges list) – qo‘shni uzellar yoylaridan iborat chiziqli ro‘yxatdir.
Qo‘shma matrisa
Graf:
4
1
6
7
2
3
8
5
3
5
3
1
4
2
6
2
6
1
Munosabat matrisasi
1-2 1-4 1-6 2-6 2-7 3-5 3-8 4-6 5-8 6-7
1
2
3
4
5
6
7
8
Qo‘shnilik ro‘yxati
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.
Amaliy Dasturdagi Kornishi
Masala. Bizga bir bir tugunli massuv berilgan u massivni bir elemrntidan ikkinchi elementiga
boradigan eng yaqin yolni topish dasturni tuzing.
