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