---
# System prepended metadata

title: Zajęcia 17.02.2021 - DFS
tags: [Informatyka 1PR]

---

# 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++}$:

```cpp
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);
        }
    }
}
```