Teg

#graph

Noyabr 13, 2020by Sherzod Shermukhamedov

Topological sort

Biz o'tgan graph masalalarida asosan undirected graph'larni ko'rib chiqdik. Aslida undirected graph directed graph'dan kodda ifodalanganda bor yo'g'i graph'dagi barcha vertex'larning ikki tomonlama (ikki yo'nalishli) bog'langani bilan farq qiladi. Shuning uchun undirected graph masalalaridagi yechim

Noyabr 12, 2020by Sherzod Shermukhamedov

Kenigsbergning yetti ko'prigi

The-Koenigsberg-bridge-problem-a-seven-bridges-of-Koenigsberg-b-graph-representation

Kenigsberg (Königsberg, hozirgi Kaliningrad) shahridagi yetti ko'prikni qanday qilib bir ko'prikga ikki marta chiqmasdan bosib o'tish - qadimiy matematik masalalardan biri bo'lib, birinchi marta 1736-yilda Leonard Eyler tomonidan yechilgan. Eyler har bir ko'prikdan faqat bir marta foydalanib barcha

Noyabr 11, 2020by Sherzod Shermukhamedov

Graph'dagi aylanalarni topish

Graph'da aylana (cycle) nimaligi haqida graph atamalarida tushuntirilgan. Bir graph'da aylanalar bir necha bo'lishi mumkin.

Noyabr 9, 2020by Sherzod Shermukhamedov

Graph masalalari. Bipartite graph

Agar graph'ning har bir vertex'i qarama-qarshi tomondagi vertex'ga bog'lanuvchi ikki subset'ga (qismga) ajraladigan bo'lsa, demak graph - bipartite bo'ladi.

Noyabr 8, 2020by Sherzod Shermukhamedov

Graph'da bog'langan komponentlar

Bog'langan komponentlar (Connected components, CC) deb graphdagi bir-biriga tog'ridan to'g'ri yoki oradagi vertex'lar orqali bog'langan komponentlar to'plamiga aytiladi. Amaliyotda agar ikki vertex orasida path bo'lsa, biz ularni bog'langan deb ayta olamiz.

Noyabr 7, 2020by Sherzod Shermukhamedov

Breadth first search algoritmi

Breadth first search (BFS) algoritmi graph'ning barcha vertex'larini ko'rib chiqishning yana bir yo'li bo'lib, u rekursiv algoritm hisoblanmaydi. BFS Depth first search algoritmidan farqli ravishda queue ishlatadi (DFS - stack'dan foydalanardi).

Noyabr 6, 2020by Sherzod Shermukhamedov

Depth first search algoritmi

Depth first search (DFS) algoritmi oson klassik graph algoritmlaridan biri bo'lib, u rekursiya ichida graph'dagi barcha vertex'larni tekshirib chiqishga yordam beradi. Aslida biz bu algoritmdan binary search tree'dagi barcha ma'lumotlarni ko'rib chiqish uchun foydalanib, traverse() funksiyasini yozg

Noyabr 4, 2020by Sherzod Shermukhamedov

Graph'ni kodda ifodalash. Graph API

Graph ma'lumotlar tuzilmasini kodda ifodalashning bir necha usullari bor. Amaliyotda qo'yiladigan masalaga qarab usullardan biri tanlanadi.

Noyabr 3, 2020by Sherzod Shermukhamedov

Graph ma'lumotlar tuzilmasi

Biz chiziqli bo’lmagan ma’lumotlar tuzilmasini o’rganishni boshlaganimizda, ularning bazaviy xarakteristikasini ko’rib chiqqandik: tuzilmadagi ma’lumotlar qandaydir tartibga ega emas (hech bo’lmaganda sanoq tartibiga ega emas).