# Zajęcia 17.02.2021 - DFS

###### tags: `Informatyka 1PR`

| Nr | Imię i nazwisko | Ocena |
| --- | --------------------- | ----- |
| 1 | Wojciech Romanowski | |
| 2 | Alicja Rosińska | |
| 3 | Jakub Zaszkodny | |
| 4 | Wojciech Reda | |
| 5 | Zuzanna Trzebiatowska | |
| 6 | Jan Sas | |
| 7 | Maciej Solecki | |
| 8 | Wojtek Rybak | |
| 9 | Konrad Sobczak | |
| 10 | Mikołaj Sczogiel | |
| 11 | Kamil Żmudziński | |
| 12 | Radek Pałys | |

$\texttt{DFS}$ (Depth First Search) jest kolejnym algorytmem przeszukiwania grafu. W algorytmie $\texttt{BFS}$ priorytetyzowaliśmy przetwarzanie wierzchołków, które zostały odwiedzone najwcześniej. $\texttt{DFS}$ w pewnym sensie robi dokładnie odwrotnie - priorytetyzuje przetworzenie wierzchołka, który został odwiedzony najpóźniej. Możliwą implementacją $\texttt{DFS'a}$ jest literalna podmiana kolejki na stos w implementacji $\texttt{BFS'a}$. Jednakże, dużo wygodniejszym i przyjętym sposobem jest użycie rekurencji. Oto najprostsza wersja algorytmu napisana w $\texttt{C++}$:

const int N = 1000003;
vector<int> G[N];
bool vis[N];

// v jest numerem aktualnie przetwarzanego wierzchołka
void DFS(int v) {
    vis[v] = true;
    for (int i = 0; i < G[v].size(); i++) {
        int u = G[v][i];
        if (!vis[u]) {     // ekwiwalent if (vis[u] == false)
            DFS(u);
        }
    }
}