Pretraga u širinu

S Vikipedije, slobodne enciklopedije

Pretraga u širinu (BFS; engl. Breadth-first search) je algoritam za pretraživanje ili kretanje kroz stablo ili graf strukturu podataka. Počinje iz proizvoljnog zadatog čvora r koji se označava kao posećen i dodaje kao jedini element reda. Potom se ponavljaju sledeći koraci, dok god red ne postane prazan: čvor sa početka reda se briše i svaki neposećeni sused ovog čvora se označava kao posećen i dodaje na kraj reda.

Pseudokod[uredi | uredi izvor]

Ideja: Kod BFS pretrage kada se stigne do nekog čvora x grafa G, najpre se obilaze njegovi neposećeni i neposredni susedi. Nakon toga se nastavlja BFS algoritam, tj. posećuju se svi neposećeni susedi iz prethodnog nivoa pretrage. Zbog toga se koristi FIFO red.[1]

Skica rešenja:

  1. Polazni čvor x grafa G.
    • Smesti se u red.
    • Poseti se.
    • Označi se kao posećen.
    • Upišu se susedi čvorova x na kraj reda.
  2. Poseti se sledeći čvor iz reda, označi kao posećen, njegovi neposećeni susedi se upišu na kraj reda.
  3. Ponavlja se korak 2 dok ima neposećenih čvorova u redu.[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   }
    

Složenost[uredi | uredi izvor]

Svaka grana pregleda se tačno dva puta, jednom sa svakog kraja. Prema tome, vremenska složenost je proporcionalna broju grana. S druge strane, broj rekurzivnih pokretanja algoritma je V, pa se složenost algoritma može opisati izrazom O(|V|+|E|). Ako je korišćeno matrično predstavljanje, imamo vremensku složenost od O(|V|²), a ukoliko je korišćeno ulančano predstavljanje, složenost je O(|V|+|E|). Ulančano predstavljanje daje bolje vremenske performanse.

Problemi koji se rešavaju obilaskom grafa[uredi | uredi izvor]

Reference[uredi | uredi izvor]

  1. ^ „Škola koda | Pretraga u širinu”. skolakoda.org (na jeziku: srpski). Pristupljeno 2020-03-27. 
  2. ^ „Breadth First Search Tutorials & Notes | Algorithms”. HackerEarth (na jeziku: engleski). Pristupljeno 2020-03-27. 

Literatura[uredi | uredi izvor]

  • Algoritmi, profesor Miodrag Živković, MATF, Beograd 2001. godina.
  • 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.

Spoljašnje veze[uredi | uredi izvor]