Обилазак графа

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

Проблем обиласка графа

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

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

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

Грана стабла (u,v) је она грана преко које се први пут током обиласка открива и посећује чвор v, чвор v је директни следбеник чвора u у стаблу обиласка.
Директна грана (u,v) је она грана где је чвор v следбеник, али не директни чвора u у стаблу обиласка.
Повратна грана (u,v) је она грана где је чвор v претходник чвора u у стаблу обиласка.
Попречна грана (u,v) је она грана где u и v нису у директној линији наслеђивања у стаблу обиласка. Ова грана мора бити усмерена здесна улево, те отуд и назив грана улево.

За DFS стабло неусмереног графа, пак важи: гране повезаног неусмереног графа не могу бити бити попречне за DFS стабло, тј. не могу повезивати чворове на различитим путевима од корена. Код неусмереног графа повратне и директне гране се поклапају јер нису усмерене.

Може се показати да је усмерени граф ацикличан ако и само ако DFS стабло нема повратних грана.

Алгоритми за обилазак графа

Алгоритми обиласка графа се разликују по правилу избора наредног чвора за обилазак. Два основна алгоритма су:

Обилазак у дубину (DFS)

Обилазак започиње из произвољног задатог чвора r, корена претраге у дубину. Корен се означава као посећен. Затим се бира произвољни неозначени чвор r1, суседан са r, па се из чвора r1 рекурзивно стартује претрага у дубину. Из неког нивоа рекурзије излази се кад се наиђе на чвор v коме су сви суседи (ако их има) већ означени. Ако су у тренутку завршетка претраге из r1, сви суседи чвора r означени, онда се претрага за чвор r завршава. У противном, бира се следећи произвољни неозначени сусед r2 чвора r, извршава се претрага полазећи од r2, итд. Претрага графа увек се врши са неким циљем. Да би се различите апликације уклопиле у претрагу у дубину, посећивању чвора или гране придружују се две врсте обраде:

улазна обрада,
излазна обрада.

Улазна обрада врши се у тренутку означавања чвора. Излазна обрада врши се после повратка неком граном, или кад се открије да нека грана води већ означеном чвору. Улазна и излазна обрада зависе од конкретне примене DFS.

Псеудокод

Улаз: G = (V,E) (усмерени повезани граф) и v (чвор графа G).

Излаз: зависи од примене.

 1    Алгоритам DFS(G, v);
 2    begin
 3        означи v;
 4        изврши улазну обраду на v; //улазна обрада зависи од примене -{DFS}-
 5        for све гране (v,w) do
 6            if w је неозначен then
 7                DFS(G,w); //Нови рекурзивни позив
 8            изврши излазну обраду за (v,w); //излазна обрада зависи од примене -{DFS}-
 9     //она се понекад врши само за гране ка новоозначеним чворовима
 10    end

Редослед обиласка чворова није јединствен. Да би био јединствен, потребно је увести додатно правило да се међу суседима бира чвор са најмањом вредношћу (слово најближе почетку азбуке или абецеде).

Обилазак у ширину (BFS)

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

Псеудокод

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

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

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

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