: index | programowanie | webmastering | algorytmika | download | projekty | słownik | grafika | flash | linki :

a l g o r y t m y > grafy >

P R Z E S Z U K A N I E   G R A F U   W S Z E R Z   ( B F S )

 

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 29 30

 
       

Przeszukanie grafu wszerz (BFS) pozwala wyznaczyć najkrótsze z możliwych ścieżek od ustalonego wierzchołka grafu s do wszystkich pozostałych wierzchołków grafu - w wyniku dla każdego wierzchołka u otrzymujemy jedną ze wszystkich ścieżek s-...-u o najkrótszej długości. Jeśli pomiędzy wierzchołkami s oraz u istnieje kilka takich ścieżek, to o wyborze ścieżki decyduje kolejność przetwarzania następników poszczególnych wierzchołków ścieżki.
Dodatkowo dla każdego wierzchołka grafu u algorytm wyznacza jego głębokość g[u] w stosunku do wierzchołka początkowego s, czyli długość znalezione najkrótszej ścieżki s-...-u.

Przeszukanie wszerz wykonuje się przy pomocy kolejki, w której na początku umieszczamy wierzchołek startowy s. Każdemu składnikowi kolejki towarzyszy jego głębokość względem wierzchołka startowego s zapisana w tablicy głębokości g - ten pierwszy składnik kolejki, którym jest wierzchołek s zapisujemy z głębokością 0.
Algotytm musi mieć możliwość sprawdzania, dla których wierzchołków grafu wyznaczona została już najkrótsza ścieżka i jej długość. Odbywa się to przy pomocy tzw. kolorowania grafu. Do kolorowania używamy trzech barw:

  • czarnej, gdy następuje odwiedzenie wierzchołka - w tym algorytmie ma to miejsce wówczas, gdy wierzchołek jest pierwszym składnikiem kolejki,

  • szarej, gdy wierzchołek jest dodawany do kolejki i oczekuje na odwiedzenie

  • białej, w pozostałych przypadkach, gdy jeszcze nic nie wiadomo o wierzchołku, na początku algorytmu

Barwy te zapisujemy w pewnej tablicy w postaci liczb, stałych lub typu wyliczeniowego - tutaj będzie to tablica b. Odkładając do kolejki wierzchołek startowy s kolorujemy go na szaro.

Podczas przeszukiwania w tablicy d zapisujemy poprzedniki odwiedzanych wierzchołków. Jeśli podczas analizy wierzchołka u stwierdzimy, że jego następnikiem jest wierzchołek v, który nie został jeszcze odwiedzony (jest biały), to w tablicy d w miejscu v wpisujemy poprzednik u (d[v]:=u), przyjmując tym samym, że ścieżka do wierzchołka v prowadzić będzie przez wierzchołek u.
Na początku, gdy kolejka zawiera tylko jeden wierzchołek s wygląda to tak:

  • dla każdego białego następnika v wierzchołka s:

    • dodaj następnik v do kolejki,

    • pokoloruj go na szaro,

    • w tablicy g zapisz długość ścieżki o jeden większą niż długość ścieżki do wierzchołka s (g[v]:=g[s]+1), czyli w zasadzie 1, bo g[s]=0,

    • w tablicy ścieżek d wpisz poprzednik wierzchołka v równy s, czyli d[v]:=s,

  • usuń z kolejki składnik początkowy s i pokoloruj go na czarno.

Taką iterację należy powtarzać dopóty, aż kolejka będzie pusta. Każdy wierzchołek grafu dodawany jest do kolejki co najwyżej raz, maksymalny rozmiar kolejki może być równy maksymalnej ilości wierzchołków w grafie.

 

DANE:
  n - liczba wierzchołków grafu
  k - liczba krawędzi grafu
  s - wierzchołek startowy (tzw. źródło)
  a - graf skierowany lub nieskierowany - macierz sąsiedztwa
      a[i, j] = True, gdy istnieje krawędź (i, j)
WYNIK:
  tablica "g" głębokości wierzchołków grafu względem wierzchołka "s"
  tablica "d", w której zapisano najkrótsze ścieżki do wszystkich wierzchołków 
    d[i] - numer poprzednika wierzchołka o numerze "i"
    i-d[i]-d[d[i]]-d[d[d[i]]]-...-s - odwrócona najkrótsza ścieżka "s"-...-"i"

 

  1. Umieść w kolejce rekord zawierający numer ustalonego wierzchołka s, a także wpisz długość scieżki 0 do tablicy g

  2. Pokoloruj wierzchołek s na szaro

  3. Dopóki kolejka nie jest pusta wykonuj następujące czynności:

    • Dla każdego białego następnika v wierzchołka pierwszego w kolejce u:

      • dodaj wierzchołek v do kolejki i pokoloruj go na szaro

      • zapisz w tablicy dróg, że poprzednikiem wierzchołka v jest wierzchołek u

      • w tablicy głębokości g wierzchołkowi v wpisz długość ścieżki o 1 większą niż głębokość wierzchołka u

    • Usuń z kolejki pierwszy jej składnik u i pokoloruj go na czarno

Const
  MaxIloscWezlow = 1000;

Type
  TypWezla = Word;
  Kolory   = (bialy, szary, czarny);
  Barwy    = Array[1..MaxIloscWezlow] Of Kolory;

  Kolejka  = Array[0..MaxIloscWezlow-1] Of TypWezla;
  Graf     = Array[1..MaxIloscWezlow, 1..MaxIloscWezlow] Of Boolean;

Var
  i, j, t        : TypWezla;
  kol            : Kolejka;
  start, rozmiar : TypWezla;
  a              : Graf;
  b              : Barwy;
  d              : Array[1..MaxIloscWezlow] Of TypWezla;
  g              : Array[1..MaxIloscWezlow] Of TypWezla;
  n, k, s        : TypWezla;

Begin
  Write('Ilosc wierzcholkow = ');
  ReadLn(n);
  Write('Ilosc krawedzi = ');
  ReadLn(k);
  Write('Wierzcholek poczatkowy = ');
  ReadLn(s);

  {Inicjacja tablic}
  For i:=1 To n Do
    For j:=1 To n Do a[i, j]:=False;
  For i:=1 To n Do
    Begin
      d[i]:=0;
      g[i]:=0;
      b[i]:=bialy;
    End;

  {Wczytaj krawedzie}
  For t:=1 To k Do
    Begin
      ReadLn(i, j);
      a[i, j]:=True;
    End;

  {Umiesc w kolejce wierzcholek "s"}
  start:=0;
  rozmiar:=1;
  kol[start]:=s;
  b[s]:=szary;

  {Dopoki kolejka nie jest pusta}
  While rozmiar>0 Do
    Begin
      {Dla wszystkich następnikow wierzcholka pierwszego w kolejce }
      {Jezeli nastepnik nie byl jeszcze analizowany - jest "bialy" }
      For i:=1 To n Do
        If a[kol[start], i] And (b[i]=bialy) Then
          Begin
            {Umiesc nastepnik w kolejce}
            kol[start+rozmiar]:=i;
            rozmiar:=rozmiar+1;
            {Wezlowi "i" przypisz glebokosc}
            g[i]:=g[kol[start]]+1;
            {Wezlowi "i" przypisz poprzednik}
            d[i]:=kol[start];
            b[i]:=szary;
          End;
      {Usun poczatkowy skladnik z kolejki}
      b[kol[start]]:=czarny;
      start:=start+1;
      rozmiar:=rozmiar-1;
    End;

  WriteLn('Wierzcholek : Dlugosc sciezki : Odwrocona sciezka :');
  For i:=1 To n Do
    Begin
      Write(i, ' : ', g[i], ' : ');
      Write(i, ' ');
      j:=d[i];
      While j<>0 Do
        Begin
          Write(j, ' ');
          j:=d[j];
        End;
      WriteLn;
    End;
  ReadLn;
End.

Złożoność obliczeniowa: O(V+E).