Pretraga u širinu

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

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.

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.

    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

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

• Topološko sortiranje.
• Minimalno povezujuće stablo.
• Transportne mreže.
• Uparivanje, Hopkroft-Karp algoritam.
• Tranzitivno zatvorenje.
• Najkraći putevi iz datog čvora, Dajkstrin algoritam.
• Svi najkraći putevi, Flojd-Voršalov algoritam.
• Pronalaženje artikulacionih tačaka.
• Pronalaženje mostova.

Literatura

• 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

• Breadth-First Explanation and Example