Graflar

Ağaçlar hiyerarşiyi modellemekte mükemmeldi ama katı bir kuralları vardı: Her düğümün tek bir ebeveyni olabilir ve döngü bulunamaz. Gerçek dünyadaki pek çok ilişki bu kalıba sığmaz. İki şehir arasında birden fazla yol vardır, bir kişi birden fazla kişiyle arkadaştır, bir görev birden fazla göreve bağlı olabilir ve bu bağımlılıklar birbirine dolanabilir.

Graf, bu kısıtları tamamen kaldıran yapıdır: Düğümler ve aralarındaki kenarlardan ibarettir. Bu kadar genel olması, onu bilgisayar biliminin en güçlü modelleme aracı yapar. Sosyal ağlar, haritalar, internet, bağımlılık yönetimi, devre tasarımı, öneri sistemleri, derleyicilerin kod analizi — hepsi graf problemleridir. Aslında ağaçlar da graflardır: döngüsüz ve bağlantılı özel bir türü.

Bu ders, graf algoritmalarına geçmeden önceki temeli kurar. Terminolojiyi, yönlü ve ağırlıklı graf ayrımını, üç temel temsil yöntemini ve bunların ödünleşmelerini öğreneceksin. Temsil seçimi göründüğünden önemlidir: Yanlış temsil, sonraki tüm algoritmaların karmaşıklığını olumsuz etkiler.

Terminoloji

Yönsüz graf                    Yönlü graf (digraf)

    A ─── B                        A ──► B
    │   ╱ │                        │   ╱ │
    │  ╱  │                        ▼  ▼  ▼
    C ─── D                        C ──► D

kenar: {A,B} çift yönlü         kenar: (A,B) tek yönlü

İki büyüklük tüm graf analizinde tekrar tekrar karşına çıkar: V (düğüm sayısı) ve E (kenar sayısı). Aralarındaki ilişki, hangi temsilin ve hangi algoritmanın uygun olduğunu belirler.

n düğümlü bir grafta en fazla kaç kenar olabilir?

yönsüz : n(n−1)/2       → n=1000 için ~500.000
yönlü  : n(n−1)         → n=1000 için ~999.000

seyrek graf : E ≈ V        (sosyal ağlar, yol haritaları)
yoğun graf  : E ≈ V²       (tam bağlantılı ağlar)

Gerçek dünyadaki grafların büyük çoğunluğu seyrektir. Bir sosyal ağda milyarlarca kullanıcı vardır ama kimsenin milyarlarca arkadaşı yoktur. Bu gözlem, temsil seçiminin cevabını da büyük ölçüde verir.

Aşağıdaki görselleştirmede bir graf üzerinde gezinmeyi adım adım izleyebilirsin; kenarların ve ziyaret sırasının nasıl belirlendiğine dikkat et:

Komşuluk matrisi

İlk temsil, V×V boyutunda bir tablo tutar: matrix[i][j], i'den j'ye kenar olup olmadığını söyler.

    A B C D                Yönsüz graf: matris SİMETRİKTİR
A [ 0 1 1 0 ]              A─B, A─C, B─C, B─D, C─D
B [ 1 0 1 1 ]
C [ 1 1 0 1 ]              matrix[i][j] == matrix[j][i]
D [ 0 1 1 0 ]

package main

import (
	"fmt"
	"strings"
)

type MatrixGraph struct {
	names    []string
	index    map[string]int
	matrix   [][]int // 0 = kenar yok, >0 = ağırlık
	directed bool
}

func NewMatrixGraph(names []string, directed bool) *MatrixGraph {
	g := &MatrixGraph{
		names:    names,
		index:    make(map[string]int, len(names)),
		matrix:   make([][]int, len(names)),
		directed: directed,
	}
	for i, n := range names {
		g.index[n] = i
		g.matrix[i] = make([]int, len(names))
	}
	return g
}

// AddEdge: O(1)
func (g *MatrixGraph) AddEdge(from, to string, weight int) {
	i, j := g.index[from], g.index[to]
	g.matrix[i][j] = weight
	if !g.directed {
		g.matrix[j][i] = weight
	}
}

// HasEdge: O(1) — matrisin en güçlü yanı
func (g *MatrixGraph) HasEdge(from, to string) bool {
	return g.matrix[g.index[from]][g.index[to]] != 0
}

// Neighbors: O(V) — tüm satırı taramak gerekir
func (g *MatrixGraph) Neighbors(node string) []string {
	i := g.index[node]
	var out []string
	for j, w := range g.matrix[i] {
		if w != 0 {
			out = append(out, g.names[j])
		}
	}
	return out
}

func (g *MatrixGraph) Degree(node string) int {
	return len(g.Neighbors(node))
}

func (g *MatrixGraph) String() string {
	var sb strings.Builder
	sb.WriteString("    ")
	for _, n := range g.names {
		fmt.Fprintf(&sb, "%-3s", n)
	}
	sb.WriteString("\n")
	for i, row := range g.matrix {
		fmt.Fprintf(&sb, "%-3s ", g.names[i])
		for _, w := range row {
			fmt.Fprintf(&sb, "%-3d", w)
		}
		sb.WriteString("\n")
	}
	return sb.String()
}

func main() {
	g := NewMatrixGraph([]string{"A", "B", "C", "D"}, false)
	g.AddEdge("A", "B", 1)
	g.AddEdge("A", "C", 1)
	g.AddEdge("B", "C", 1)
	g.AddEdge("B", "D", 1)
	g.AddEdge("C", "D", 1)

	fmt.Print(g.String())
	fmt.Println("A-B kenarı var mı:", g.HasEdge("A", "B"))
	fmt.Println("A-D kenarı var mı:", g.HasEdge("A", "D"))
	fmt.Println("B'nin komşuları:", g.Neighbors("B"), "| derece:", g.Degree("B"))

	// Ağırlıklı ve yönlü graf
	fmt.Println()
	roads := NewMatrixGraph([]string{"Ankara", "İzmir", "Bursa"}, true)
	roads.AddEdge("Ankara", "İzmir", 588)
	roads.AddEdge("Ankara", "Bursa", 385)
	roads.AddEdge("Bursa", "İzmir", 330)

	fmt.Print(roads.String())
	fmt.Println("Ankara → İzmir var mı:", roads.HasEdge("Ankara", "İzmir"))
	fmt.Println("İzmir → Ankara var mı:", roads.HasEdge("İzmir", "Ankara"), "← yönlü graf")
	fmt.Println("bellek kullanımı: V² =", len(roads.names)*len(roads.names), "hücre")
}

A  B  C  D
A   0  1  1  0
B   1  0  1  1
C   1  1  0  1
D   0  1  1  0
A-B kenarı var mı: true
A-D kenarı var mı: false
B'nin komşuları: [A C D] | derece: 3

    AnkaraİzmirBursa
Ankara 0  588385
İzmir 0  0  0
Bursa 0  3300
Ankara → İzmir var mı: true
İzmir → Ankara var mı: false ← yönlü graf
bellek kullanımı: V² = 9 hücre

Matrisin avantajı nettir: Kenar var mı sorusu tek bir dizi erişimiyle yanıtlanır. Dezavantajı ise bellek kullanımıdır — düğüm sayısının karesi kadar yer kaplar, kenar olsun olmasın. Bir milyon düğümlü seyrek bir graf için matris kullanmak bir trilyon hücre demektir; yani imkânsız.

Komşuluk listesi

İkinci temsil, her düğüm için yalnızca gerçekten var olan komşuları saklar:

A: [B, C]
B: [A, C, D]
C: [A, B, D]
D: [B, C]

Bellek: O(V + E) — kenar yoksa yer kaplamaz

package main

import (
	"fmt"
	"maps"
	"slices"
)

type Edge struct {
	To     string
	Weight int
}

type ListGraph struct {
	adj      map[string][]Edge
	directed bool
}

func NewListGraph(directed bool) *ListGraph {
	return &ListGraph{adj: map[string][]Edge{}, directed: directed}
}

func (g *ListGraph) AddNode(name string) {
	if _, ok := g.adj[name]; !ok {
		g.adj[name] = nil
	}
}

// AddEdge: O(1)
func (g *ListGraph) AddEdge(from, to string, weight int) {
	g.AddNode(from)
	g.AddNode(to)
	g.adj[from] = append(g.adj[from], Edge{To: to, Weight: weight})
	if !g.directed {
		g.adj[to] = append(g.adj[to], Edge{To: from, Weight: weight})
	}
}

// Neighbors: O(derece) — matristen çok daha hızlı
func (g *ListGraph) Neighbors(node string) []Edge {
	return g.adj[node]
}

// HasEdge: O(derece) — matristen daha yavaş
func (g *ListGraph) HasEdge(from, to string) bool {
	for _, e := range g.adj[from] {
		if e.To == to {
			return true
		}
	}
	return false
}

func (g *ListGraph) Nodes() []string {
	return slices.Sorted(maps.Keys(g.adj))
}

func (g *ListGraph) EdgeCount() int {
	total := 0
	for _, edges := range g.adj {
		total += len(edges)
	}
	if !g.directed {
		return total / 2 // her kenar iki kez sayıldı
	}
	return total
}

func (g *ListGraph) Degree(node string) int { return len(g.adj[node]) }

// InDegree: yönlü grafta gelen kenar sayısı — O(V + E)
func (g *ListGraph) InDegree(node string) int {
	count := 0
	for _, edges := range g.adj {
		for _, e := range edges {
			if e.To == node {
				count++
			}
		}
	}
	return count
}

func main() {
	social := NewListGraph(false)
	social.AddEdge("Ayşe", "Mehmet", 1)
	social.AddEdge("Ayşe", "Zeynep", 1)
	social.AddEdge("Mehmet", "Can", 1)
	social.AddEdge("Zeynep", "Can", 1)
	social.AddNode("Deniz") // arkadaşı olmayan düğüm

	fmt.Println("düğümler:", social.Nodes())
	fmt.Println("kenar sayısı:", social.EdgeCount())

	for _, n := range social.Nodes() {
		var names []string
		for _, e := range social.Neighbors(n) {
			names = append(names, e.To)
		}
		slices.Sort(names)
		fmt.Printf("  %-7s derece=%d komşular=%v\n", n, social.Degree(n), names)
	}

	// Yönlü ve ağırlıklı: görev bağımlılıkları
	fmt.Println()
	deps := NewListGraph(true)
	deps.AddEdge("tasarım", "geliştirme", 3)
	deps.AddEdge("geliştirme", "test", 5)
	deps.AddEdge("geliştirme", "belgeleme", 2)
	deps.AddEdge("test", "yayın", 1)
	deps.AddEdge("belgeleme", "yayın", 1)

	fmt.Println("bağımlılık grafı:")
	for _, n := range deps.Nodes() {
		fmt.Printf("  %-12s giden=%d gelen=%d →", n, deps.Degree(n), deps.InDegree(n))
		for _, e := range deps.Neighbors(n) {
			fmt.Printf(" %s(%d gün)", e.To, e.Weight)
		}
		fmt.Println()
	}
}

düğümler: [Ayşe Can Deniz Mehmet Zeynep]
kenar sayısı: 4
  Ayşe    derece=2 komşular=[Mehmet Zeynep]
  Can     derece=2 komşular=[Mehmet Zeynep]
  Deniz   derece=0 komşular=[]
  Mehmet  derece=2 komşular=[Ayşe Can]
  Zeynep  derece=2 komşular=[Ayşe Can]

bağımlılık grafı:
  belgeleme    giden=1 gelen=1 → yayın(1 gün)
  geliştirme   giden=2 gelen=1 → test(5 gün) belgeleme(2 gün)
  tasarım      giden=1 gelen=0 → geliştirme(3 gün)
  test         giden=1 gelen=1 → yayın(1 gün)
  yayın        giden=0 gelen=2 →

Komşuluk listesi, pratikte en çok kullanılan temsildir ve sebebi basittir: Gerçek graflar seyrektir ve algoritmaların çoğu "bu düğümün komşuları kimler?" sorusunu sorar — matriste O(V), listede O(derece).

Go'da komşuluk listesini map[string][]Edge ile tutmak okunabilirlik açısından rahattır. Performans kritikse düğümleri tamsayıya eşleyip [][]Edge kullanmak daha hızlıdır: hash hesabı ortadan kalkar ve bellek bitişik olur.

Kenar listesi

Üçüncü temsil en sadesidir: Yalnızca kenarların bir listesi.

package main

import (
	"fmt"
	"slices"
)

type Edge struct {
	From, To string
	Weight   int
}

type EdgeListGraph struct {
	edges []Edge
	nodes map[string]bool
}

func NewEdgeListGraph() *EdgeListGraph {
	return &EdgeListGraph{nodes: map[string]bool{}}
}

func (g *EdgeListGraph) AddEdge(from, to string, weight int) {
	g.edges = append(g.edges, Edge{From: from, To: to, Weight: weight})
	g.nodes[from] = true
	g.nodes[to] = true
}

// SortedByWeight: Kruskal algoritmasının ilk adımı
func (g *EdgeListGraph) SortedByWeight() []Edge {
	out := slices.Clone(g.edges)
	slices.SortFunc(out, func(a, b Edge) int {
		if a.Weight != b.Weight {
			return a.Weight - b.Weight
		}
		if a.From != b.From {
			return cmpString(a.From, b.From)
		}
		return cmpString(a.To, b.To)
	})
	return out
}

func cmpString(a, b string) int {
	switch {
	case a < b:
		return -1
	case a > b:
		return 1
	}
	return 0
}

// ToAdjacency: kenar listesinden komşuluk listesine dönüşüm — O(E)
func (g *EdgeListGraph) ToAdjacency() map[string][]string {
	adj := make(map[string][]string, len(g.nodes))
	for n := range g.nodes {
		adj[n] = nil
	}
	for _, e := range g.edges {
		adj[e.From] = append(adj[e.From], e.To)
		adj[e.To] = append(adj[e.To], e.From)
	}
	for n := range adj {
		slices.Sort(adj[n])
	}
	return adj
}

func main() {
	g := NewEdgeListGraph()
	g.AddEdge("A", "B", 4)
	g.AddEdge("A", "C", 2)
	g.AddEdge("B", "C", 1)
	g.AddEdge("B", "D", 5)
	g.AddEdge("C", "D", 8)
	g.AddEdge("C", "E", 10)
	g.AddEdge("D", "E", 2)

	fmt.Println("ağırlığa göre sıralı kenarlar:")
	for _, e := range g.SortedByWeight() {
		fmt.Printf("  %s-%s: %d\n", e.From, e.To, e.Weight)
	}

	fmt.Println()
	fmt.Println("düğüm sayısı:", len(g.nodes), "| kenar sayısı:", len(g.edges))

	fmt.Println()
	fmt.Println("komşuluk listesine dönüştürülmüş hâli:")
	adj := g.ToAdjacency()
	for _, n := range slices.Sorted(slicesKeys(adj)) {
		fmt.Printf("  %s: %v\n", n, adj[n])
	}
}

func slicesKeys(m map[string][]string) func(func(string) bool) {
	return func(yield func(string) bool) {
		for k := range m {
			if !yield(k) {
				return
			}
		}
	}
}

ağırlığa göre sıralı kenarlar:
  B-C: 1
  A-C: 2
  D-E: 2
  A-B: 4
  B-D: 5
  C-D: 8
  C-E: 10

düğüm sayısı: 5 | kenar sayısı: 7

komşuluk listesine dönüştürülmüş hâli:
  A: [B C]
  B: [A C D]
  C: [A B D E]
  D: [B C E]
  E: [C D]

Kenar listesi tek başına komşu sorgusu için kötüdür — her sorguda tüm listeyi taraman gerekir. Ama iki durumda vazgeçilmezdir. Birincisi, kenarları ağırlığa göre işleyen algoritmalar: Minimum kapsayan ağaç bulan Kruskal algoritması tam olarak bu biçimi ister. İkincisi, grafı diskte saklamak veya ağ üzerinden aktarmak: En kompakt gösterim budur.

Temsil seçimi

Üç temsili yan yana koyduğunda seçim ölçütleri netleşir:

Pratik kural şudur: Varsayılan olarak komşuluk listesi kullan. Gerçek grafların çoğu seyrektir ve algoritmaların çoğu komşu gezinmeye dayanır. Matrisi yalnızca graf gerçekten yoğunsa, düğüm sayısı küçükse ya da algoritma matris çarpımı gibi işlemler gerektiriyorsa tercih et. Kenar listesini ise kenarları bir bütün olarak sıralaman ya da işlemen gerektiğinde kullan.

Bir başka pratik nokta: Bu üç temsil arasında dönüşüm ucuzdur. Kenar listesinden komşuluk listesi kurmak tek bir geçiş alır. Bu yüzden veriyi en doğal biçimde sakla, algoritmanın istediği biçime ihtiyaç anında dönüştür.

Graflarla çalışırken

Graf kodu yazarken karşılaşacağın sorunların çoğu algoritmadan değil, modellemeden kaynaklanır. Birkaç pratik uyarı işe yarar.

Yön konusunu baştan netleştir. "Arkadaşlık" yönsüzdür ama "takip etme" yönlüdür. Yönsüz bir grafı yönlü bir yapıyla modelliyorsan her kenarı iki kez eklemen gerekir; bunu unutmak, algoritmanın grafın yarısını görememesine yol açar ve hata ayıklaması zor bir durumdur.

Yalıtılmış düğümleri unutma. Yalnızca kenar ekleyerek graf kuruyorsan, hiçbir kenarı olmayan düğümler hiç var olmaz. Bileşen sayma gibi problemlerde bu, yanlış sonuçlar üretir. Düğümleri ayrıca kaydetmek iyi bir alışkanlıktır.

Kendine döngü ve çoklu kenar mümkün mü? Bir düğümden kendisine giden kenar ya da aynı iki düğüm arasında birden fazla kenar bazı modellerde anlamlıdır, bazılarında hatadır. Algoritmanı yazmadan önce bu soruyu yanıtla; pek çok algoritma bu durumlarda sessizce yanlış çalışır.

Ağırlıklar negatif olabilir mi? Bu, algoritma seçimini doğrudan belirler. Bazı en kısa yol algoritmaları negatif ağırlıklarla çalışmaz ve yanlış cevap verir — hata da vermezler, sadece yanlış sonuç döndürürler.

Graf bağlantılı mı? Tek bir düğümden başlayan bir gezinme, yalnızca o düğümün bileşenini görür. Grafın tamamını işlemen gerekiyorsa her düğümü başlangıç noktası olarak denemeyi unutma.

Bu soruları baştan yanıtlamak, sonraki derslerde göreceğin algoritmaları uygularken karşılaşacağın hataların büyük kısmını önler. Gezinme algoritmalarını BFS ve DFS, en kısa yolu En Kısa Yol, bağlantılılığı Union-Find derslerinde ayrıntısıyla işliyoruz.

Graf problemlerini tanımak

Bir problemin graf problemi olduğunu fark etmek, çözümün yarısıdır. Bunu görmek başta zordur çünkü problem metni nadiren "graf" kelimesini kullanır. Aşağıdaki işaretler, bir problemin graf olarak modellenebileceğini gösterir.

İlişkiler var mı? Problemde nesneler ve aralarındaki bağlantılar geçiyorsa, nesneler düğüm, bağlantılar kenardır. Arkadaşlıklar, uçuşlar, bağımlılıklar, dönüşümler, benzerlikler — hepsi kenar olarak modellenir.

"Ulaşılabilir mi" sorusu soruluyorsa. Bir durumdan başka bir duruma gidilip gidilemeyeceği, bir labirentin çıkışı olup olmadığı, iki kişinin tanışıklık zinciriyle bağlanıp bağlanmadığı — hepsi aynı sorudur ve gezinme algoritmalarıyla yanıtlanır.

"En az kaç adımda" sorusu soruluyorsa. Adımların hepsi eşit maliyetliyse genişlik öncelikli arama yeterlidir; adımların maliyeti farklıysa en kısa yol algoritmaları gerekir.

Sıralama kısıtları varsa. "A'dan önce B yapılmalı" biçimindeki kurallar, yönlü kenarlar olarak modellenir ve geçerli bir sıra bulmak topolojik sıralama problemidir.

Durum uzayı aramaları. Bu, en sık kaçırılan modellemedir. Bir bulmacanın her olası konumu bir düğüm, her geçerli hamle bir kenardır. Sekiz taş bulmacası, su doldurma problemleri ve kelime dönüştürme oyunları böyle çözülür. Graf bellekte hiç kurulmaz; komşular gerektiğinde hesaplanır.

Gruplama ve bileşenler. "Kaç ayrı küme var", "bunlar aynı gruba mı ait" soruları bağlantılı bileşen problemleridir ve gezinme ya da ayrık küme yapısıyla çözülür.

Bu kalıpları tanımaya başladığında, ilk bakışta birbiriyle alakasız görünen pek çok problemin aynı birkaç algoritmayla çözüldüğünü fark edersin. Graf teorisinin cazibesi tam olarak budur: Az sayıda araçla çok geniş bir problem ailesini kapsar.

Sık yapılan hatalar

• Yönsüz grafta kenarı tek yönlü eklemek. Her iki komşuluk listesine de eklenmelidir.
• Seyrek graf için matris kullanmak. V² bellek, büyük graflarda hızla imkânsız hâle gelir.
• Yalıtılmış düğümleri kaydetmemek. Yalnızca kenarlardan kurulan graf, komşusuz düğümleri kaybeder.
• Yönsüz grafta kenar sayısını iki kez saymak. Komşuluk listesindeki toplam, kenar sayısının iki katıdır.
• Grafın bağlantılı olduğunu varsaymak. Tek bir başlangıçtan yapılan gezinme diğer bileşenleri görmez.
• Map tabanlı temsili performans kritik kodda kullanmak. Düğümleri tamsayıya eşlemek belirgin hız kazandırır.
• Negatif ağırlık olasılığını göz ardı etmek. Algoritma seçimini doğrudan etkiler.

Alıştırmalar

package main

import (
	"fmt"
	"maps"
	"slices"
)

type Graph struct {
	adj map[string][]string
}

func NewGraph() *Graph { return &Graph{adj: map[string][]string{}} }

func (g *Graph) AddNode(n string) {
	if _, ok := g.adj[n]; !ok {
		g.adj[n] = nil
	}
}

func (g *Graph) AddEdge(a, b string) {
	g.AddNode(a)
	g.AddNode(b)
	g.adj[a] = append(g.adj[a], b)
	g.adj[b] = append(g.adj[b], a)
}

func (g *Graph) EdgeCount() int {
	total := 0
	for _, e := range g.adj {
		total += len(e)
	}
	return total / 2
}

func main() {
	g := NewGraph()
	edges := [][2]string{
		{"A", "B"}, {"A", "C"}, {"B", "C"},
		{"B", "D"}, {"C", "D"}, {"D", "E"},
	}
	for _, e := range edges {
		g.AddEdge(e[0], e[1])
	}
	g.AddNode("F") // yalıtılmış düğüm

	nodes := slices.Sorted(maps.Keys(g.adj))
	degreeSum := 0
	maxDegree, maxNode := -1, ""

	fmt.Println("derece dağılımı:")
	for _, n := range nodes {
		d := len(g.adj[n])
		degreeSum += d
		if d > maxDegree {
			maxDegree, maxNode = d, n
		}
		fmt.Printf("  %-3s derece=%d komşular=%v\n", n, d, slices.Sorted(slices.Values(g.adj[n])))
	}

	fmt.Println()
	fmt.Println("düğüm sayısı:", len(nodes))
	fmt.Println("kenar sayısı:", g.EdgeCount())
	fmt.Println("derece toplamı:", degreeSum)
	fmt.Println("el sıkışma önermesi (toplam == 2E):", degreeSum == 2*g.EdgeCount())
	fmt.Printf("ortalama derece: %.2f\n", float64(degreeSum)/float64(len(nodes)))
	fmt.Printf("en yüksek derece: %s (%d)\n", maxNode, maxDegree)

	// Yoğunluk: mevcut kenar / olası en fazla kenar
	v := len(nodes)
	maxEdges := v * (v - 1) / 2
	fmt.Printf("yoğunluk: %d/%d = %.2f → %s graf\n",
		g.EdgeCount(), maxEdges, float64(g.EdgeCount())/float64(maxEdges),
		map[bool]string{true: "seyrek", false: "yoğun"}[g.EdgeCount() < maxEdges/2])
}

derece dağılımı:
  A   derece=2 komşular=[B C]
  B   derece=3 komşular=[A C D]
  C   derece=3 komşular=[A B D]
  D   derece=3 komşular=[B C E]
  E   derece=1 komşular=[D]
  F   derece=0 komşular=[]

düğüm sayısı: 6
kenar sayısı: 6
derece toplamı: 12
el sıkışma önermesi (toplam == 2E): true
ortalama derece: 2.00
en yüksek derece: B (3)
yoğunluk: 6/15 = 0.40 → seyrek graf

package main

import (
	"fmt"
	"slices"
	"strings"
)

type Edge struct {
	From, To string
}

// edgesToAdjacency: O(V + E)
func edgesToAdjacency(edges []Edge, extraNodes []string) map[string][]string {
	adj := map[string][]string{}
	for _, n := range extraNodes {
		adj[n] = nil
	}
	for _, e := range edges {
		adj[e.From] = append(adj[e.From], e.To)
		adj[e.To] = append(adj[e.To], e.From)
	}
	for n := range adj {
		slices.Sort(adj[n])
	}
	return adj
}

// adjacencyToMatrix: O(V² + E)
func adjacencyToMatrix(adj map[string][]string) ([]string, [][]int) {
	names := make([]string, 0, len(adj))
	for n := range adj {
		names = append(names, n)
	}
	slices.Sort(names)

	index := make(map[string]int, len(names))
	for i, n := range names {
		index[n] = i
	}

	matrix := make([][]int, len(names))
	for i := range matrix {
		matrix[i] = make([]int, len(names))
	}
	for from, neighbors := range adj {
		for _, to := range neighbors {
			matrix[index[from]][index[to]] = 1
		}
	}
	return names, matrix
}

// matrixToEdges: O(V²)
func matrixToEdges(names []string, matrix [][]int) []Edge {
	var out []Edge
	for i := range matrix {
		for j := i + 1; j < len(matrix[i]); j++ { // üst üçgen: her kenar bir kez
			if matrix[i][j] != 0 {
				out = append(out, Edge{From: names[i], To: names[j]})
			}
		}
	}
	return out
}

func printMatrix(names []string, matrix [][]int) {
	var sb strings.Builder
	sb.WriteString("     ")
	for _, n := range names {
		fmt.Fprintf(&sb, "%-3s", n)
	}
	sb.WriteString("\n")
	for i, row := range matrix {
		fmt.Fprintf(&sb, "  %-3s", names[i])
		for _, v := range row {
			fmt.Fprintf(&sb, "%-3d", v)
		}
		sb.WriteString("\n")
	}
	fmt.Print(sb.String())
}

func main() {
	edges := []Edge{
		{"A", "B"}, {"A", "C"}, {"B", "C"}, {"B", "D"}, {"C", "D"},
	}

	fmt.Println("1) kenar listesi:")
	for _, e := range edges {
		fmt.Printf("  %s-%s\n", e.From, e.To)
	}

	adj := edgesToAdjacency(edges, []string{"E"}) // E yalıtılmış
	fmt.Println()
	fmt.Println("2) komşuluk listesi:")
	for _, n := range slices.Sorted(slices.Values(keysOf(adj))) {
		fmt.Printf("  %s: %v\n", n, adj[n])
	}

	names, matrix := adjacencyToMatrix(adj)
	fmt.Println()
	fmt.Println("3) komşuluk matrisi:")
	printMatrix(names, matrix)

	back := matrixToEdges(names, matrix)
	fmt.Println("matristen geri dönen kenarlar:", len(back), "adet")
	fmt.Println("özgün kenar sayısıyla aynı mı:", len(back) == len(edges))
}

func keysOf(m map[string][]string) []string {
	out := make([]string, 0, len(m))
	for k := range m {
		out = append(out, k)
	}
	return out
}

1) kenar listesi:
  A-B
  A-C
  B-C
  B-D
  C-D

2) komşuluk listesi:
  A: [B C]
  B: [A C D]
  C: [A B D]
  D: [B C]
  E: []

3) komşuluk matrisi:
     A  B  C  D  E
  A  0  1  1  0  0
  B  1  0  1  1  0
  C  1  1  0  1  0
  D  0  1  1  0  0
  E  0  0  0  0  0
matristen geri dönen kenarlar: 5 adet
özgün kenar sayısıyla aynı mı: true

package main

import (
	"fmt"
	"maps"
	"slices"
)

type Graph struct {
	adj map[string][]string
}

func NewGraph() *Graph { return &Graph{adj: map[string][]string{}} }

func (g *Graph) AddNode(n string) {
	if _, ok := g.adj[n]; !ok {
		g.adj[n] = nil
	}
}

func (g *Graph) AddEdge(a, b string) {
	g.AddNode(a)
	g.AddNode(b)
	g.adj[a] = append(g.adj[a], b)
	if a != b { // kendine döngüyü iki kez ekleme
		g.adj[b] = append(g.adj[b], a)
	}
}

func (g *Graph) Nodes() []string { return slices.Sorted(maps.Keys(g.adj)) }

// hasSelfLoop: bir düğüm kendi komşuları arasında mı
func (g *Graph) hasSelfLoop() bool {
	for n, neighbors := range g.adj {
		if slices.Contains(neighbors, n) {
			return true
		}
	}
	return false
}

// hasMultiEdge: aynı komşu birden fazla kez geçiyor mu
func (g *Graph) hasMultiEdge() bool {
	for _, neighbors := range g.adj {
		seen := map[string]bool{}
		for _, to := range neighbors {
			if seen[to] {
				return true
			}
			seen[to] = true
		}
	}
	return false
}

// isConnected: BFS ile tüm düğümlere ulaşılabiliyor mu
func (g *Graph) isConnected() bool {
	nodes := g.Nodes()
	if len(nodes) == 0 {
		return true
	}
	visited := map[string]bool{nodes[0]: true}
	queue := []string{nodes[0]}

	for len(queue) > 0 {
		cur := queue[0]
		queue = queue[1:]
		for _, next := range g.adj[cur] {
			if !visited[next] {
				visited[next] = true
				queue = append(queue, next)
			}
		}
	}
	return len(visited) == len(nodes)
}

// isComplete: her düğüm çifti arasında kenar var mı
func (g *Graph) isComplete() bool {
	n := len(g.adj)
	for node, neighbors := range g.adj {
		unique := map[string]bool{}
		for _, to := range neighbors {
			if to != node {
				unique[to] = true
			}
		}
		if len(unique) != n-1 {
			return false
		}
	}
	return true
}

// isBipartite: iki renkle boyanabiliyor mu
func (g *Graph) isBipartite() (bool, map[string]int) {
	color := map[string]int{}

	for _, start := range g.Nodes() {
		if _, done := color[start]; done {
			continue
		}
		color[start] = 0
		queue := []string{start}

		for len(queue) > 0 {
			cur := queue[0]
			queue = queue[1:]
			for _, next := range g.adj[cur] {
				c, seen := color[next]
				if !seen {
					color[next] = 1 - color[cur]
					queue = append(queue, next)
					continue
				}
				if c == color[cur] {
					return false, nil // aynı renkte iki komşu
				}
			}
		}
	}
	return true, color
}

func report(name string, g *Graph) {
	fmt.Println(name)
	fmt.Println("  düğümler:", g.Nodes())
	fmt.Println("  bağlantılı:", g.isConnected())
	fmt.Println("  kendine döngü:", g.hasSelfLoop())
	fmt.Println("  çoklu kenar:", g.hasMultiEdge())
	fmt.Println("  tam graf:", g.isComplete())

	ok, color := g.isBipartite()
	fmt.Print("  iki parçalı: ", ok)
	if ok {
		var a, b []string
		for _, n := range g.Nodes() {
			if color[n] == 0 {
				a = append(a, n)
			} else {
				b = append(b, n)
			}
		}
		fmt.Printf(" → grup1=%v grup2=%v", a, b)
	}
	fmt.Println()
	fmt.Println()
}

func main() {
	// Kare: iki parçalı (çift uzunluklu döngü)
	square := NewGraph()
	for _, e := range [][2]string{{"A", "B"}, {"B", "C"}, {"C", "D"}, {"D", "A"}} {
		square.AddEdge(e[0], e[1])
	}
	report("kare graf (4-döngü):", square)

	// Üçgen: iki parçalı DEĞİL (tek uzunluklu döngü)
	triangle := NewGraph()
	for _, e := range [][2]string{{"A", "B"}, {"B", "C"}, {"C", "A"}} {
		triangle.AddEdge(e[0], e[1])
	}
	report("üçgen graf (3-döngü):", triangle)

	// Kopuk graf + kendine döngü + çoklu kenar
	messy := NewGraph()
	messy.AddEdge("A", "B")
	messy.AddEdge("A", "B") // çoklu kenar
	messy.AddEdge("C", "C") // kendine döngü
	messy.AddNode("D")      // yalıtılmış
	report("düzensiz graf:", messy)
}

kare graf (4-döngü):
  düğümler: [A B C D]
  bağlantılı: true
  kendine döngü: false
  çoklu kenar: false
  tam graf: false
  iki parçalı: true → grup1=[A C] grup2=[B D]

üçgen graf (3-döngü):
  düğümler: [A B C]
  bağlantılı: true
  kendine döngü: false
  çoklu kenar: false
  tam graf: true
  iki parçalı: false

düzensiz graf:
  düğümler: [A B C D]
  bağlantılı: false
  kendine döngü: true
  çoklu kenar: true
  tam graf: false
  iki parçalı: false

Kısa sınav

Özet

• Graf, düğümler ve kenarlardan oluşur; ağaçlar, grafların döngüsüz ve bağlantılı özel bir hâlidir.
• Kenarlar yönlü veya yönsüz, ağırlıklı veya ağırlıksız olabilir; modelleme kararı algoritma seçimini belirler.
• Gerçek dünyadaki grafların çoğu seyrektir: E ≈ V, E ≈ V² değil.
• Komşuluk matrisi O(V²) bellek kullanır ama kenar sorgusunu O(1) yapar; yoğun ve küçük graflar için uygundur.
• Komşuluk listesi O(V + E) bellek kullanır ve komşu gezinmeyi derece kadar sürede yapar; varsayılan tercihtir.
• Kenar listesi en kompakt biçimdir ve kenar odaklı algoritmalar için doğaldır.
• El sıkışma önermesi (derece toplamı = 2E), graf kurma kodunu doğrulamanın pratik bir yoludur.
• Yönsüz grafta kenar iki komşuluk listesine de eklenmeli; yalıtılmış düğümler ayrıca kaydedilmelidir.
• İki parçalılık, BFS ile iki renge boyayarak O(V + E) sürede test edilir.