DFS (Depth-First Search / Distributed File System)

Pojem DFS se v informatice používá ve dvou zcela odlišných významech:

1. DFS jako Algoritmus (Depth-First Search)

Prohledávání do hloubky je algoritmus pro procházení grafů nebo stromových struktur. Strategií tohoto algoritmu je postupovat v jedné větvi co nejdále do hloubky, dokud nenarazí na konec (list) nebo na již navštívený uzel, a teprve poté se vrátit k nejbližšímu rozcestí (backtracking).

Vlastnosti algoritmu

Datová struktura: K implementaci se typicky používá zásobník (stack) nebo rekurze.

Využití: Hledání cest v bludišti, topologické uspořádání, detekce cyklů v grafu.

Složitost: $O(V + E)$, kde $V$ je počet vrcholů a $E$ počet hran.

2. DFS jako Distribuovaný souborový systém

Distributed File System je technologie, která umožňuje přistupovat k souborům rozptýleným na různých serverech tak, jako by byly uloženy na jednom lokálním disku. Uživatel vidí jednu logickou strukturu složek, i když fyzicky data leží na deseti různých strojích.

Hlavní příklady a implementace

NFS (Network File System): Klasika v Unixových systémech.

Microsoft DFS: Součást Windows Serveru, která sjednocuje sdílené složky do jednoho jmenného prostoru (Namespace).

HDFS (Hadoop Distributed File System): Navržen pro ukládání obrovských objemů dat (Big Data) napříč tisíci levných serverů.

Výhody distribuovaného ukládání

Škálovatelnost: Snadné přidání dalších serverů pro zvýšení kapacity.

Redundance: Data mohou být replikována na více místech. Pokud jeden server vypadne, soubory jsou stále dostupné odjinud.

Transparentnost: Uživatel nemusí vědět, na kterém konkrétním serveru je jeho soubor uložen.

Srovnání: DFS vs. BFS (u algoritmů)

Vlastnost	DFS (Do hloubky)	BFS (Do šířky)
Priorita	Jde co nejdál od startu.	Prozkoumává nejbližší sousedy.
Paměť	Obvykle méně náročný.	Náročnější na paměť (ukládá celou „vlnu“).
Nejkratší cesta	Negarantuje nalezení nejkratší cesty.	V neseřazeném grafu vždy najde nejkratší cestu.
Zajímavost: Algoritmus DFS se často přirovnává k procházení bludiště s nití (jako Ariadnina nit). Jdete pořád dál, a když narazíte na zeď, vracíte se po niti zpět, dokud nenajdete jinou odbočku.

Zpět na Algoritmy nebo Zpět na Architekturu