DFS i DFS dla grida

DFS

Do czego służy?

Algorytm DFS (przeszukiwanie grafu w głąb) polega na przejściu całego grafu (tzn tam gdzie się da dostać z danego miejsca). Takie przejście jest podstawą do wielu bardziej skomplikowanych algorytmów. (np. funkcja low).

Algorytm

Algorytm DFS polega na najpierw przechodzeniu do nieodwiedzonych sąsiadów jak najdalej się da. Jak już jesteśmy w wierzchołku, gdzie nie ma nieodwiedzonych sąsiadów, to cofamy się do poprzedniego wierzchołka i kontynuujemy. Czyli tak bardziej schematycznie:
Jeśli mamy nieodwiedzonego sąsiada, to do niego idziemy
Jeśli nie mamy nieodwiedzonego sąsiada, to cofamy się do poprzedniego wierzchołka

Przykład

Zasymulujmy algorytm DFS (zaczynając od wierzchołka 1) dla przykładowego grafu:
Z wierzchołka 1 przechodzimy do jednego z jego nieodwiedzonych sąsiadów, czyli wierzchołka 2.
Z wierzchołka 2 przechodzimy do jednego z jego nieodwiedzonych sąsiadów, czyli wierzchołka 4.
Wierzchołek 4 nie ma nieodwiedzonych sąsiadów, więc cofamy się do wierzchołka 2.
Wierzchołek 2 nie ma nieodwiedzonych sąsiadów, więc cofamy się do wierzchołka 1.
Z wierzchołka 1 przechodzimy do jednego z jego nieodwiedzonych sąsiadów, czyli wierzchołka 3.
Z wierzchołka 3 przechodzimy do jednego z jego nieodwiedzonych sąsiadów, czyli wierzchołka 5.
Z wierzchołka 5 przechodzimy do jednego z jego nieodwiedzonych sąsiadów, czyli wierzchołka 8.
Wierzchołek 8 nie ma nieodwiedzonych sąsiadów, więc cofamy się do wierzchołka 5.
Wierzchołek 5 nie ma nieodwiedzonych sąsiadów, więc cofamy się do wierzchołka 3.
Z wierzchołka 3 przechodzimy do jednego z jego nieodwiedzonych sąsiadów, czyli wierzchołka 6.
Wierzchołek 6 nie ma nieodwiedzonych sąsiadów, więc cofamy się do wierzchołka 3.
Z wierzchołka 3 przechodzimy do jednego z jego nieodwiedzonych sąsiadów, czyli wierzchołka 7.
Wierzchołek 7 nie ma nieodwiedzonych sąsiadów, więc cofamy się do wierzchołka 3.
Wierzchołek 3 nie ma nieodwiedzonych sąsiadów, więc cofamy się do wierzchołka 1.
Wierzchołek 1 nie ma nieodwiedzonych sąsiadów, więc kończymy nasz algorytm.

implementacja i złożoność

implementacja w c++:

const int MAXI = 500007;
bool odwiedzone[MAXI];
vector <int> graf[MAXI];

void dfs(int w){
int i;
odwiedzone[w] = true;
for(i = 0; i < graf[w].size(); i++){
if(odwiedzone[graf[w][i]] == false){
dfs(graf[w][i]);
}
}
}

implementacja w python:

n = 500007
graf = [[] for i in range(n)]
odw = [False for i in range(n)]

def dfs(w):
odw[w] = True
for i in range(len(graf[w])):
if(odw[graf[w][i]] == False):
dfs(graf[w][i])

złożoność:

O(n+m)

Zadania

Preorder i postorder

Preorder i postorder to technika często wykorzystywana w zadaniach. Polega ona na zapisywaniu w którym momencie weszliśmy do danego wierzchołka i w którym momencie z niego wyszliśmy. Umożliwia nam np. ocenienie czy wierzchołek a znajduje się w poddrzewie wierzchołka b.

DFS dla grida

Do czego służy?

Algorytm DFS dla grida polega na przejściu całego grida (tzn tam gdzie się da dostać z danego miejsca). Takie przejście może być podstawą do wielu bardziej skomplikowanych algorytmów.

Algorytm

Algorytm DFS dla grida polega dokładnie na tym samym co zwykły algorytm DFS, tylko że zamiast grafu mamy prostokątną planszę. Wierzchołkami będą komórki grida, a krawędziami ścianki pomiędzy komórkami. Jeśli chcemy, możemy też niektóre ścianki bądź komórki blokować, trzeba będzie tylko odpowiednio podifować w kodzie. Poniżej (w przykładzie i kodzie) przedstawiam wersję bez blokad.

Przykład

Zasymulujmy algorytm DFS dla grida dla grida o wymiarach 3x2 (zaczynając w komórce 1 1):

	1	2	3
1
2

Z komórki 1 1 przechodzimy do jednego z jej sąsiadów (nieodwiedzonych), czyli do 1 2.
Z 1 2 przechodzimy do jednego z nieodwiedzonych sąsiadów 1 2, czyli do 2 2.
Z 2 2 przechodzimy do jednego z nieodwiedzonych jego sąsiadów, czyli 2 1.
Z 2 1 przechodzimy do jednego z nieodwiedzonych jego sąsiadów, czyli 3 1.
Z 3 1 przechodzimy do jednego z nieodwiedzonych jego sąsiadów, czyli 3 2.
3 2 nie ma nieodwiedzonych sąsiadów, więc cofamy się do 3 1.
3 1 nie ma nieodwiedzonych sąsiadów, więc cofamy się do 2 1.
2 1 nie ma nieodwiedzonych sąsiadów, więc cofamy się do 2 2.
2 2 nie ma nieodwiedzonych sąsiadów, więc cofamy się do 1 2.
1 2 nie ma nieodwiedzonych sąsiadów, więc cofamy się do 1 1.
1 1 nie ma nieodwiedzonych sąsiadów, więc kończymy nasz algorytm.

implementacja i złożoność

implementacja w c++:

const int MAXI = 1007;
bool odw[MAXI][MAXI];
int dx[] = {0, 0, -1, 1}, dy[] = {1, -1, 0, 0};
int n, m;

void dfs_grif(int v, int w){
int i;
odw[v][w] = true;
for(i = 0; i < 4; i++){
pair <int, int> sasiad = make_pair(v + dx[i], w + dy[i]);
if(1 <=sasiad.first && sasiad.first <=n &&
1 <=sasiad.second && sasiad.second <=m ) {
if(odw[sasiad.first][sasiad.second] == false) {
odw[sasiad.firt][sasiad.second] = true;
dfs_grid(sasiad.first, sasiad.second);
}
}
}
}

implementacja w python:

odw = [[False for i in range(1007)] for i in range(1007)]
dx = [0, 0, -1, 1]
dy = [1, -1, 0, 0]
n = 0
m = 0

def dfs_grid(v, w):
odw[v][w] = True
for i in range(4):
sasiadx = v + dx[i]
sasiady = w + dy[i]
if(1 <= sasiadx and sasiadx <=n and
1 <= sasiady and sasiady <=m ):
if(odw[sasiadx][sasiady] == False):
odw[sasiadx][sasiady] = True
dfs_grid(sasiadx, sasiady)

złożoność:

O(n*m)