Suvga tosh tashlaganingizda hosil bo'lgan to'lqinlarni tasavvur qiling: markazdan boshlab, bir xil masofadagi hamma nuqtaga birdek tarqaladi, keyin bir qadam uzoqroqqa, va hokazo. Breadth-First Search (BFS, "kenglik bo'yicha qidiruv") — grafni aynan shu tarzda kezib chiqadi: avval boshlang'ich nuqtaning bevosita qo'shnilari, keyin ularning qo'shnilari, va hokazo — "qatlama-qatlam".

BFS'ning eng katta afzalligi: agar barcha bog'lanishlar "bir xil uzunlikda" deb hisoblansa, u ikkita uch orasidagi eng qisqa yo'lni kafolatlangan tarzda topadi — chunki u yaqinroq nuqtalarni uzoqroqlaridan oldin ko'radi.

package main

import "fmt"

func bfs(graph map[string][]string, start string) []string {
	visited := map[string]bool{start: true}
	queue := []string{start} // "Queue Implementation" darsidagi Queue tuzilmasi
	var order []string

	for len(queue) > 0 {
		node := queue[0]
		queue = queue[1:]
		order = append(order, node)

		for _, neighbor := range graph[node] {
			if !visited[neighbor] {
				visited[neighbor] = true
				queue = append(queue, neighbor)
			}
		}
	}
	return order
}

func main() {
	graph := map[string][]string{
		"A": {"B", "C"},
		"B": {"D"},
		"C": {"D"},
		"D": {},
	}
	fmt.Println(bfs(graph, "A"))
}

Diqqat qiling: bu yerda queue — aynan "Queue Implementation" darsida yasagan FIFO tuzilmaning o'zi (bu yerda oddiy slice bilan qisqartirilgan ko'rinishda). BFS'ning "qatlama-qatlam" tabiati aynan shu Queue tufayli ta'minlanadi: yangi qo'shnilar navbatning oxiriga qo'shiladi, va biz doim navbatning boshidan olamiz — shuning uchun yaqinroq (avvalroq qo'shilgan) uchlar birinchi ko'riladi.

visited xaritasi ham juda muhim: uni ishlatmasak, A -> B -> A -> B -> ... kabi cheksiz aylanaga tushib qolishimiz mumkin edi (agar grafda tsikl bo'lsa). Har bir uchni faqat bir marta navbatga qo'shish — bu muammoning oldini oladi.