Graf nazariyasining asosiy ta’riflarini o‘rganing
Graf — bu chekli cho‘qqilar va ularni bog‘lovchi qirralar to‘plamidan iborat bo‘lgan chiziqli bo‘lmagan ma’lumotlar tuzilmasi.
Grafdagi yo‘l — bu cho‘qqilar ketma-ketligi bo‘lib, unda har bir qo‘shni cho‘qqilar jufti qirra bilan bog‘langan bo‘ladi. Boshqacha aytganda, har bir uchun va orasida qirra mavjud.
Birinchi cho‘qqi yo‘lning boshi, oxirgi cho‘qqi esa yo‘lning oxiri deb ataladi.
Rasmdagi misollar:
Yo‘l uzunligi — undagi qirralar soni.
Sikl — bu bir xil cho‘qqida boshlanib, bir xil cho‘qqida tugaydigan yo‘l, ya’ni .
Rasmdagi misol:
Bog‘langan komponenta — bu cho‘qqilar to‘plami bo‘lib, to‘plamdagi istalgan cho‘qqi graf qirralari orqali shu to‘plamdagi istalgan boshqa cho‘qqiga yetib bora oladi.
Rasmdagi graf uchun bog‘langan komponentalar:
Qirralar yo‘naltirilgan yoki yo‘naltirilmagan bo‘lishi mumkin.
Agar qirra yo‘naltirilmagan bo‘lsa, unda biz ham dan ga, ham dan ga harakatlana olamiz.
Agar qirra yo‘naltirilgan bo‘lsa, unda harakat faqat dan ga ruxsat etiladi.
Qirra og‘irlik ga ega bo‘lishi mumkin.
Og‘irlik ushbu qirrani ishlatish qiymatini bildiradi. Masalan, yo‘l tarmog‘ida cho‘qqilar shaharlarni, qirralar yo‘llarni, og‘irlik esa shu yo‘l bo‘ylab harakatlanish qiymati yoki masofasini ifodalashi mumkin.
Bir xil cho‘qqilar jufti orasida bir nechta qirra bo‘lishi mumkin. Bunday qirralar ko‘p qirralar yoki parallel qirralar deb ataladi.
Cho‘qqining o‘ziga ham qirra bo‘lishi mumkin. Bunday qirra halqa deb ataladi.
Yo‘naltirilmagan graf — bu barcha qirralari yo‘naltirilmagan bo‘lgan graf.
Yo‘naltirilgan graf — bu barcha qirralari yo‘naltirilgan bo‘lgan graf.
Siklsiz yo‘naltirilgan graf — bu sikllarni o‘z ichiga olmaydigan yo‘naltirilgan graf.
Bog‘langan graf — bu har bir cho‘qqi har qanday boshqa cho‘qqiga yetib bora oladigan graf.
Boshqacha aytganda, u aynan bitta bog‘langan komponentadan iborat.
Daraxt — bu sikllarsiz bog‘langan yo‘naltirilmagan graf.
Daraxtning muhim xossalari:
Ikki qismli graf — bu cho‘qqilari ikki guruhga bo‘linishi mumkin bo‘lgan graf bo‘lib, har bir qirra bir guruhdagi cho‘qqini boshqa guruhdagi cho‘qqi bilan bog‘laydi.
Demak, bir xil guruhdagi ikki cho‘qqini bog‘laydigan qirralar bo‘lmaydi.
Ikkilik daraxt — bu har bir cho‘qqisi ko‘pi bilan ikkita farzandga ega bo‘lgan daraxt.
Har bir farzandning o‘zi ham boshqa ikkilik daraxtning ildizi hisoblanadi.
Har bir cho‘qqida odatda ma’lumotlar va uning ota-ona hamda farzandlariga ko‘rsatkichlar saqlanadi.
Ikkilik daraxtni aylanib chiqishning uchta keng tarqalgan usuli mavjud:
Algoritm:
Aylanib chiqish natijasi:
Algoritm:
Aylanib chiqish natijasi:
Algoritm:
Aylanib chiqish natijasi:
struct Node {
Node* parent;
Node* left;
Node* right;
int value;
Node(Node* parent_, int value_) : parent(parent_),
value(value_),
left(nullptr),
right(nullptr) {}
};
void printPreOrder(Node* node) {
if (node == nullptr) {
return;
}
cout << node->value << " ";
printPreOrder(node->left);
printPreOrder(node->right);
}
void printInOrder(Node* node) {
if (node == nullptr) {
return;
}
printInOrder(node->left);
cout << node->value << " ";
printInOrder(node->right);
}
void printPostOrder(Node* node) {
if (node == nullptr) {
return;
}
printPostOrder(node->left);
printPostOrder(node->right);
cout << node->value << " ";
}