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.

Działanie algorytmu

Załóżmy, że zaczynamy przeszukiwanie od wierzchołka numer 1. 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:

$$1\ 2\ 5\ 9$$

• następnie opuszczamy wierzchołek numer 1 usuwając go jednocześnie z kolejki:

$$2\ 5\ 9$$

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

$$2\ 5\ 9\ 3\ 4$$

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

$$ 5\ 9\ 3\ 4\ 6\ 7\ 8$$

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

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 $$O(n + p)$$, 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:

10 11
1 2
2 3
3 4
2 4
1 5
1 9
9 10
5 6
5 7
5 8
8 10

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:

10 11
1 2
2 3
3 4
2 4
1 5
1 9
9 10
5 6
5 7
5 8
8 10
1 7

Wyjście:

2

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;
}