Претрага у ширину (BFS; ) је алгоритам за претраживање или кретање кроз стабло или граф структуру података. Почиње из произвољног задатог чвора -{r}- који се означава као посећен и додаје као једини елемент реда. Потом се понављају следећи кораци, док год ред не постане празан: чвор са почетка реда се брише и сваки непосећени сусед овог чвора се означава као посећен и додаје на крај реда.
Псеудокод Идеја: Код -{BFS}- претраге када се стигне до неког чвора -{x}- графа -{G}-, најпре се обилазе његови непосећени и непосредни суседи. Након тога се наставља -{BFS}- алгоритам, тј. посећују се сви непосећени суседи из претходног нивоа претраге. Због тога се користи FIFO ред.
Скица решења: Полазни чвор -{x}- графа -{G}-. Смести се у ред. Посети се. Означи се као посећен. Упишу се суседи чворова -{x}- на крај реда. Посети се следећи чвор из реда, означи као посећен, његови непосећени суседи се упишу на крај реда. Понавља се корак 2 док има непосећених чворова у реду. 1 /* a = матрица суседства, n= број чворова графа G */ 2 void BFS (int a[], int n ) 3 { 4 int x; /* чвор графа */ 5 int m; /* m је низ означених чворова графа */ 6 /* иницијализација низа означених чворова на 0, јер су на почетку сви непосећени */ 7 for (x = 0 ; x < n ; x++ ) 8 m[x] = 0; 9 /* посета графа почев од првог непосећеног чвора */ 10 for (x = 0 ; x < n ; x++ ) 11 if (!m[x] ) 12 poseti (x, a, n, m ) 13 } 14 /* s = пролази чвор претраге по ширини, a = матрица суседства */ 15 /* n = број чворова графа, m = низ посећених чворова */ 16 17 18 void poseti(int s, int a [], int n, int m[] ) 19 { 20 int i, k; /* бројачи у циклусу */ 21 int v; /* чвор графа */ 22 int red; /* низ чворова графа поређаних у поретку BFS претраге */ 23 /*иницијализација низа m, ред у односу на полазну чвор претраге s */ 24 m[s] = 1; 25 red = s; 26 k = 1; 27 /* обилазак непосредних суседа чвора s, разлика од DFSа */ 28 for (i = 0 ; i < k ; i++ ) 29 { 30 s = red[i]; 31 for (v = 0 ; v < n ; v++ ) 32 if(!m[v] && a[s][v] ) 33 { 34 m[v] = 1; 35 red[k++] = v; 36 } 37 } 38 /*испис -{BFS}- поретка*/ 39 for (i = 0 ; i < k ; i++ ) 40 printf("%d" , red[i] ); 41 }
</code>
Сложеност Свака грана прегледа се тачно два пута, једном са сваког краја. Према томе, временска сложеност је пропорционална броју грана. С друге стране, број рекурзивних покретања алгоритма је -{V}-, па се сложеност алгоритма може описати изразом -{O(|V|+|E|)}-. Ако је коришћено матрично представљање, имамо временску сложеност од -{O(|V|²)}-, а уколико је коришћено уланчано представљање, сложеност је -{O(|V|+|E|)}-. Уланчано представљање даје боље временске перформансе.
Проблеми који се решавају обиласком графа Тополошко сортирање. Минимално повезујуће стабло. Транспортне мреже. Упаривање, Хопкрофт-Карп алгоритам. Транзитивно затворење. Најкраћи путеви из датог чвора, Дајкстрин алгоритам. Сви најкраћи путеви, Флојд-Воршалов алгоритам. Проналажење артикулационих тачака. Проналажење мостова.
Референце
Литература
Алгоритми, професор Миодраг Живковић, МАТФ, Beograd 2001. година. -{Beginning Algorithms, Simon Harris and James Ross, published 2006. by Wiley Publishing, Inc., Indianapolis, Indiana.}- -{How to Think About Algorithms, Jeff Edmonds, published 2008. by Cambridge University Press, New York.}- -{ Coding Theory Algorithms, Architectures, and Applications, Andre Neubauer, Volker Kuhn, Jurgen Freudenberger, published 2007. by John Wiley & Sons Ltd, The Atrium, Southern Gate, Chichester, West Sussex PO19 8SQ, England.}- -{Elementary Functions Algorithms and Implementation Second Edition, Jean-Michel Muller, publised 2006 by Birkhauser Boston.}- -{Introduction to Algorithms Second Edition, Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein, published 2001. by The Massachusetts Institute of Technology.}-
Спољашње везе
Breadth-First Explanation and Example
Категорија:Графовски алгоритми