Претрага у ширину
Претрага у ширину (BFS; енгл. Breadth-first search) је алгоритам за претраживање или кретање кроз стабло или граф структуру података. Почиње из произвољног задатог чвора r који се означава као посећен и додаје као једини елемент реда. Потом се понављају следећи кораци, док год ред не постане празан: чвор са почетка реда се брише и сваки непосећени сусед овог чвора се означава као посећен и додаје на крај реда.
Псеудокод
Идеја: Код BFS претраге када се стигне до неког чвора x графа G, најпре се обилазе његови непосећени и непосредни суседи.
Након тога се наставља BFS алгоритам, тј. посећују се сви непосећени суседи из претходног нивоа претраге. Због тога се користи FIFO ред.[1]
Скица решења:
- Полазни чвор x графа G.
- Смести се у ред.
- Посети се.
- Означи се као посећен.
- Упишу се суседи чворова x на крај реда.
- Посети се следећи чвор из реда, означи као посећен, његови непосећени суседи се упишу на крај реда.
- Понавља се корак 2 док има непосећених чворова у реду.[2]
1 /* a = матрица суседства, n= број чворова графа G */
2 void BFS (int a[][50], int n )
3 {
4 int x; /* чвор графа */
5 int m[50]; /* 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 [][50], int n, int m[] )
19 {
20 int i, k; /* бројачи у циклусу */
21 int v; /* чвор графа */
22 int red[50]; /* низ чворова графа поређаних у поретку BFS претраге */
23 /*иницијализација низа m, ред у односу на полазну чвор претраге s */
24 m[s] = 1;
25 red[0] = 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 }
Сложеност
Свака грана прегледа се тачно два пута, једном са сваког краја. Према томе, временска сложеност је пропорционална броју грана. С друге стране, број рекурзивних покретања алгоритма је 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.
Спољашње везе
|
|