Labirintda yurayotganingizni tasavvur qiling: BFS kabi "barcha yo'nalishlarni bir vaqtda" sinab ko'rish o'rniga, siz bitta yo'lni tanlab, tupikka yetguncha unga davom etasiz, so'ng orqaga qaytib, boshqa yo'lni sinaysiz. Depth-First Search (DFS, "chuqurlik bo'yicha qidiruv") — aynan shu strategiya: "kenglik" emas, "chuqurlik" bo'yicha birinchi.

DFS'ni odatda BFS'dagidek Queue bilan emas, rekursiya orqali (yoki Stack bilan) yozish tabiiyroq — chunki "bitta yo'lga chuqur kirib, keyin orqaga qaytish" xatti-harakati aynan funksiya chaqiruvlarining o'zi ishlaydigan tarzga ("Stack Implementation" darsida ko'rgan LIFO) mos keladi.

package main

import "fmt"

func dfs(graph map[string][]string, node string, visited map[string]bool, order *[]string) {
	if visited[node] {
		return
	}
	visited[node] = true
	*order = append(*order, node)

	for _, neighbor := range graph[node] {
		dfs(graph, neighbor, visited, order) // shu qo'shniga DARHOL chuqur kiramiz
	}
}

func main() {
	graph := map[string][]string{
		"A": {"B", "C"},
		"B": {"D"},
		"C": {"D"},
		"D": {},
	}
	visited := map[string]bool{}
	var order []string
	dfs(graph, "A", visited, &order)
	fmt.Println(order)
}

BFS'da qo'shnilarning hammasi navbatga qo'shilib, keyin navbat bo'yicha ko'riladi. DFS'da esa har bir qo'shni topilishi bilanoq, unga darhol rekursiv chuqurlashamiz (dfs(graph, neighbor, ...)) — faqat o'sha "filial" to'liq tugagach (barcha uning qo'shnilari ham ko'rilgach), funksiya "orqaga qaytib", keyingi qo'shnini sinaydi. Shuning uchun natija tartibi BFS'dan farq qiladi: [A B D C] (avval Bga chuqur kirib, Dgacha yetib, keyingina Cga qaytadi), [A B C D] emas.

Qachon DFS, qachon BFS? Agar sizga eng qisqa yo'l kerak bo'lsa — BFS. Agar sizga faqat "bog'lanish bor-yo'qligi" yoki "barcha yo'llarni sanab chiqish" kerak bo'lsa (masalan labirintni to'liq kezib chiqish, yoki daraxtni to'liq aylanib chiqish — "Binary Tree Basics"dagi InOrder aslida DFS'ning bir turi edi) — DFS ko'pincha soddaroq va tabiiyroq.