Претрага у ширину

Из Википедије, слободне енциклопедије

У рачунарству, обилазак графа је проблем посете свих чворова у графу на одређени начин. Обилазак дрвета је посебан случај обиласка графа.

Обилазак у ширину почиње из произвољног задатог чвора r који се означава као посећен и додаје као једини елемент реда. Потом се понављају следећи кораци, док год ред не постане празан: обриши чвор са почетка реда и сваког непосећеног суседа овог чвора означи као посећен и додај га на крај реда.

Псеудокод[уреди]

Псеудокод BFS алгоритма за обилазак графа G=(V,E) који је задат матрицом повезаности тако да исписује чворове у редоследу обиласка:

Идеја: Код BFS претраге када се стигне до неког чвора x графа G, најпре се обилазе његови непосећени и непосредни суседи. Након тога се наставља BFS алгоритам, тј. посећују се сви непосећени суседи из претходног нивоа претраге. Због тога се користи FIFO (First InFirst Out) ред.

Скица решења:

  1. Полазни чвор x графа G.
    • Смести се у ред.
    • Посети се.
    • Маркира као посећен.
    • Упишу се суседи чворова x на крај реда.
  2. Посети се следећи чвор из реда, маркира као посећен, његови непосећени суседи се упишу на крај реда.
  3. Понавља се корак 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.

Спољашње везе[уреди]

Викиостава
Викимедијина остава има још мултимедијалних датотека везаних за: Претрага у ширину