grafda o`tish bo`yi bo`yicha gfs algoritmi

DOCX 22 стр. 221,9 КБ Бесплатная загрузка

22 стр.

FaylHub.uz

Скачать через Telegram

Размер 221,9 КБ

Тип файла DOCX

Страницы 22

Обновлено Дек 2025

Предварительный просмотр (5 стр.)

Прокрутите вниз 👇

1 / 22

grafda o`tish bo`yi bo`yicha gfs algoritmi reja floyd algoritmlari 2. haddan tashqari algoritmlar 3. graflar ustida amallar 4. xulosa 5. foydalanilgan adabiyotlar floyd algoritmlari ushbu algoritm ba'zan floyd-warshell algoritmi deb ataladi. floyd-warshell algoritmi 1962da robert floyd va stiven uorchell tomonidan ishlab chiqilgan graflarda algoritmdir. grafning barcha juftlari orasidagi eng qisqa yo'llarni topishga xizmat qiladi. floyd usuli to'g'ridan-to'g'ri qovurg'alarning ijobiy og'irliklari bo'lgan ustunda, har qanday elementar bo'lmagan (1 qovurg'asidan ko'prog'ini o'z ichiga olgan), eng qisqa yo'l boshqa eng qisqa yo'llardan iborat. ushbu algoritm dijkstra algoritmiga nisbatan ancha keng tarqalgan, chunki har qanday ikki ustun o'rtasida eng qisqa yo'llarnitopadi. floyd algoritmida eng qisqa yo'llarning uzunligi hisoblangan nxn matritsasi ishlatiladi. a[i,j] elementi, agar u erda chekka (i, j) bo'lsa,yakuniy qiymatga ega bo'lgan va aks holda abadiylikka teng bo'lgan j ning yuqori qismidan masofaga teng. floyd algoritmning asosiy g'oyasi. i, j, k ning uchta tepasi bor va ular orasidagi masofa belgilanadi. agar tengsizlik a[i,k]+a[k,j] …

2 / 22

agi natijalarni olamiz: keyingi qadamlar . qolgan cho’qqilar uchun algoritmning qadamini takrorlaymiz. bular mos ravishda 6, 4 va 5 uchlari bo’ladi. algoritmning bajarilishini yakunlash. algoritm boshqa cho’qqilarni qayta ishlash mumkin bo’lmaganda tugaydi. bu misolda barcha cho’qqilar chizilgan, lekin har qanday misolda shunday bo’ladi deb o’ylash xatodir - agar ularga etib bo’lmasa, ya’ni graf uzilgan bo’lsa, ba’zi cho’qqilar chizilmagan holda qolishi mumkin. algoritmning natijasi oxirgi rasmda ko’rinadi: 1 cho’qqidan 2 gacha bo’lgan eng qisqa yo’l 7, 3 gacha - 9, 4 - 20, 5 - 20, 6 – 11 bo’lishini ko’rishimiz mumkin. grafdagi ma’lum bir manba tuguniga ega bo’lgan algoritm bu tugun bilan har bir boshqa o’rtasidagi eng qisqa yo’lni topadi. bundan tashqari, bitta tugunning eng qisqa yo’llarini to’xtatish yo’li bilan bitta maqsadli tugunga maqsad tuguniga eng qisqa yo’l aniqlanganidan keyin algoritm aniqlandi. masalan, agar graf tugunlari shaharlarni ifodalasa va chekka xarajatlari to’g’ridan-to’g’ri yo’l bilan bog’langan shaharlarning juftliklari o’rtasidagi masofani ifodalaydi …

3 / 22

$ude using namespace std; int minidist(int distance[], bool tset[]) // minimal masofani topish { int minimum=int_max,ind; for(int k=0;k<6;k++) { if(tset[k]==false && distance[k]<=minimum) { minimum=distance[k]; ind=k; } } return ind; } void dijkstraalgo(int graph[6][6],int src) // qo’shnilik matritsasi { int distance [6]; // har bir tugun uchun minimal masofani hisoblash uchun massiv bool tset[6];// har bir tugun uchun tashrif buyurilgan va tashrif buyurilmagan belgilash uchun mantiqiy massiv for(int k = 0; k<6; k++) { distance[k] = int_max; tset[k] = false; } distance[src] = 0; // manba tepasi masofasi 0 ga o’rnatiladi for(int k = 0; k<6; k++) { int m=minidist(distance,tset); tset[m]=true; for(int k = 0; k<6; k++) { // qo’shni vertex masofasini yangilash if (!tset [k] && graph[m][k] && distance[m]!=int_max && distance[m]+graph[m][k]<distance[k]) distance[k]=distance[m]+graph[m][k]; } } cout<<" vertex\t\tmanba cho’qqisidan masofa "<<endl; for(int k = 0; k<6; k++) { char str=65+k; cout<<str<<"\t\t\t"<<distance[k]<<endl; } } int main() { int graph[6][6]={ {0, 1, 2, 0, …$

4 / 22

biri sifatida grafdan uchni olib tashlash amalini keltirsa bo‘ladi. bu amalni qo‘llash berilgan grafning uchlari to‘plamidan birorta element yo‘qotishni (olib tashlashni) anglatadi. natijada uchlari soni bittaga kamaygan yangi graf hosil bo‘ladi. albatta, bu amalni uchlari soni ikkitadan kam bo‘lmagan graflar uchun qo‘llash mumkin bo‘lib, uni bajarish jarayonida olib tashlanayotgan uch bilan birgalikda shu uchga insident bo‘lgan barcha qirralar (yoylar) ham olib tashlanadi. eng sodda amallar qatoriga grafdan qirrani (yoyni) olib tashlash amalini ham kiritish mumkin. bu amalga ko‘ra berilgan grafning qirralari (yoylari) to‘plamidan birorta element yo‘qotiladi (olib tashlanadi). berilgan grafdan qirrani (yoyni) olib tashlayotganda shu qirraga (yoyga) insident uchlarni grafda qoldirish ham yo‘qotish ham mumkin. bu yerda vaziyatga qarab ish yuritiladi. agar g graf karrali qirralarga ega bo‘lmasa, u holda uchlari g grafning barcha uchlaridan iborat bo‘lgan shunday yagona g graf mavjudki, g grafdagi barcha juft uchlar faqat va faqat g grafda qo‘shni bo‘lmagandagina qo‘shnidir. bunday g graf berilgan g …

5 / 22

ikkita qirralar: v va v1 uchlariga insedent u1 qirra hamda v va v2 uchlariga insedent qirra qo’shiladi. teorema.agargrafdagiharbiruchninglokaldarajasiikkidankichik bo‘lmasa, u holda bu graf siklgaega. grafning bog‘lamliligi tushunchasi. agar oriyentirlanmagan grafda chetlari a va b uchlardan iborat marshrut topilsa, bu a vab uchlar bog‘langan deb, marshrutning o‘zi esa a va b uchlarni bog‘lovchi marshrut deb ataladi. tabiiyki, agar qandaydir uchlarni bog‘lovchimarshrutbirorai uchdanbir necha marta o‘tsa,uholdamarshrutningsiklikqisminiolibtashlab(bundasiklik qismning o‘rniga marshrutda faqat ai uch qoldiriladi) yana o‘shauchlarni bog‘lovchi oddiy zanjir ko‘rinishdagi marshrutni hosil qilish mumkin. shuning uchun, marshrut bilan bog‘langan uchlar doimo oddiy zanjir bilan ham bo‘glangan bo‘ladi degan xulosagakelamiz. bir-biri bilan ustma-ust tushmaydigan ixtiyoriy ikkita uchlari bog‘langan graf agar grafdagi ikkita uchni biror oddiy zanjir bilan tutashtirish mumkin bo‘lsa, u holda bu ikkita uch ekvivalent (bog‘langan) deyiladi. bunday uchlar to‘plami grafda ekvivalentlik munosabati bilan aniqlangan deb hisoblanadi. uchlar to‘plami bo‘yicha ekvivalentlik munosabatini inobatga olgan holda berilgan grafni bog‘lamlilik komponentalari (qisqacha, komponentalari) deb ataluvchi …

Хотите читать дальше?

Скачайте все 22 страниц бесплатно через Telegram.

Скачать полный файл

О "grafda o`tish bo`yi bo`yicha gfs algoritmi"

grafda o`tish bo`yi bo`yicha gfs algoritmi reja floyd algoritmlari 2. haddan tashqari algoritmlar 3. graflar ustida amallar 4. xulosa 5. foydalanilgan adabiyotlar floyd algoritmlari ushbu algoritm ba'zan floyd-warshell algoritmi deb ataladi. floyd-warshell algoritmi 1962da robert floyd va stiven uorchell tomonidan ishlab chiqilgan graflarda algoritmdir. grafning barcha juftlari orasidagi eng qisqa yo'llarni topishga xizmat qiladi. floyd usuli to'g'ridan-to'g'ri qovurg'alarning ijobiy og'irliklari bo'lgan ustunda, har qanday elementar bo'lmagan (1 qovurg'asidan ko'prog'ini o'z ichiga olgan), eng qisqa yo'l boshqa eng qisqa yo'llardan iborat. ushbu algoritm dijkstra algoritmiga nisbatan ancha keng tarqalgan, chunki har qanday ikki ustun o'rtasida eng qisqa yo'llarnitopadi. floyd algoritmida ...

Этот файл содержит 22 стр. в формате DOCX (221,9 КБ). Чтобы скачать "grafda o`tish bo`yi bo`yicha gfs algoritmi", нажмите кнопку Telegram слева.

Теги: grafda o`tish bo`yi bo`yicha gf… DOCX 22 стр. Бесплатная загрузка Telegram