Breadth First Search (BFS)

Aylanib chiqish (traversal) — bu graf (Graph) yoki daraxtning barcha tugunlarini ziyorat qilishni anglatadi. Kenglik bo'yicha qidiruv (Breadth First Search - BFS) yoki kenglik bo'yicha aylanib chiqish — bu graf yoki daraxt ma'lumotlar tuzilmasining barcha cho'qqilarini qatlam-ba-qatlam ziyorat qilish uchun qo'llaniladigan navbatga (queue) asoslangan algoritm hisoblanadi.

Kenglik bo'yicha qidiruv algoritmi

Standart BFS algoritmi grafning har bir cho'qqisini ikkita toifadan biriga ajratadi:

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

Algoritmning asosiy maqsadi — sikllarga tushib qolmasdan har bir cho'qqini bir marta ziyorat qilingan deb belgilashdir.

BFS algoritmining ishlash tartibi:

1. Grafning ixtiyoriy bitta boshlang'ich cho'qqisini navbatning (queue) oxiriga joylang.
2. Navbatning boshidagi elementni oling, uni navbatdan chiqarib ziyorat qilinganlar ro'yxatiga qo'shing.
3. Ushbu cho'qqining barcha qo'shni tugunlari ro'yxatini ko'rib chiqing. Ziyorat qilinganlar ro'yxatida bo'lmagan qo'shnilarni navbatning oxiriga qo'shing va ularni ziyorat qilingan deb belgilang.
4. Navbat bo'shab qolguniga qadar 2 va 3-qadamlarni takrorlang.

[!NOTE] Agar graf bir-biri bilan tutashmagan bir nechta ajratilgan bo'laklardan iborat bo'lsa, barcha cho'qqilar qamrab olinishini ta'minlash uchun BFS har bir ziyorat qilinmagan cho'qqi uchun alohida ishga tushiriladi.

Kenglik bo'yicha qidiruvga misol

Keling, Breadth First Search algoritmining ishlashini 5 ta cho'qqidan iborat yo'naltirilmagan graf misolida tahlil qilaylik.

5 ta cho'qqiga ega yo'naltirilmagan graf

Biz 0-cho'qqidan boshlaymiz. BFS algoritmi uni ziyorat qilinganlar ro'yxatiga kiritadi va uning barcha qo'shni cho'qqilarini navbatga joylaydi.

Boshlang'ich cho'qqini ziyorat qilish va uning qo'shnilarini navbatga kiritish

Keyin navbat boshidagi birinchi elementni, ya'ni 1-cho'qqini navbatdan chiqaramiz va uning qo'shnilarini ko'rib chiqamiz. 0-cho'qqi allaqachon ziyorat qilingan, shuning uchun faqat yangi qo'shnilarni tekshiramiz.

0-tugunning birinchi qo'shnisi bo'lgan 1-cho'qqini ziyorat qilish

2-cho'qqi hali ziyorat qilinmagan 4-qo'shniga ega. Shuning uchun 4-cho'qqini navbatning orqa tomoniga qo'shamiz va navbatning boshida turgan 3-cho'qqini ziyorat qilamiz.

Navbatda turgan cho'qqilarni ketma-ket chiqarib ularning qo'shnilarini qo'shish

3-cho'qqining qo'shnilari allaqachon ziyorat qilingani sababli navbatda faqat 4 qoladi

Navbatda faqat 4-cho'qqi qoldi (chunki 3-cho'qqining yagona qo'shnisi 0 allaqachon ziyorat qilingan edi). Biz 4-cho'qqini ziyorat qilamiz:

Navbatdagi oxirgi qolgan elementni ziyorat qilish

Navbat bo'shab qolganligi sababli, graf bo'ylab kenglik bo'yicha aylanib chiqish muvaffaqiyatli yakunlandi.

BFS soxta kodi

create a queue Q 
mark v as visited and put v into Q 
while Q is non-empty:
    remove the head u of Q 
    mark and enqueue all (unvisited) neighbours of u

Dasturiy namunalar

// Go tilida Kenglik bo'yicha qidiruv (BFS) algoritmi
package main

import "fmt"

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

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

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

// Kenglik bo'yicha aylanib chiqish (BFS)
func (g *Graph) BFS(startVertex int) {
	visited := make([]bool, g.numVertices)
	queue := make([]int, 0)

	visited[startVertex] = true
	queue = append(queue, startVertex)

	for len(queue) > 0 {
		// Navbat boshidagi elementni olish
		currVertex := queue[0]
		queue = queue[1:]
		fmt.Printf("%d ", currVertex)

		// Barcha qo'shnilarini ko'rib chiqish
		for _, neighbor := range g.adjLists[currVertex] {
			if !visited[neighbor] {
				visited[neighbor] = true
				queue = append(queue, 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 BFS aylanib chiqish tartibi:")
	g.BFS(2)
	fmt.Println()
}

BFS algoritmining murakkabligi

• Vaqt murakkabligi: O(V + E) ko'rinishida ifodalanadi, bu yerda V — grafning cho'qqilari soni, E — qirralar soni. Chunki har bir cho'qqi navbatga bir marta kiritiladi va chiqariladi, har bir qirra esa bir marta tekshiriladi.
• Xotira murakkabligi: O(V). Eng yomon holatda navbatda barcha V ta cho'qqi saqlanishi mumkin.

BFS algoritmining amaliy qo'llanilishi

1. Qidiruv tizimlarida indekslash: Veb-sahifalarni havolalar bo'ylab qatlamma-qatlam indekslab chiqish (veb-kroulerlar).
2. GPS navigatsiya tizimlari: Og'irliksiz tarmoqlarda ikki nuqta o'rtasidagi eng qisqa yo'lni (eng kam oraliq ulanishlar sonini) topishda.
3. Yo'l qidirish algoritmlarida: Ijtimoiy tarmoqlarda do'stlik masofasini (do'stingizning do'stlarini) aniqlashda.
4. Ford-Fulkerson algoritmida: Tarmoqdagi maksimal oqimni hisoblashda (Edmonds-Karp varianti).
5. Yo'naltirilmagan grafda sikllarni aniqlashda: Halqalarni topish.
6. Minimal qoplovchi daraxt (Minimum Spanning Tree) yaratishda.