Depth First Search (DFS)

Chuqurlik bo'yicha qidiruv (Depth First Search - DFS) yoki chuqurlik bo'yicha aylanib chiqish (Depth First Traversal) — bu daraxt yoki graf (Graph) ma'lumotlar tuzilmasining barcha cho'qqilarini to'liq ko'rib chiqish uchun qo'llaniladigan rekursiv algoritm hisoblanadi. Aylanib chiqish (traversal) grafning barcha tugunlarini ziyorat qilishni anglatadi.

Chuqurlik bo'yicha qidiruv algoritmi

DFS algoritmining standart realizatsiyasi grafning har bir cho'qqisini ikkita toifadan biriga ajratadi:

1. Ziyorat qilingan (Visited)
2. Ziyorat qilinmagan (Not Visited)

Algoritmning asosiy maqsadi — halqalardan (sikllardan) qochgan holda har bir cho'qqini aynan bir marta ziyorat qilingan deb belgilab chiqishdir.

DFS algoritmining ishlash tartibi:

1. Grafning ixtiyoriy bitta cho'qqisini tanlab, uni stekning (stack) yuqorisiga joylang.
2. Stekning eng yuqori elementini oling va uni ziyorat qilinganlar ro'yxatiga (visited list) qo'shing.
3. Ushbu cho'qqining barcha qo'shni tugunlari ro'yxatini tuzing. Ziyorat qilinganlar ro'yxatida bo'lmagan qo'shnilarni stekning yuqorisiga qo'shing.
4. Stek bo'shab qolguniga qadar 2 va 3-qadamlarni takrorlang.

Chuqurlik bo'yicha qidiruvga misol

Keling, Depth First Search algoritmining ishlashini misol orqali ko'rib chiqamiz. Buning uchun 5 ta cho'qqidan iborat yo'naltirilmagan grafni tahlil qilamiz.

5 ta cho'qqiga ega yo'naltirilmagan graf

Biz 0-cho'qqidan boshlaymiz. DFS algoritmi uni ziyorat qilinganlar ro'yxatiga kiritadi va uning barcha qo'shni cho'qqilarini (1, 2, 3) stekka joylaydi.

Elementni ziyorat qilish va ziyorat qilinganlar ro'yxatiga qo'shish

Keyin stekning yuqorisidagi elementni, ya'ni 1-cho'qqini ziyorat qilamiz va uning qo'shni tugunlariga qaraymiz. 0-cho'qqi allaqachon ziyorat qilinganligi sababli, 2-cho'qqiga o'tamiz.

Stekning eng yuqori elementini ziyorat qilish

2-cho'qqi hali ziyorat qilinmagan 4-qo'shniga ega, shuning uchun biz 4-cho'qqini stekning yuqorisiga joylaymiz va uni ziyorat qilamiz.

2-cho'qqining ziyorat qilinmagan 4-qo'shnisini stekka qo'shish va ziyorat qilish

4-cho'qqi va uning qo'shnilari ko'rib chiqilmoqda

Oxirgi 3-elementni ziyorat qilganimizdan so'ng, unda boshqa hech qanday ziyorat qilinmagan qo'shni tugun qolmaydi. Shu tariqa, graf bo'ylab chuqurlik bo'yicha qidiruv muvaffaqiyatli yakunlanadi.

Oxirgi element ziyorat qilingach, grafni DFS bo'yicha to'liq aylanib chiqish yakunlandi

DFS psevdokodi

Quyida DFS algoritmining rekursiv ifodalanishi ko'rsatilgan. init() funksiyasiga e'tibor bering: biz DFS funksiyasini har bir tugun bo'yicha chaqiramiz. Chunki graf bir-biri bilan bog'lanmagan bir nechta ajratilgan bo'laklardan iborat bo'lishi ham mumkin; barcha cho'qqilar qamrab olinishini ta'minlash uchun har bir ziyorat qilinmagan tugun tekshiriladi:

DFS(G, u)
    u.visited = true
    for each v in G.Adj[u]
        if v.visited == false
            DFS(G, v)

init() {
    for each u in G
        u.visited = false
    for each u in G
        if u.visited == false
            DFS(G, u)
}

Dasturiy namunalar

// Go tilida Chuqurlik bo'yicha qidiruv (DFS) algoritmi
package main

import "fmt"

type Graph struct {
	numVertices int
	adjLists    [][]int
	visited     []bool
}

func NewGraph(vertices int) *Graph {
	return &Graph{
		numVertices: vertices,
		adjLists:    make([][]int, vertices),
		visited:     make([]bool, vertices),
	}
}

// Qirra qo'shish
func (g *Graph) AddEdge(src, dest int) {
	g.adjLists[src] = append(g.adjLists[src], dest)
}

// Rekursiv DFS algoritmi
func (g *Graph) DFS(vertex int) {
	g.visited[vertex] = true
	fmt.Printf("%d ", vertex)

	for _, neighbor := range g.adjLists[vertex] {
		if !g.visited[neighbor] {
			g.DFS(neighbor)
		}
	}
}

func main() {
	g := NewGraph(4)

	g.AddEdge(0, 1)
	g.AddEdge(0, 2)
	g.AddEdge(1, 2)
	g.AddEdge(2, 0)
	g.AddEdge(2, 3)
	g.AddEdge(3, 3)

	fmt.Println("2-cho'qqidan boshlangan DFS aylanib chiqish tartibi:")
	g.DFS(2)
	fmt.Println()
}

Chuqurlik bo'yicha qidiruvning murakkabligi

• Vaqt murakkabligi: O(V + E) ko'rinishida ifodalanadi, bu yerda V — grafning cho'qqilari soni, E — qirralar soni. Chunki har bir cho'qqi va qirra ko'pi bilan bir marta ko'rib chiqiladi.
• Xotira murakkabligi: O(V). Eng yomon holatda (zanjirsimon grafda) rekursiya steki yoki qo'shimcha visited massivi barcha V ta cho'qqini o'zida saqlaydi.

DFS algoritmining amaliy qo'llanilishi

1. Grafda yo'l mavjudligini aniqlash: Ikki cho'qqi o'rtasida yo'l bor-yo'qligini tekshirishda.
2. Grafning ikki qismli (bipartite) ekanligini sinash: Cho'qqilarni ikki to'plamga ajratish imkoniyatini aniqlashda.
3. Kuchli bog'langan komponentlarni topish: Kosaraju algoritmi orqali kuchli bog'langan qismlarni ajratishda.
4. Grafda sikllarni aniqlash (Cycle Detection): Grafda halqa yoki berk sikl hosil bo'lganligini tekshirishda.