Informatyka. Konkursy i algorytmy
tryb:

BFS i BFS dla grida

BFS

Do czego służy?

Algorytm BFS(przeszukiwanie wszerz) służy do znajdowania najkrótszej ścieżki z jednego wierzchołka do wszystkich w grafie nieważonym lub o jednakowych wagach. Pierwszym pomysłem na algorytm może być przejście po wszystkich ścieżkach, ale to jest oczywiście za wolne. Rozwiązaniem tego problemu jest algorytm BFS.

Algorytm

Algorytm BFS polega na podzieleniu grafu na warstwy w taki sposób, że numer warstwy odpowiada za odległość z wierzchołka startowego do wierzchołka z danej warstwy. Jak podzielić graf na warstwy? A bardzo prosto:
W warstwie zerowej jest wierzchołek startowy
W pierwszej warstwie są sąsiedzi wierzchołka startowego
W drugiej warstwie są jeszcze nieokreśleni sąsiedzi wierzchołków z warstwy pierwszej.
W x-tej warstwie są jeszcze niekreśleni sąsiedzi wierzchołków z warsty x-1.
Algorytm powtarzamy, aż żaden wierzchołek nie zostanie nam do rozpatrzenia.

Przykład

Zasymulujmy algorytm BFS dla takiego grafu(zaczynając od wierzchołka 1):
W warstwie zerowej, skoro zaczynamy od 1 będzie wierzchołek 1.
W warstie pierwszej będą sąsiedzi 1, czyli 2 3 i 5.
W warstie drugiej będą nieodwiedzeni jeszcze sąsiedzi 2 3 i 5, czyli 4 6 i 7.
W warstwie trzeciej będą nieodwiedzeni jeszcze sąsiedzi 4 6 i 7, czyli 8
Tutaj zauważamy, że odwiedziliśmy już wszystkie wierzchołki, więc kończymy algorytm.

implementacja i złożoność

implementacja w c++:
const int MAXI = 1e6 + 7;
vector <int> graf[MAXI];
bool odw[MAXI];
int odl[MAXI];

void bfs(int w){
queue <int> q;
q.push(w);
odw[w] = true;
while(q.size()){
w = q.front();
q.pop();
for(int i : graf[w]){
if(!odw[i]){
odw[i] = true;
odl[i] = odl[w] + 1;
q.push(i);
}
}
}
}

implementacja w python:
import collections
n = 1000007
graf = [[] for i in range(n)]
odw = [False for i in range(n)]
odl = [0 for i in range(n)]

def bfs(vpocz):
kolejka = collections.deque([vpocz])
odw[vpocz] = True
while(len(kolejka) > 0):
v = kolejka.popleft()
for i in range(0, len(graf[v])):
w = graf[v][i]
if(odw[w] == False):
odl[w] = odl[v] + 1
odw[w] = True
kolejka.append(w)

złożoność:
O(n+m)

Zadania

BFS dla grida

Do czego służy?

Algorytm BFS(przeszukiwanie wszerz) dla grida służy do znajdowania najkrótszej ścieżki z jednej komórki do wszystkich w gridzie. Pierwszym pomysłem na algorytm może być przejście po wszystkich ścieżkach, ale to jest oczywiście za wolne. Rozwiązaniem tego problemu jest algorytm BFS dla grida.

Algorytm

Algorytm BFS dla grida polega dokładnie na tym samym co zwykły algorytm BFS, tylko że zamiast grafu mamy prostokątną planszę - grida. Jako wierzchołki występują poszczególne komórki, a jako krawędzie - ścianki pomiędzy komórkami. Można niektóre ścianki/komórki zablokować, tylko trzeba będzie dodać odpowiednie ify 😉. Poniżej (w przykładzie i kodzie) przedstawiam wersję bez blokad ścianek i krawędzi.

Przykład

Zasymulujmy algorytm BFS dla grida dla grida o wymiarach 3x2 (zaczynając z komórki 1, 1).

123
1
2
W zerowej warstwie będzie komórka 1 1 (bo od niej zaczynamy)
W pierwszej warstwie będą sąsiedzi komórki 1 1, czyli 1 2 i 2 1
W drugiej warstwie będą sąsiedzi komórek 1 2 i 2 1, czyli komórki 1 3 i 2 2
W trzeciej warstwie będą sąsiedzi komórek 1 3 i 2 2, czyli komórka 3 2
Tutaj kończymy algorytm, ponieważ odwiedziliśmy już wszystkie komórki.
123
1012
2123

implementacja i złożoność

implementacja w c++:
const int MAXN = 1007;
bool odw[MAXN][MAXN];
int odl[MAXN][MAXN];
int dx[] = {0, 0, -1, 1}, dy[] = {1, -1, 0, 0};
int n, m;

void bfs_grid(){
queue <pair <int, int> > q;
q.push(make_pair(1,1));
odw[1][1] = true;
while(q.size() > 0) {
int wie = q.front().first;
int kol = q.front().second;
q.pop();
for(int i = 0; i < 4; i++) {
pair <int, int> sasiad = make_pair (wie + dx[i], kol + dy[i]);
if(1 <=sasiad.first && sasiad.first <=n &&
1 <=sasiad.second && sasiad.second <=m ) {
if(odw[sasiad.first][sasiad.second] == false){
odw[sasiad.first][sasiad.second] = true;
q.push(sasiad);
odl[sasiad.first][sasiad.second] = odl[wie][kol] + 1;
}
}
}
}
}

implementacja w python:
import collections
odw = [[False for i in range(1007)] for i in range(1007)]
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
odw = [[0 for i in range(1007)] for i in range(1007)]
n = 0
m = 0

def bfs_grid():
q = collecions.deque([])
q.append((1, 1))
odw[1][1] = True
while(len(q) > 0):
v = q.popleft()
for i in range(4):
w = (v[0] + dx[i], v[1] + dy[i])
if(1 <=w [0] and w[0] <=n and
1 <=w [1] and w[1] <=m ):
if(odw[w[0]][w[1]] == False):
odw[w[0]][w[1]] = True
q.append(w)
odl[w[0]][w[1]] = odl[v[0]][v[1]] + 1

złożoność:
O(n*m)

Zadania

Projekt realizowany na potrzeby stypendium mazowieckiego. © made by Zofia Mroziuk