Bir grafı elinde tuttuğunda ilk yapacağın şey onu gezmektir: Hangi düğümlere ulaşabiliyorum, kaç parçaya ayrılmış, iki nokta arasında yol var mı? Graf algoritmalarının neredeyse tamamı, iki temel gezinme stratejisinden birinin üzerine kuruludur.
Genişlik öncelikli arama (BFS) katman katman ilerler: Önce bir adımda ulaşılan her yeri, sonra iki adımda ulaşılan her yeri ziyaret eder. Bu yüzden ağırlıksız graflarda en kısa yolu bulmanın doğal yoludur. Derinlik öncelikli arama (DFS) ise bir yolu sonuna kadar takip eder, tıkanınca geri döner ve başka bir dal dener. Döngü tespiti, bağlantılı bileşen bulma ve topolojik sıralama bu stratejiye dayanır.
Aradaki fark tek bir veri yapısıdır: BFS kuyruk, DFS yığın kullanır. Kodları neredeyse aynıdır ama davranışları tamamen farklıdır. Bu derste ikisini de yazacak, ızgara problemlerine uygulayacak, bileşen sayacak, döngü tespit edecek ve çok kaynaklı BFS gibi güçlü bir varyantı öğreneceksin.
Genişlik öncelikli arama
A'dan başla:
A ─── B ─── D
│ │
C ─── E ─── F
katman 0: A
katman 1: B, C (A'nın komşuları)
katman 2: D, E (B ve C'nin yeni komşuları)
katman 3: F (E'nin yeni komşusu)
Kuyruk kullanılır: ilk giren ilk çıkar → yakın düğümler önceAşağıdaki görselleştirmede BFS'in katman katman ilerleyişini adım adım izleyebilirsin:
package main
import (
"fmt"
"maps"
"slices"
)
type Graph map[string][]string
func (g Graph) AddEdge(a, b string) {
g[a] = append(g[a], b)
g[b] = append(g[b], a)
slices.Sort(g[a]) // deterministik gezinme sırası
slices.Sort(g[b])
}
func (g Graph) Nodes() []string { return slices.Sorted(maps.Keys(g)) }
// bfs: ziyaret sırasını ve her düğümün uzaklığını döndürür
func (g Graph) bfs(start string) ([]string, map[string]int) {
visited := map[string]bool{start: true}
dist := map[string]int{start: 0}
queue := []string{start}
var order []string
for len(queue) > 0 {
cur := queue[0]
queue = queue[1:] // kuyruktan çıkar
order = append(order, cur)
for _, next := range g[cur] {
if visited[next] {
continue
}
visited[next] = true // ÇIKARIRKEN değil, EKLERKEN işaretle
dist[next] = dist[cur] + 1
queue = append(queue, next)
}
}
return order, dist
}
// bfsLevels: katmanları ayrı ayrı döndürür
func (g Graph) bfsLevels(start string) [][]string {
visited := map[string]bool{start: true}
current := []string{start}
var levels [][]string
for len(current) > 0 {
levels = append(levels, current)
var next []string
for _, node := range current {
for _, n := range g[node] {
if !visited[n] {
visited[n] = true
next = append(next, n)
}
}
}
current = next
}
return levels
}
func main() {
g := Graph{}
for _, e := range [][2]string{
{"A", "B"}, {"A", "C"}, {"B", "D"}, {"B", "E"},
{"C", "E"}, {"E", "F"},
} {
g.AddEdge(e[0], e[1])
}
g["G"] = nil // ayrı bileşen
order, dist := g.bfs("A")
fmt.Println("BFS ziyaret sırası:", order)
fmt.Println()
fmt.Println("A'dan uzaklıklar:")
for _, n := range g.Nodes() {
d, ok := dist[n]
if !ok {
fmt.Printf(" %s: ulaşılamaz\n", n)
continue
}
fmt.Printf(" %s: %d adım\n", n, d)
}
fmt.Println()
fmt.Println("katmanlar:")
for i, level := range g.bfsLevels("A") {
fmt.Printf(" katman %d: %v\n", i, level)
}
}BFS ziyaret sırası: [A B C D E F] A'dan uzaklıklar: A: 0 adım B: 1 adım C: 1 adım D: 2 adım E: 2 adım F: 3 adım G: ulaşılamaz katmanlar: katman 0: [A] katman 1: [B C] katman 2: [D E] katman 3: [F]
Ağırlıksız grafta en kısa yol
BFS'in en önemli özelliği şudur: Katman katman ilerlediği için, bir düğüme ilk ulaştığında en kısa yolu bulmuş olur. Bu, yalnızca tüm kenarların ağırlığı eşit olduğunda geçerlidir; farklı ağırlıklar varsa Dijkstra gerekir.
package main
import (
"fmt"
"slices"
"strings"
)
type Graph map[string][]string
func (g Graph) AddEdge(a, b string) {
g[a] = append(g[a], b)
g[b] = append(g[b], a)
slices.Sort(g[a])
slices.Sort(g[b])
}
// shortestPath: BFS ile en kısa yolu bulur ve yolu geri oluşturur
func (g Graph) shortestPath(start, target string) ([]string, int, bool) {
if start == target {
return []string{start}, 0, true
}
parent := map[string]string{start: ""}
queue := []string{start}
for len(queue) > 0 {
cur := queue[0]
queue = queue[1:]
for _, next := range g[cur] {
if _, seen := parent[next]; seen {
continue
}
parent[next] = cur
if next == target {
// Yolu geriye doğru kur
var path []string
for n := target; n != ""; n = parent[n] {
path = append(path, n)
}
slices.Reverse(path)
return path, len(path) - 1, true
}
queue = append(queue, next)
}
}
return nil, -1, false
}
func main() {
// Metro hattı benzetimi
g := Graph{}
lines := [][2]string{
{"Kadıköy", "Ayrılık Çeşmesi"},
{"Ayrılık Çeşmesi", "Acıbadem"},
{"Acıbadem", "Ünalan"},
{"Ünalan", "Göztepe"},
{"Ayrılık Çeşmesi", "Söğütlüçeşme"},
{"Söğütlüçeşme", "Fikirtepe"},
{"Fikirtepe", "Göztepe"},
{"Göztepe", "Yenisahra"},
}
for _, e := range lines {
g.AddEdge(e[0], e[1])
}
g["Sirkeci"] = nil // bağlantısı olmayan istasyon
routes := [][2]string{
{"Kadıköy", "Yenisahra"},
{"Kadıköy", "Göztepe"},
{"Acıbadem", "Fikirtepe"},
{"Kadıköy", "Kadıköy"},
{"Kadıköy", "Sirkeci"},
}
for _, r := range routes {
path, stops, ok := g.shortestPath(r[0], r[1])
if !ok {
fmt.Printf("%s → %s: ULAŞILAMAZ\n", r[0], r[1])
continue
}
fmt.Printf("%s → %s: %d durak\n", r[0], r[1], stops)
fmt.Println(" ", strings.Join(path, " → "))
}
fmt.Println()
fmt.Println("BFS'in garantisi: bir düğüme İLK ulaşıldığında")
fmt.Println("bulunan yol, en kısa yoldur (ağırlıksız grafta).")
}Kadıköy → Yenisahra: 5 durak Kadıköy → Ayrılık Çeşmesi → Acıbadem → Ünalan → Göztepe → Yenisahra Kadıköy → Göztepe: 4 durak Kadıköy → Ayrılık Çeşmesi → Acıbadem → Ünalan → Göztepe Acıbadem → Fikirtepe: 3 durak Acıbadem → Ayrılık Çeşmesi → Söğütlüçeşme → Fikirtepe Kadıköy → Kadıköy: 0 durak Kadıköy Kadıköy → Sirkeci: ULAŞILAMAZ BFS'in garantisi: bir düğüme İLK ulaşıldığında bulunan yol, en kısa yoldur (ağırlıksız grafta).
Derinlik öncelikli arama
DFS bir yolu sonuna kadar takip eder. Özyinelemeli yazımı çok kısadır; iteratif yazımı bir yığın kullanır.
A'dan başla (alfabetik sırayla):
A ─── B ─── D
│ │
C ─── E ─── F
A → B → D (tıkandı, geri dön) → E → C (tıkandı) → geri → F
Ziyaret sırası: A B D E C F
Yığın kullanılır: son giren ilk çıkar → derine dalAşağıdaki görselleştirmede DFS'in derine dalıp geri dönüş davranışını izleyebilirsin:
package main
import (
"fmt"
"maps"
"slices"
)
type Graph map[string][]string
func (g Graph) AddEdge(a, b string) {
g[a] = append(g[a], b)
g[b] = append(g[b], a)
slices.Sort(g[a])
slices.Sort(g[b])
}
func (g Graph) Nodes() []string { return slices.Sorted(maps.Keys(g)) }
// dfsRecursive: özyinelemeli — kısa ve okunaklı
func (g Graph) dfsRecursive(start string) []string {
visited := map[string]bool{}
var order []string
var walk func(string)
walk = func(node string) {
if visited[node] {
return
}
visited[node] = true
order = append(order, node)
for _, next := range g[node] {
walk(next)
}
}
walk(start)
return order
}
// dfsIterative: yığınla — derin graflarda güvenli
func (g Graph) dfsIterative(start string) []string {
visited := map[string]bool{}
stack := []string{start}
var order []string
for len(stack) > 0 {
cur := stack[len(stack)-1]
stack = stack[:len(stack)-1]
if visited[cur] {
continue
}
visited[cur] = true
order = append(order, cur)
// TERS sırada ekle: alfabetik olarak ilk komşu önce çıksın
for i := len(g[cur]) - 1; i >= 0; i-- {
if !visited[g[cur][i]] {
stack = append(stack, g[cur][i])
}
}
}
return order
}
// dfsWithTimes: giriş ve çıkış zamanlarını kaydeder
func (g Graph) dfsWithTimes(start string) (map[string]int, map[string]int) {
entry, exit := map[string]int{}, map[string]int{}
visited := map[string]bool{}
timer := 0
var walk func(string)
walk = func(node string) {
visited[node] = true
timer++
entry[node] = timer
for _, next := range g[node] {
if !visited[next] {
walk(next)
}
}
timer++
exit[node] = timer
}
walk(start)
return entry, exit
}
func main() {
g := Graph{}
for _, e := range [][2]string{
{"A", "B"}, {"A", "C"}, {"B", "D"}, {"B", "E"},
{"C", "E"}, {"E", "F"},
} {
g.AddEdge(e[0], e[1])
}
rec := g.dfsRecursive("A")
it := g.dfsIterative("A")
fmt.Println("DFS (özyinelemeli):", rec)
fmt.Println("DFS (iteratif): ", it)
fmt.Println("aynı sıra mı:", slices.Equal(rec, it))
fmt.Println()
entry, exit := g.dfsWithTimes("A")
fmt.Printf("%-6s %8s %8s\n", "düğüm", "giriş", "çıkış")
for _, n := range g.Nodes() {
fmt.Printf("%-6s %8d %8d\n", n, entry[n], exit[n])
}
fmt.Println()
fmt.Println("Giriş/çıkış zamanları köprü bulma, güçlü bağlı bileşen")
fmt.Println("ve ata-torun ilişkisi tespitinde kullanılır.")
}DFS (özyinelemeli): [A B D E C F] DFS (iteratif): [A B D E C F] aynı sıra mı: true düğüm giriş çıkış A 1 12 B 2 11 C 6 7 D 3 4 E 5 10 F 8 9 Giriş/çıkış zamanları köprü bulma, güçlü bağlı bileşen ve ata-torun ilişkisi tespitinde kullanılır.
BFS ile DFS'in kod farkı yalnızca veri yapısıdır:
Izgara problemleri ve bileşen sayma
Izgaralar örtük graflardır: Her hücre bir düğüm, komşu hücreler arasında kenar var. Grafı bellekte kurmaya gerek yoktur; komşular formülle hesaplanır.
package main
import "fmt"
var directions = [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}} // yukarı, aşağı, sol, sağ
// countIslands: DFS ile ada sayma
func countIslands(grid [][]byte) (int, []int) {
if len(grid) == 0 {
return 0, nil
}
rows, cols := len(grid), len(grid[0])
visited := make([][]bool, rows)
for i := range visited {
visited[i] = make([]bool, cols)
}
var size int
var dfs func(r, c int)
dfs = func(r, c int) {
if r < 0 || r >= rows || c < 0 || c >= cols {
return
}
if visited[r][c] || grid[r][c] != '1' {
return
}
visited[r][c] = true
size++
for _, d := range directions {
dfs(r+d[0], c+d[1])
}
}
count := 0
var sizes []int
for r := range rows {
for c := range cols {
if grid[r][c] == '1' && !visited[r][c] {
size = 0
dfs(r, c)
count++
sizes = append(sizes, size)
}
}
}
return count, sizes
}
// floodFill: BFS ile boyama
func floodFill(grid [][]byte, sr, sc int, newColor byte) [][]byte {
rows, cols := len(grid), len(grid[0])
oldColor := grid[sr][sc]
if oldColor == newColor {
return grid
}
queue := [][2]int{{sr, sc}}
grid[sr][sc] = newColor
for len(queue) > 0 {
cur := queue[0]
queue = queue[1:]
for _, d := range directions {
r, c := cur[0]+d[0], cur[1]+d[1]
if r < 0 || r >= rows || c < 0 || c >= cols {
continue
}
if grid[r][c] != oldColor {
continue
}
grid[r][c] = newColor
queue = append(queue, [2]int{r, c})
}
}
return grid
}
// shortestPathInGrid: engelli ızgarada en kısa yol (BFS)
func shortestPathInGrid(grid [][]byte, start, end [2]int) int {
rows, cols := len(grid), len(grid[0])
if grid[start[0]][start[1]] == '#' || grid[end[0]][end[1]] == '#' {
return -1
}
dist := make([][]int, rows)
for i := range dist {
dist[i] = make([]int, cols)
for j := range dist[i] {
dist[i][j] = -1
}
}
dist[start[0]][start[1]] = 0
queue := [][2]int{start}
for len(queue) > 0 {
cur := queue[0]
queue = queue[1:]
if cur == end {
return dist[cur[0]][cur[1]]
}
for _, d := range directions {
r, c := cur[0]+d[0], cur[1]+d[1]
if r < 0 || r >= rows || c < 0 || c >= cols {
continue
}
if grid[r][c] == '#' || dist[r][c] != -1 {
continue
}
dist[r][c] = dist[cur[0]][cur[1]] + 1
queue = append(queue, [2]int{r, c})
}
}
return -1
}
func printGrid(grid [][]byte) {
for _, row := range grid {
for _, b := range row {
switch b {
case '1':
fmt.Print("■ ")
case '0':
fmt.Print("· ")
case '#':
fmt.Print("█ ")
default:
fmt.Printf("%c ", b)
}
}
fmt.Println()
}
}
func toGrid(lines []string) [][]byte {
out := make([][]byte, len(lines))
for i, l := range lines {
out[i] = []byte(l)
}
return out
}
func main() {
islands := toGrid([]string{
"11000",
"11000",
"00100",
"00011",
})
fmt.Println("ada haritası:")
printGrid(islands)
count, sizes := countIslands(islands)
fmt.Println("ada sayısı:", count, "| boyutlar:", sizes)
fmt.Println()
canvas := toGrid([]string{
"1110",
"1100",
"0010",
})
fmt.Println("boyama öncesi:")
printGrid(canvas)
floodFill(canvas, 0, 0, '2')
fmt.Println("boyama sonrası (0,0'dan başlayarak):")
printGrid(canvas)
fmt.Println()
maze := toGrid([]string{
".....",
".###.",
".....",
".#.#.",
".....",
})
fmt.Println("labirent (█ = duvar):")
printGrid(maze)
d := shortestPathInGrid(maze, [2]int{0, 0}, [2]int{4, 4})
fmt.Println("(0,0) → (4,4) en kısa yol:", d, "adım")
blocked := toGrid([]string{
"..#",
"..#",
"###",
})
fmt.Println()
fmt.Println("kapalı labirent:")
printGrid(blocked)
fmt.Println("(0,0) → (2,2):", shortestPathInGrid(blocked, [2]int{0, 0}, [2]int{2, 2}))
}ada haritası: ■ ■ · · · ■ ■ · · · · · ■ · · · · · ■ ■ ada sayısı: 3 | boyutlar: [4 1 2] boyama öncesi: ■ ■ ■ · ■ ■ · · · · ■ · boyama sonrası (0,0'dan başlayarak): 2 2 2 · 2 2 · · · · ■ · labirent (█ = duvar): . . . . . . █ █ █ . . . . . . . █ . █ . . . . . . (0,0) → (4,4) en kısa yol: 8 adım kapalı labirent: . . █ . . █ █ █ █ (0,0) → (2,2): -1
Izgara problemlerinde directions dizisini ayrı tanımlamak, kodu hem kısaltır hem de komşuluk tanımını tek noktada toplar. Köşegen hareketi eklemek istiyorsan diziye dört eleman daha eklemek yeterlidir; algoritmanın geri kalanına dokunmazsın.
Yönsüz grafta döngü tespiti
DFS ile döngü bulmak, bir düğümün ebeveyni dışındaki ziyaret edilmiş bir komşuya rastlamasını kontrol etmektir.
package main
import (
"fmt"
"maps"
"slices"
)
type Graph map[string][]string
func (g Graph) AddEdge(a, b string) {
g[a] = append(g[a], b)
g[b] = append(g[b], a)
slices.Sort(g[a])
slices.Sort(g[b])
}
func (g Graph) AddNode(n string) {
if _, ok := g[n]; !ok {
g[n] = nil
}
}
func (g Graph) Nodes() []string { return slices.Sorted(maps.Keys(g)) }
// hasCycle: yönsüz grafta döngü var mı
func (g Graph) hasCycle() (bool, []string) {
visited := map[string]bool{}
parent := map[string]string{}
var cyclePath []string
var dfs func(node, from string) bool
dfs = func(node, from string) bool {
visited[node] = true
for _, next := range g[node] {
if next == from {
continue // ebeveyne dönmek döngü değil
}
if visited[next] {
// Döngü bulundu: yolu geri kur
cyclePath = []string{next}
for n := node; n != next && n != ""; n = parent[n] {
cyclePath = append(cyclePath, n)
}
cyclePath = append(cyclePath, next)
return true
}
parent[next] = node
if dfs(next, node) {
return true
}
}
return false
}
for _, n := range g.Nodes() {
if !visited[n] {
if dfs(n, "") {
return true, cyclePath
}
}
}
return false, nil
}
// connectedComponents: bağlı bileşenleri döndürür
func (g Graph) connectedComponents() [][]string {
visited := map[string]bool{}
var components [][]string
for _, start := range g.Nodes() {
if visited[start] {
continue
}
var component []string
queue := []string{start}
visited[start] = true
for len(queue) > 0 {
cur := queue[0]
queue = queue[1:]
component = append(component, cur)
for _, next := range g[cur] {
if !visited[next] {
visited[next] = true
queue = append(queue, next)
}
}
}
slices.Sort(component)
components = append(components, component)
}
return components
}
// isTree: bağlantılı ve döngüsüz mü
func (g Graph) isTree() bool {
hasCyc, _ := g.hasCycle()
return !hasCyc && len(g.connectedComponents()) == 1
}
func main() {
// Ağaç: döngüsüz ve bağlantılı
tree := Graph{}
for _, e := range [][2]string{{"A", "B"}, {"A", "C"}, {"B", "D"}, {"B", "E"}} {
tree.AddEdge(e[0], e[1])
}
cyc, path := tree.hasCycle()
fmt.Println("AĞAÇ:")
fmt.Println(" döngü var mı:", cyc)
fmt.Println(" bileşenler:", tree.connectedComponents())
fmt.Println(" ağaç mı:", tree.isTree())
fmt.Println(" kenar sayısı:", 4, "düğüm sayısı:", len(tree.Nodes()), "(n-1 kuralı ✓)")
// Döngülü graf
cyclic := Graph{}
for _, e := range [][2]string{{"A", "B"}, {"B", "C"}, {"C", "A"}, {"C", "D"}} {
cyclic.AddEdge(e[0], e[1])
}
cyc, path = cyclic.hasCycle()
fmt.Println()
fmt.Println("DÖNGÜLÜ GRAF:")
fmt.Println(" döngü var mı:", cyc)
if cyc {
fmt.Println(" döngü yolu:", path)
}
fmt.Println(" ağaç mı:", cyclic.isTree())
// Kopuk graf: birden çok bileşen
forest := Graph{}
for _, e := range [][2]string{{"A", "B"}, {"C", "D"}, {"E", "F"}, {"F", "G"}} {
forest.AddEdge(e[0], e[1])
}
forest.AddNode("H")
fmt.Println()
fmt.Println("ORMAN (kopuk graf):")
cyc, _ = forest.hasCycle()
fmt.Println(" döngü var mı:", cyc)
fmt.Println(" bileşen sayısı:", len(forest.connectedComponents()))
for i, c := range forest.connectedComponents() {
fmt.Printf(" bileşen %d: %v\n", i+1, c)
}
fmt.Println(" ağaç mı:", forest.isTree(), "← bağlantılı değil")
}AĞAÇ:
döngü var mı: false
bileşenler: [[A B C D E]]
ağaç mı: true
kenar sayısı: 4 düğüm sayısı: 5 (n-1 kuralı ✓)
DÖNGÜLÜ GRAF:
döngü var mı: true
döngü yolu: [A C B A]
ağaç mı: false
ORMAN (kopuk graf):
döngü var mı: false
bileşen sayısı: 4
bileşen 1: [A B]
bileşen 2: [C D]
bileşen 3: [E F G]
bileşen 4: [H]
ağaç mı: false ← bağlantılı değilYönsüz grafta next == from kontrolü kritiktir: A-B kenarı üzerinden B'ye geldiysek, B'den A'ya geri bakmak bir döngü değildir. Bu kontrolü atlamak, her kenarı bir döngü olarak bildirmeye yol açar.
Yönlü graflarda döngü tespiti farklıdır ve üç renkli DFS gerektirir; onu Topolojik Sıralama dersinde göreceksin.
Çok kaynaklı BFS
Bu, BFS'in en zarif varyantıdır: Tek bir başlangıç düğümü yerine birden çok düğümü aynı anda kuyruğa koyarsın. Sonuç, "en yakın kaynağa uzaklık" haritası olur — ve bu, her kaynaktan ayrı ayrı BFS yapmaktan çok daha hızlıdır.
package main
import "fmt"
var directions = [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
// nearestSource: her hücrenin en yakın kaynağa uzaklığı
func nearestSource(grid [][]byte, sourceChar byte) [][]int {
rows, cols := len(grid), len(grid[0])
dist := make([][]int, rows)
var queue [][2]int
for i := range dist {
dist[i] = make([]int, cols)
for j := range dist[i] {
dist[i][j] = -1
}
}
// TÜM kaynakları başlangıçta kuyruğa koy
for r := range rows {
for c := range cols {
if grid[r][c] == sourceChar {
dist[r][c] = 0
queue = append(queue, [2]int{r, c})
}
}
}
for len(queue) > 0 {
cur := queue[0]
queue = queue[1:]
for _, d := range directions {
r, c := cur[0]+d[0], cur[1]+d[1]
if r < 0 || r >= rows || c < 0 || c >= cols {
continue
}
if grid[r][c] == '#' || dist[r][c] != -1 {
continue
}
dist[r][c] = dist[cur[0]][cur[1]] + 1
queue = append(queue, [2]int{r, c})
}
}
return dist
}
// rottenOranges: çürük portakallar tüm taze portakalları kaç dakikada çürütür
func rottenOranges(grid [][]byte) (int, int) {
rows, cols := len(grid), len(grid[0])
var queue [][2]int
fresh := 0
for r := range rows {
for c := range cols {
switch grid[r][c] {
case '2':
queue = append(queue, [2]int{r, c})
case '1':
fresh++
}
}
}
minutes := 0
for len(queue) > 0 && fresh > 0 {
minutes++
var next [][2]int
for _, cur := range queue {
for _, d := range directions {
r, c := cur[0]+d[0], cur[1]+d[1]
if r < 0 || r >= rows || c < 0 || c >= cols {
continue
}
if grid[r][c] != '1' {
continue
}
grid[r][c] = '2'
fresh--
next = append(next, [2]int{r, c})
}
}
queue = next
}
return minutes, fresh
}
func printDist(dist [][]int) {
for _, row := range dist {
for _, v := range row {
if v == -1 {
fmt.Printf("%4s", "-")
continue
}
fmt.Printf("%4d", v)
}
fmt.Println()
}
}
func toGrid(lines []string) [][]byte {
out := make([][]byte, len(lines))
for i, l := range lines {
out[i] = []byte(l)
}
return out
}
func main() {
// Her hücrenin en yakın su kaynağına uzaklığı
grid := toGrid([]string{
"..W..",
".....",
"..#..",
"W....",
".....",
})
fmt.Println("harita (W = su kaynağı, # = engel):")
for _, row := range grid {
fmt.Println(" " + string(row))
}
dist := nearestSource(grid, 'W')
fmt.Println()
fmt.Println("en yakın kaynağa uzaklık:")
printDist(dist)
fmt.Println()
fmt.Println("Tek kaynaklı BFS'i 2 kez yapmak yerine")
fmt.Println("tek çok kaynaklı BFS yeterli: O(R×C) toplam.")
// Çürük portakal problemi
fmt.Println()
oranges := toGrid([]string{
"2110",
"1101",
"0111",
})
fmt.Println("portakallar (2=çürük, 1=taze, 0=boş):")
for _, row := range oranges {
fmt.Println(" " + string(row))
}
minutes, remaining := rottenOranges(oranges)
fmt.Println("tüm portakallar çürüdü:", minutes, "dakika")
fmt.Println("çürümeyen taze portakal:", remaining)
isolated := toGrid([]string{
"2100",
"0001",
})
fmt.Println()
m2, r2 := rottenOranges(isolated)
fmt.Println("izole portakal olan durum:", m2, "dakika,", r2, "portakal çürümedi")
}harita (W = su kaynağı, # = engel): ..W.. ..... ..#.. W.... ..... en yakın kaynağa uzaklık: 2 1 0 1 2 2 2 1 2 3 1 2 - 3 4 0 1 2 3 4 1 2 3 4 5 Tek kaynaklı BFS'i 2 kez yapmak yerine tek çok kaynaklı BFS yeterli: O(R×C) toplam. portakallar (2=çürük, 1=taze, 0=boş): 2110 1101 0111 tüm portakallar çürüdü: 6 dakika çürümeyen taze portakal: 0 izole portakal olan durum: 2 dakika, 1 portakal çürümedi
Çok kaynaklı BFS'in gücünü sayılarla düşün: k kaynak varsa, her birinden ayrı BFS yapmak O(k × (V+E)) sürer. Hepsini aynı kuyruğa koymak ise tek geçişte O(V+E) verir. Kazanç kaynak sayısı kadardır.
Bu varyant pek çok problemde işe yarar: en yakın hastaneye uzaklık, yangının yayılma süresi, bir hastalığın bulaşma katmanları, oyunlarda düşman etki alanı.
BFS mi DFS mi?
İki algoritma arasında seçim yapmak genelde kolaydır; hangi bilgiye ihtiyaç duyduğunla belirlenir.
En kısa yol veya minimum adım sayısı gerekiyorsa BFS. Ağırlıksız graflarda BFS bunu doğal olarak verir, DFS vermez. "En az kaç hamlede" tipi tüm sorular BFS'tir.
Bir yol bulmak yeterliyse ve en kısa olması gerekmiyorsa DFS. Kodu daha kısadır, özyinelemeli yazımı zariftir ve genelde daha az bellek kullanır.
Tüm olasılıkları denemek gerekiyorsa DFS. Geri izleme (backtracking) algoritmaları DFS'in bir biçimidir: Bir yolu dene, çıkmazsa geri dön, başkasını dene.
Döngü, bileşen veya yapısal özellik arıyorsan DFS. Giriş/çıkış zamanları, köprüler, kesme noktaları ve güçlü bağlı bileşenler DFS'in doğal ürünleridir.
Katman bilgisi gerekiyorsa BFS. "İki adımda ulaşılabilen düğümler", "aynı seviyedeki elemanlar" gibi sorular BFS'in yapısına uyar.
Bellek kısıtı varsa grafın şekline bak. BFS en geniş katman kadar, DFS en derin yol kadar bellek kullanır. Geniş ve sığ graflarda DFS, derin ve dar graflarda BFS daha ekonomiktir.
Bir de pratik uyarı: Çok derin graflarda özyinelemeli DFS yığın taşırabilir. Go'da goroutine yığınları büyüdüğü için sınır yüksektir ama sonsuz değildir. Girdi boyutu kontrolsüzse iteratif sürümü tercih et.
Gezinmenin üzerine kurulan algoritmalar
BFS ve DFS'i öğrenmek, graf algoritmalarının büyük kısmının kapısını açar. Çünkü geri kalanların çoğu, bu iki gezinmenin üzerine küçük eklemeler yapar. Hangi algoritmanın hangi temele dayandığını bilmek, yeni bir algoritma öğrenirken zihinsel yükü azaltır.
BFS'in üzerine kurulanlar. Ağırlıksız en kısa yol doğrudan BFS'tir. Kenar ağırlıkları yalnızca sıfır ve bir olabiliyorsa, kuyruk yerine çift uçlu kuyruk kullanmak yeterlidir: sıfır ağırlıklı kenarlar öne, bir ağırlıklılar arkaya eklenir. Ağırlıklar serbestse kuyruk yerine öncelik kuyruğu gelir ve elde ettiğin şey Dijkstra algoritmasıdır. Yani üç algoritma, aynı iskeletin farklı veri yapılarıyla kurulmuş hâlleridir.
DFS'in üzerine kurulanlar. Topolojik sıralama, DFS'in çıkış sırasının tersidir. Yönlü graflarda döngü tespiti, gezinme sırasında hâlâ yığında olan bir düğüme rastlamaktır. Güçlü bağlı bileşenler, iki DFS geçişiyle bulunur. Köprüler ve kesme noktaları, giriş zamanları ile geri kenarların karşılaştırılmasıyla belirlenir. Geri izleme algoritmalarının tamamı — bulmaca çözücüleri, permütasyon üretme, kısıt sağlama — DFS'in bir biçimidir.
İki gezinmeye de dayanmayan az sayıda algoritma vardır. Minimum kapsayan ağaç bulan Kruskal algoritması kenarları sıralar ve ayrık küme yapısı kullanır; gezinme yapmaz. Tüm çiftler arası en kısa yol bulan Floyd-Warshall ise üç iç içe döngüden ibarettir.
Bu haritayı akılda tutmanın pratik faydası şudur: Yeni bir graf problemiyle karşılaştığında, önce "bu bir gezinme problemi mi?" diye sorarsın. Cevap evetse, hangi gezinmenin uygun olduğunu ve hangi ek bilgiyi takip etmen gerektiğini belirlemek kalır. Bu iki karar, çözümün neredeyse tamamını verir.
Sık yapılan hatalar
- BFS'te ziyaret işaretini kuyruktan çıkarırken koymak. Aynı düğüm birden çok kez kuyruğa girer; ekleme anında işaretle.
- Yönsüz grafta ebeveyn kontrolünü atlamak. Her kenar döngü olarak bildirilir.
- Izgara sınırlarını kontrol etmemek. Negatif indeks veya taşma paniğe yol açar.
- DFS'i en kısa yol için kullanmak. DFS bir yol bulur, en kısa olanı değil.
- Birden çok bileşeni unutmak. Tek başlangıçtan yapılan gezinme yalnızca o bileşeni görür; tüm düğümleri döngüyle denemelisin.
- Ziyaret takibi için map yerine yavaş yapı kullanmak. Izgaralarda iki boyutlu boolean dizi çok daha hızlıdır.
- Çok kaynaklı problemde her kaynaktan ayrı BFS yapmak. Hepsini aynı kuyruğa koymak kaynak sayısı kadar hızlandırır.
Alıştırmalar
Bir kelimeden diğerine, her adımda yalnızca bir harf değiştirerek ve her ara kelime sözlükte bulunarak geçilebilir mi? En kısa dönüşüm zincirini bul.
İpucu
Her kelime bir düğüm, tek harf farkı olan kelimeler arasında kenar var. Grafı bellekte kurmaya gerek yok; komşuları gerektiğinde üret. En kısa zincir istendiği için BFS kullan.
Çözümü göster
package main
import (
"fmt"
"slices"
"strings"
)
// neighbors: tek harf değiştirerek üretilebilen sözlük kelimeleri
func neighbors(word string, dict map[string]bool) []string {
var out []string
r := []rune(word)
for i := range r {
original := r[i]
for c := 'a'; c <= 'z'; c++ {
if c == original {
continue
}
r[i] = c
candidate := string(r)
if dict[candidate] {
out = append(out, candidate)
}
}
r[i] = original
}
slices.Sort(out) // deterministik sıra
return out
}
// ladder: en kısa dönüşüm zinciri (BFS)
func ladder(start, end string, words []string) ([]string, bool) {
dict := make(map[string]bool, len(words))
for _, w := range words {
dict[w] = true
}
if !dict[end] {
return nil, false
}
if start == end {
return []string{start}, true
}
parent := map[string]string{start: ""}
queue := []string{start}
for len(queue) > 0 {
cur := queue[0]
queue = queue[1:]
for _, next := range neighbors(cur, dict) {
if _, seen := parent[next]; seen {
continue
}
parent[next] = cur
if next == end {
var path []string
for n := end; n != ""; n = parent[n] {
path = append(path, n)
}
slices.Reverse(path)
return path, true
}
queue = append(queue, next)
}
}
return nil, false
}
func main() {
words := []string{
"hit", "hot", "dot", "dog", "cog", "lot", "log",
"cat", "cot", "can", "ban", "bat",
}
cases := [][2]string{
{"hit", "cog"},
{"hit", "hot"},
{"cat", "ban"},
{"hit", "xyz"},
{"hit", "hit"},
}
fmt.Println("sözlük:", words)
fmt.Println()
for _, c := range cases {
path, ok := ladder(c[0], c[1], words)
if !ok {
fmt.Printf("%s → %s: dönüşüm YOK\n", c[0], c[1])
continue
}
fmt.Printf("%s → %s: %d adım\n", c[0], c[1], len(path)-1)
fmt.Println(" ", strings.Join(path, " → "))
}
fmt.Println()
fmt.Println("Not: Graf hiç kurulmadı; komşular gerektiğinde hesaplandı.")
fmt.Println("Bu, durum uzayı aramalarının tipik yaklaşımıdır.")
}sözlük: [hit hot dot dog cog lot log cat cot can ban bat] hit → cog: 3 adım hit → hot → cot → cog hit → hot: 1 adım hit → hot cat → ban: 2 adım cat → bat → ban hit → xyz: dönüşüm YOK hit → hit: 0 adım hit Not: Graf hiç kurulmadı; komşular gerektiğinde hesaplandı. Bu, durum uzayı aramalarının tipik yaklaşımıdır.
Bu problem, durum uzayı araması kalıbının güzel bir örneğidir: Graf bellekte hiç kurulmaz. Her kelime bir düğümdür ama düğüm listesini ve kenar listesini önceden hesaplamak yerine, bir düğümün komşularını gerektiğinde üretirsin. Bu yaklaşım, düğüm sayısı çok büyük ya da sonsuz olan problemlerde tek uygulanabilir yöntemdir — bulmaca çözücüleri, oyun ağaçları ve yapılandırma arama problemleri böyle çalışır.
Bir ızgarada her adanın alanını ve çevresini hesapla. En büyük alanlı ve en uzun çevreli adayı bul. Ayrıca bir su hücresini karaya çevirerek elde edilebilecek en büyük ada alanını hesapla.
İpucu
Çevre hesabı için her kara hücresinin kaç kenarının su veya ızgara dışına baktığını say. En büyük adayı bulmak için önce tüm adaları etiketle, sonra her su hücresi için komşu farklı adaların alanlarını topla.
Çözümü göster
package main
import "fmt"
var directions = [][2]int{{-1, 0}, {1, 0}, {0, -1}, {0, 1}}
type island struct {
id int
area int
perimeter int
}
// analyze: tüm adaları etiketler, alan ve çevrelerini hesaplar
func analyze(grid [][]byte) ([][]int, []island) {
rows, cols := len(grid), len(grid[0])
label := make([][]int, rows)
for i := range label {
label[i] = make([]int, cols)
}
var islands []island
nextID := 1
var dfs func(r, c, id int, isl *island)
dfs = func(r, c, id int, isl *island) {
label[r][c] = id
isl.area++
for _, d := range directions {
nr, nc := r+d[0], c+d[1]
// Izgara dışı veya su: bir çevre kenarı
if nr < 0 || nr >= rows || nc < 0 || nc >= cols || grid[nr][nc] == '0' {
isl.perimeter++
continue
}
if label[nr][nc] == 0 {
dfs(nr, nc, id, isl)
}
}
}
for r := range rows {
for c := range cols {
if grid[r][c] == '1' && label[r][c] == 0 {
isl := island{id: nextID}
dfs(r, c, nextID, &isl)
islands = append(islands, isl)
nextID++
}
}
}
return label, islands
}
// largestAfterOneFill: bir su hücresini karaya çevirerek en büyük ada
func largestAfterOneFill(grid [][]byte) (int, [2]int) {
rows, cols := len(grid), len(grid[0])
label, islands := analyze(grid)
areaByID := map[int]int{}
for _, isl := range islands {
areaByID[isl.id] = isl.area
}
best, bestCell := 0, [2]int{-1, -1}
for _, isl := range islands {
if isl.area > best {
best = isl.area // hiç doldurmasak da en büyük ada bu
}
}
for r := range rows {
for c := range cols {
if grid[r][c] != '0' {
continue
}
seen := map[int]bool{}
total := 1 // doldurulan hücrenin kendisi
for _, d := range directions {
nr, nc := r+d[0], c+d[1]
if nr < 0 || nr >= rows || nc < 0 || nc >= cols {
continue
}
id := label[nr][nc]
if id != 0 && !seen[id] {
seen[id] = true
total += areaByID[id]
}
}
if total > best {
best, bestCell = total, [2]int{r, c}
}
}
}
return best, bestCell
}
func toGrid(lines []string) [][]byte {
out := make([][]byte, len(lines))
for i, l := range lines {
out[i] = []byte(l)
}
return out
}
func main() {
grid := toGrid([]string{
"11000",
"11000",
"00100",
"00011",
})
fmt.Println("harita:")
for _, row := range grid {
fmt.Println(" " + string(row))
}
label, islands := analyze(grid)
fmt.Println()
fmt.Println("ada etiketleri:")
for _, row := range label {
for _, v := range row {
fmt.Printf("%3d", v)
}
fmt.Println()
}
fmt.Println()
fmt.Printf("%6s %8s %10s\n", "ada", "alan", "çevre")
maxArea, maxPerim := 0, 0
for _, isl := range islands {
fmt.Printf("%6d %8d %10d\n", isl.id, isl.area, isl.perimeter)
maxArea = max(maxArea, isl.area)
maxPerim = max(maxPerim, isl.perimeter)
}
fmt.Println("en büyük alan:", maxArea, "| en uzun çevre:", maxPerim)
best, cell := largestAfterOneFill(grid)
fmt.Println()
fmt.Println("bir su hücresi doldurularak elde edilebilecek en büyük ada:", best)
if cell[0] != -1 {
fmt.Printf("doldurulacak hücre: (%d,%d)\n", cell[0], cell[1])
}
fmt.Println()
single := toGrid([]string{"1"})
_, isl := analyze(single)
fmt.Println("tek kara hücresi: alan =", isl[0].area, "çevre =", isl[0].perimeter)
allWater := toGrid([]string{"000", "000"})
_, none := analyze(allWater)
fmt.Println("tamamen su: ada sayısı =", len(none))
}harita:
11000
11000
00100
00011
ada etiketleri:
1 1 0 0 0
1 1 0 0 0
0 0 2 0 0
0 0 0 3 3
ada alan çevre
1 4 8
2 1 4
3 2 6
en büyük alan: 4 | en uzun çevre: 8
bir su hücresi doldurularak elde edilebilecek en büyük ada: 6
doldurulacak hücre: (1,2)
tek kara hücresi: alan = 1 çevre = 4
tamamen su: ada sayısı = 0İkinci bölümdeki teknik dikkate değer: Her su hücresi için komşu adaların alanlarını toplamak, ama aynı adayı iki kez saymamak. Bir su hücresinin iki komşusu aynı adaya ait olabilir; bu yüzden ada kimliklerini bir kümede takip etmek gerekir. Etiketleme adımını önceden yapmak, bu sorguyu her hücre için sabit sürede yanıtlamayı sağlar.
Naif yaklaşım — her su hücresini doldurup adaları baştan saymak — O((R×C)²) olurdu. Önceden etiketleme, problemi doğrusal hâle getirir. Bu, "bir kez hesapla, çok kez kullan" fikrinin tipik uygulamasıdır.
Bir grafın iki parçalı olup olmadığını BFS ile kontrol et. İki parçalıysa renklendirmeyi göster; değilse çelişkiye yol açan tek uzunluklu döngüyü bul. Birden çok bileşen olabileceğini hesaba kat.
İpucu
BFS ile gezerken her komşuya kendi renginin tersini ver. Aynı renkte iki komşu bulursan graf iki parçalı değildir; o iki düğümün köklerine giden yolları birleştirerek tek uzunluklu döngüyü bulabilirsin.
Çözümü göster
package main
import (
"fmt"
"maps"
"slices"
)
type Graph map[string][]string
func (g Graph) AddEdge(a, b string) {
g[a] = append(g[a], b)
g[b] = append(g[b], a)
slices.Sort(g[a])
slices.Sort(g[b])
}
func (g Graph) AddNode(n string) {
if _, ok := g[n]; !ok {
g[n] = nil
}
}
func (g Graph) Nodes() []string { return slices.Sorted(maps.Keys(g)) }
// isBipartite: iki renkle boyanabilir mi + çelişki yolu
func (g Graph) isBipartite() (bool, map[string]int, []string) {
color := map[string]int{}
parent := map[string]string{}
for _, start := range g.Nodes() {
if _, done := color[start]; done {
continue
}
color[start] = 0
parent[start] = ""
queue := []string{start}
for len(queue) > 0 {
cur := queue[0]
queue = queue[1:]
for _, next := range g[cur] {
c, seen := color[next]
if !seen {
color[next] = 1 - color[cur]
parent[next] = cur
queue = append(queue, next)
continue
}
if c != color[cur] {
continue // farklı renk: sorun yok
}
// Aynı renkte iki komşu: tek uzunluklu döngü var
return false, nil, oddCycle(parent, cur, next)
}
}
}
return true, color, nil
}
// oddCycle: iki düğümün ortak atasına kadar olan yolları birleştirir
func oddCycle(parent map[string]string, a, b string) []string {
pathA := pathToRoot(parent, a)
pathB := pathToRoot(parent, b)
// Ortak atayı bul
inA := map[string]int{}
for i, n := range pathA {
inA[n] = i
}
commonIdx := -1
var common string
for _, n := range pathB {
if i, ok := inA[n]; ok {
commonIdx, common = i, n
break
}
}
if commonIdx == -1 {
return []string{a, b}
}
cycle := slices.Clone(pathA[:commonIdx+1])
slices.Reverse(cycle) // ortak atadan a'ya
// b'den ortak ataya olan yolu ekle (ters sırada, ortak atayı atla)
var tail []string
for _, n := range pathB {
if n == common {
break
}
tail = append(tail, n)
}
cycle = append(cycle, tail...)
cycle = append(cycle, common)
return cycle
}
func pathToRoot(parent map[string]string, node string) []string {
var path []string
for n := node; n != ""; n = parent[n] {
path = append(path, n)
}
return path
}
func report(name string, g Graph) {
ok, color, cycle := g.isBipartite()
fmt.Println(name)
fmt.Println(" düğümler:", g.Nodes())
fmt.Println(" iki parçalı:", ok)
if ok {
var groupA, groupB []string
for _, n := range g.Nodes() {
if color[n] == 0 {
groupA = append(groupA, n)
} else {
groupB = append(groupB, n)
}
}
fmt.Println(" grup 1:", groupA)
fmt.Println(" grup 2:", groupB)
} else {
fmt.Println(" tek uzunluklu döngü:", cycle, "→ uzunluk:", len(cycle)-1)
}
fmt.Println()
}
func main() {
// Kare: 4-döngü → iki parçalı
square := Graph{}
for _, e := range [][2]string{{"A", "B"}, {"B", "C"}, {"C", "D"}, {"D", "A"}} {
square.AddEdge(e[0], e[1])
}
report("KARE (4-döngü):", square)
// Üçgen: 3-döngü → iki parçalı değil
triangle := Graph{}
for _, e := range [][2]string{{"A", "B"}, {"B", "C"}, {"C", "A"}} {
triangle.AddEdge(e[0], e[1])
}
report("ÜÇGEN (3-döngü):", triangle)
// Ağaç: her ağaç iki parçalıdır
tree := Graph{}
for _, e := range [][2]string{{"A", "B"}, {"A", "C"}, {"B", "D"}, {"B", "E"}, {"C", "F"}} {
tree.AddEdge(e[0], e[1])
}
report("AĞAÇ:", tree)
// Çok bileşenli: biri iki parçalı, diğeri değil
mixed := Graph{}
for _, e := range [][2]string{{"A", "B"}, {"C", "D"}, {"D", "E"}, {"E", "C"}} {
mixed.AddEdge(e[0], e[1])
}
mixed.AddNode("F")
report("KARIŞIK (bir bileşende üçgen var):", mixed)
fmt.Println("TEOREM: Bir graf ancak ve ancak tek uzunluklu döngü")
fmt.Println("içermiyorsa iki parçalıdır.")
fmt.Println("Ağaçlar hiç döngü içermediği için her zaman iki parçalıdır.")
}KARE (4-döngü): düğümler: [A B C D] iki parçalı: true grup 1: [A C] grup 2: [B D] ÜÇGEN (3-döngü): düğümler: [A B C] iki parçalı: false tek uzunluklu döngü: [A B C A] → uzunluk: 3 AĞAÇ: düğümler: [A B C D E F] iki parçalı: true grup 1: [A D E F] grup 2: [B C] KARIŞIK (bir bileşende üçgen var): düğümler: [A B C D E F] iki parçalı: false tek uzunluklu döngü: [C D E C] → uzunluk: 3 TEOREM: Bir graf ancak ve ancak tek uzunluklu döngü içermiyorsa iki parçalıdır. Ağaçlar hiç döngü içermediği için her zaman iki parçalıdır.
İki parçalılık testi, BFS'in yalnızca gezinme değil doğrulama aracı olarak da kullanılabileceğini gösteriyor. Renklendirme sırasında bir çelişki bulmak, grafın yapısal bir özelliğini kanıtlar: tek uzunluklu bir döngü vardır.
Çelişki yolunu geri oluşturmak, BFS ağacının parent bilgisini kullanmayı gerektirir. İki çakışan düğümden köke giden yolları bulup ortak atalarında birleştirirsen elde ettiğin döngünün uzunluğu mutlaka tektir — çünkü iki düğüm aynı renkte, yani köke uzaklıkları aynı pariteye sahip.
İki parçalı graflar pratikte çok karşımıza çıkar: öğrenci-ders, iş-makine, kullanıcı-ürün ilişkileri. Bu yapı üzerine kurulan eşleştirme algoritmaları, atama ve planlama problemlerinin temelini oluşturur.
Kısa sınav
BFS hangi veri yapısını kullanır ve ne garanti eder?
BFS'te ziyaret işareti ne zaman konmalıdır?
Yönsüz grafta DFS ile döngü tespit ederken hangi kontrol gereklidir?
Çok kaynaklı BFS ne sağlar?
BFS ile DFS'in bellek kullanımı nasıl karşılaştırılır?
Bir grafın tüm bileşenlerini gezmek için ne yapmak gerekir?
Özet
- BFS kuyruk kullanır, katman katman ilerler ve ağırlıksız grafta en kısa yolu bulur.
- DFS yığın (veya özyineleme) kullanır, derine dalar ve yapısal analizler için doğaldır.
- Her ikisi de O(V + E) zaman ve O(V) bellek kullanır.
- BFS'te ziyaret işareti kuyruğa eklerken konmalıdır.
- Yolu geri oluşturmak için her düğümün ebeveyni kaydedilir ve hedeften başlangıca yürünür.
- Izgaralar örtük graflardır; komşular formülle hesaplanır ve graf hiç kurulmaz.
- Yönsüz grafta döngü tespitinde ebeveyne geri bakma yok sayılmalıdır.
- Çok kaynaklı BFS, tüm kaynakları aynı kuyruğa koyarak "en yakın kaynağa uzaklık" haritasını tek geçişte üretir.
- Tüm bileşenleri gezmek için her düğümü başlangıç olarak denemek gerekir.
- En kısa yol veya katman bilgisi gerekiyorsa BFS; yapı analizi, döngü veya geri izleme gerekiyorsa DFS seçilir.