Przeszukiwanie wszerz

Kurs C++

Matura z informatyki

KONKURS FRAKTAL

VII edycja konkursu programistycznego

FRAKTAL

8-9 kwietnia 2017

czytaj więcej

Ćwiczenia

Warsztaty

Logowanie

Przeszukiwanie wszerz (BFS)

powrót

W tym artykule zajmiemy się przeszukiwaniem grafu wszerz nazywanym w skrócie BFS (ang. Breadth-first search). Jest to drugi, zupełnie inny sposób przeszukiwania grafu. Do realizacji tego algorytmu wykorzystujemy kolejkę fifo. Zasada działania jest bardzo prosta i przyjemna w implementacji. Przeanalizujmy działanie na grafie przedstawionym poniżej.

przeszukiwanie wszerz

Działanie algorytmu

Załóżmy, że zaczynamy przeszukiwanie od wierzchołka numer {tex}1{/tex}. Wrzucamy go do kolejki i postępujemy z zasadą:

wrzucamy do kolejki wszystkie wierzchołki, które są z nim połączone. Kolejka teraz wygląda następująco:

{tex}1\ 2\ 5\ 9{/tex}

następnie opuszczamy wierzchołek numer {tex}1{/tex} usuwając go jednocześnie z kolejki:

{tex}2\ 5\ 9{/tex}

teraz pobieramy następny element z kolejki - jest to wierzchołek numer {tex}2{/tex}
dodajemy wszystkie nieodwiedzone połączenia tego wierzchołka do kolejki, a więc wierzchołek {tex}3{/tex} i {tex}4{/tex}:

{tex}2\ 5\ 9\ 3\ 4{/tex}

wychodzimy z wierzchołka {tex}2{/tex} usuwając go z kolejki i pobieramy następny jej element: {tex}5{/tex} oraz wrzucamy do kolejki wszystkie nieodwiedzone połączenia z tym wierzchołkiem:

{tex} 5\ 9\ 3\ 4\ 6\ 7\ 8{/tex}

czynności te powtarzamy do momentu przejścia całego grafu:

bfs

Odwiedzenie wszystkich wierzchołków zakończy się w momencie, gdy kolejka będzie pusta. Przejście przez cały graf (odwiedzenie wszystkich wierzchołków) ma złożoność liniową, a dokładnie {tex}O(n + p){/tex}, gdzie n to liczba wierzchołków, natomiast p to liczba połączeń.

Iteracyjna implementacja przeszukiwania BFS:

//www.algorytm.edu.pl
#include<iostream>
#include<queue>
using namespace std;
 
struct graf{
  bool kolejka; //czy dodany do kolejki
 
  vector <int> polaczenia; //do przechowywania połączeń
  // dodatkowe opcje
}*w; 
 
void odwiedz(int n)
{
  //wykonaj jakies czynnosci
  //w przypadku odwiedzenia wierzcholka o numerze n
  cout<<"Odwiedzono wierzchołek o numerze: "<<n<<endl;
}
 
void BFS(int n)
{
  queue<int> kolejka;    //utworzenie kolejki fifo
  kolejka.push(n);  //dodanie pierwszego wierzcholka do kolejki
 
  while(!kolejka.empty()) //dopóki jest cos w kolejce
  {
    n = kolejka.front(); //pobranie pierwszego elementu w kolejce
 
      kolejka.pop(); //usuń pobrany element z kolejki
      odwiedz(n); //odwiedź go i zrób coś
      //oraz dodaj wszystkie jego nieodwiedzone i nie będące 
      //w kolejce połączenia do kolejki
      for(int i=0;i<w[n].polaczenia.size();i++)
        if(!w[w[n].polaczenia[i]].kolejka)
        {
          kolejka.push(w[n].polaczenia[i]);
          w[w[n].polaczenia[i]].kolejka = 1; //oznaczenie, że dodano do kolejki
          cout<<"Dodano do kolejki wierzcholek nr "<<w[n].polaczenia[i]<<endl;
        }
  }   
}
 
int main()
{
  cout<<"Podaj liczbę wierzchołków w grafie: ";
  int n, p, a, b;
  cin>>n;
  w = new graf [n+1];//przydzielenie pamięci na wierzchołki grafu
  //wczytanie wierzchołków grafu
  cout<<"Podaj liczbę połączeń: ";
  cin>>p;
 
  for(int i=0;i<p;i++)
  {
    cout<<"Podaj numery wierzchołków, które chcesz ze sobą połączyć: ";
    cin>>a>>b;
    w[a].polaczenia.push_back(b); //połączenie jest dwukierunkowe a-->b
    w[b].polaczenia.push_back(a); //b-->a
  }
  //przeszukaj graf
  BFS(1); //rozpoczynamy od wierzchołka o numerze 1
 
  delete [] w;
  return 0;
}

Wejście:

Wyjście (pominięto tekst pomocniczy):

Odwiedzono wierzchołek o numerze: 1
Dodano do kolejki wierzcholek nr 2
Dodano do kolejki wierzcholek nr 5
Dodano do kolejki wierzcholek nr 9
Odwiedzono wierzchołek o numerze: 2
Dodano do kolejki wierzcholek nr 3
Dodano do kolejki wierzcholek nr 4
Odwiedzono wierzchołek o numerze: 5
Dodano do kolejki wierzcholek nr 6
Dodano do kolejki wierzcholek nr 7
Dodano do kolejki wierzcholek nr 8
Odwiedzono wierzchołek o numerze: 9
Dodano do kolejki wierzcholek nr 10
Odwiedzono wierzchołek o numerze: 3
Odwiedzono wierzchołek o numerze: 4
Odwiedzono wierzchołek o numerze: 6
Odwiedzono wierzchołek o numerze: 7
Odwiedzono wierzchołek o numerze: 8
Odwiedzono wierzchołek o numerze: 10

Przykładowe zadanie

Napisz program, który określi jaka jest najkrótsza droga między dwoma wierzchołkami grafu (mamy znaleźć minimalną liczbę wierzchołków, przez które należy przejść z wierzchołka A do wierzchołka B).

Wejście

W pierwszym wierszu podajemy dwie liczby n i p określające odpowiednio liczbę wierzchołków w grafie oraz liczbę połączeń między nimi (n < 1001, p < p ⋅p)

W kolejnych p wierszach po dwie różne liczby a i b definiujące połączenie tych wierzchołków.

Następnie dwie liczby A B, gdzie A, B zawiera się w przedziale [1..n] i oznaczające numer startowego i końcowego wierzchołka.

Wyjście

Jedna liczba określająca minimalną liczbę przejść z wierzchołka A do B lub napis "Brak polaczenia", jeśli połączenie nie istnieje.

Przykład

Wejście:

Wyjście:

Rozwiązanie

//wwww.algorytm.edu.pl
#include<iostream>
#include<queue>
using namespace std;
 
struct graf{
  bool kolejka; //czy dodany do kolejki
 
  vector <int> polaczenia; //do przechowywania połączeń
  int odleglosc;   //odleglosc od poczatku
}*w; 
 
void odwiedz(int n)
{
  //wykonaj jakies czynnosci
  //w przypadku odwiedzenia wierzcholka o numerze n
 
}
 
int BFS(int n, int koniec)
{
  queue<int> kolejka;    //utworzenie kolejki fifo
  kolejka.push(n);  //dodanie pierwszego wierzcholka do kolejki
 
  while(!kolejka.empty()) //dopóki jest cos w kolejce
  {
    n = kolejka.front(); //pobranie pierwszego elementu w kolejce
   if(n == koniec) return w[n].odleglosc; //zwrócenie najkrótszej drogi
      kolejka.pop(); //usuń pobrany element z kolejki
      odwiedz(n); //odwiedź go i zrób coś
      //oraz dodaj wszystkie jego nieodwiedzone i nie będące 
      //w kolejce połączenia do kolejki
      for(int i=0;i<w[n].polaczenia.size();i++)
        if(!w[w[n].polaczenia[i]].kolejka)
        {
          kolejka.push(w[n].polaczenia[i]);
          w[w[n].polaczenia[i]].kolejka = 1; //oznaczenie, że dodano do kolejki
          w[w[n].polaczenia[i]].odleglosc = w[n].odleglosc + 1;
        }
  }  
  return -1; //brak polaczenia miedzy poczatkiem i koncem 
}
 
int main()
{
    int n, p, a, b, koniec;
    cin>>n>>p;
    w = new graf [n+1];//przydzielenie pamięci na wierzchołki grafu
 
    //wczytanie wierzchołków grafu
    for(int i=0;i<p;i++)
    {
      cin>>a>>b;
      w[a].polaczenia.push_back(b); //połączenie jest dwukierunkowe a-->b
      w[b].polaczenia.push_back(a); //b-->a
    }
    cin>>n>>koniec; //wczytanie początkowego i końcowego wierzchołka
    //przeszukaj graf
    int wynik = BFS(n, koniec);
    if(wynik==-1)
      cout<<"Brak polaczenia\n";
  else
    cout<<wynik<<endl;
 
    delete [] w;
    return 0;
}

Programowanie i algorytmy