Minimum Kapsayan Ağaç

package main

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

type Edge struct {
	From, To string
	Weight   int
}

type UnionFind struct {
	parent map[string]string
	count  int
}

func NewUF(nodes []string) *UnionFind {
	uf := &UnionFind{parent: map[string]string{}, count: len(nodes)}
	for _, n := range nodes {
		uf.parent[n] = n
	}
	return uf
}

func (u *UnionFind) Find(x string) string {
	for u.parent[x] != x {
		u.parent[x] = u.parent[u.parent[x]] // yol yarılama
		x = u.parent[x]
	}
	return x
}

func (u *UnionFind) Union(a, b string) bool {
	ra, rb := u.Find(a), u.Find(b)
	if ra == rb {
		return false
	}
	u.parent[rb] = ra
	u.count--
	return true
}

// validate: kenar kümesi geçerli bir kapsayan ağaç mı
func validate(nodes []string, candidate []Edge) (bool, []string) {
	var problems []string

	if len(candidate) != len(nodes)-1 {
		problems = append(problems,
			fmt.Sprintf("kenar sayısı %d, beklenen %d (V-1)", len(candidate), len(nodes)-1))
	}

	uf := NewUF(nodes)
	for _, e := range candidate {
		if !uf.Union(e.From, e.To) {
			problems = append(problems,
				fmt.Sprintf("%s-%s kenarı döngü oluşturuyor", e.From, e.To))
		}
	}

	if uf.count > 1 {
		problems = append(problems,
			fmt.Sprintf("graf bağlantılı değil: %d bileşen", uf.count))
	}
	return len(problems) == 0, problems
}

func kruskal(nodes []string, edges []Edge) ([]Edge, int) {
	sorted := slices.Clone(edges)
	slices.SortFunc(sorted, func(a, b Edge) int {
		if a.Weight != b.Weight {
			return a.Weight - b.Weight
		}
		return strings.Compare(a.From+a.To, b.From+b.To)
	})
	uf := NewUF(nodes)
	var chosen []Edge
	total := 0
	for _, e := range sorted {
		if uf.Union(e.From, e.To) {
			chosen = append(chosen, e)
			total += e.Weight
		}
	}
	return chosen, total
}

func weight(edges []Edge) int {
	t := 0
	for _, e := range edges {
		t += e.Weight
	}
	return t
}

func main() {
	nodes := []string{"A", "B", "C", "D"}
	all := []Edge{
		{"A", "B", 4}, {"A", "C", 1}, {"B", "C", 3},
		{"B", "D", 5}, {"C", "D", 2},
	}

	mst, mstWeight := kruskal(nodes, all)
	fmt.Println("Kruskal'ın MST'si:")
	for _, e := range mst {
		fmt.Printf("  %s-%s: %d\n", e.From, e.To, e.Weight)
	}
	fmt.Println("  ağırlık:", mstWeight)

	candidates := []struct {
		name  string
		edges []Edge
	}{
		{"MST'nin kendisi", mst},
		{"geçerli ama optimal değil", []Edge{{"A", "B", 4}, {"B", "C", 3}, {"C", "D", 2}}},
		{"döngü içeren", []Edge{{"A", "C", 1}, {"C", "D", 2}, {"A", "B", 4}, {"B", "C", 3}}},
		{"eksik kenar", []Edge{{"A", "C", 1}, {"C", "D", 2}}},
		{"kopuk", []Edge{{"A", "C", 1}, {"B", "D", 5}}},
	}

	fmt.Println()
	for _, c := range candidates {
		ok, problems := validate(nodes, c.edges)
		w := weight(c.edges)
		fmt.Printf("%s (%d kenar, ağırlık %d):\n", c.name, len(c.edges), w)
		if ok {
			optimal := "OPTIMAL"
			if w > mstWeight {
				optimal = fmt.Sprintf("optimal değil (+%d)", w-mstWeight)
			}
			fmt.Printf("  geçerli kapsayan ağaç, %s\n", optimal)
			continue
		}
		fmt.Println("  GEÇERSİZ:")
		for _, p := range problems {
			fmt.Println("   -", p)
		}
	}
}

package main

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

type Edge struct {
	From, To string
	Weight   int
}

type UnionFind struct {
	parent map[string]string
}

func NewUF(nodes []string) *UnionFind {
	uf := &UnionFind{parent: map[string]string{}}
	for _, n := range nodes {
		uf.parent[n] = n
	}
	return uf
}

func (u *UnionFind) Find(x string) string {
	for u.parent[x] != x {
		u.parent[x] = u.parent[u.parent[x]]
		x = u.parent[x]
	}
	return x
}

func (u *UnionFind) Union(a, b string) bool {
	ra, rb := u.Find(a), u.Find(b)
	if ra == rb {
		return false
	}
	u.parent[rb] = ra
	return true
}

func kruskal(nodes []string, edges []Edge) []Edge {
	sorted := slices.Clone(edges)
	slices.SortFunc(sorted, func(a, b Edge) int {
		if a.Weight != b.Weight {
			return a.Weight - b.Weight
		}
		return strings.Compare(a.From+a.To, b.From+b.To)
	})
	uf := NewUF(nodes)
	var mst []Edge
	for _, e := range sorted {
		if uf.Union(e.From, e.To) {
			mst = append(mst, e)
		}
	}
	return mst
}

// bottleneckViaMST: MST üzerindeki yolun en ağır kenarı
func bottleneckViaMST(nodes []string, edges []Edge, from, to string) (int, []string, bool) {
	mst := kruskal(nodes, edges)

	adj := map[string][]Edge{}
	for _, e := range mst {
		adj[e.From] = append(adj[e.From], e)
		adj[e.To] = append(adj[e.To], Edge{e.To, e.From, e.Weight})
	}
	for k := range adj {
		slices.SortFunc(adj[k], func(a, b Edge) int { return strings.Compare(a.To, b.To) })
	}

	visited := map[string]bool{from: true}
	type state struct {
		node string
		maxW int
		path []string
	}
	stack := []state{{from, 0, []string{from}}}

	for len(stack) > 0 {
		cur := stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		if cur.node == to {
			return cur.maxW, cur.path, true
		}
		for _, e := range adj[cur.node] {
			if visited[e.To] {
				continue
			}
			visited[e.To] = true
			newPath := slices.Clone(cur.path)
			newPath = append(newPath, e.To)
			stack = append(stack, state{e.To, max(cur.maxW, e.Weight), newPath})
		}
	}
	return 0, nil, false
}

// bruteForce: tüm yolları dene, en küçük darboğazı bul
func bruteForce(nodes []string, edges []Edge, from, to string) (int, bool) {
	adj := map[string][]Edge{}
	for _, e := range edges {
		adj[e.From] = append(adj[e.From], e)
		adj[e.To] = append(adj[e.To], Edge{e.To, e.From, e.Weight})
	}

	best := 1 << 60
	found := false
	visited := map[string]bool{}

	var dfs func(node string, maxW int)
	dfs = func(node string, maxW int) {
		if node == to {
			if maxW < best {
				best = maxW
			}
			found = true
			return
		}
		visited[node] = true
		for _, e := range adj[node] {
			if !visited[e.To] {
				dfs(e.To, max(maxW, e.Weight))
			}
		}
		visited[node] = false
	}
	dfs(from, 0)
	return best, found
}

func main() {
	nodes := []string{"A", "B", "C", "D", "E"}
	edges := []Edge{
		{"A", "B", 10}, {"A", "C", 3}, {"C", "B", 4},
		{"B", "D", 8}, {"C", "D", 9}, {"D", "E", 2},
		{"C", "E", 15},
	}

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

	mst := kruskal(nodes, edges)
	fmt.Println()
	fmt.Println("MST:")
	for _, e := range mst {
		fmt.Printf("  %s-%s: %d\n", e.From, e.To, e.Weight)
	}

	fmt.Println()
	fmt.Printf("%-12s %12s %12s %8s %s\n", "çift", "MST yolu", "kaba kuvvet", "aynı", "yol")
	for _, pair := range [][2]string{
		{"A", "B"}, {"A", "D"}, {"A", "E"}, {"B", "E"}, {"C", "E"},
	} {
		viaM, path, ok1 := bottleneckViaMST(nodes, edges, pair[0], pair[1])
		brute, ok2 := bruteForce(nodes, edges, pair[0], pair[1])
		if !ok1 || !ok2 {
			fmt.Printf("%-12s yol yok\n", pair[0]+"-"+pair[1])
			continue
		}
		fmt.Printf("%-12s %12d %12d %8t %s\n",
			pair[0]+"-"+pair[1], viaM, brute, viaM == brute, strings.Join(path, "→"))
	}

	fmt.Println()
	fmt.Println("A → B için: doğrudan kenar 10, ama A→C→B yolunda en ağır kenar 4")
	fmt.Println("MST'nin minimax özelliği bunu otomatik verir.")
}

package main

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

type Edge struct {
	From, To string
	Weight   int
}

func (e Edge) String() string { return fmt.Sprintf("%s-%s(%d)", e.From, e.To, e.Weight) }

type UnionFind struct {
	parent map[string]string
	count  int
}

func NewUF(nodes []string) *UnionFind {
	uf := &UnionFind{parent: map[string]string{}, count: len(nodes)}
	for _, n := range nodes {
		uf.parent[n] = n
	}
	return uf
}

func (u *UnionFind) Find(x string) string {
	for u.parent[x] != x {
		u.parent[x] = u.parent[u.parent[x]]
		x = u.parent[x]
	}
	return x
}

func (u *UnionFind) Union(a, b string) bool {
	ra, rb := u.Find(a), u.Find(b)
	if ra == rb {
		return false
	}
	u.parent[rb] = ra
	u.count--
	return true
}

// kruskalExcluding: belirli bir kenarı hariç tutarak MST kurar
func kruskalExcluding(nodes []string, edges []Edge, exclude int) ([]Edge, int, bool) {
	type indexed struct {
		Edge
		idx int
	}
	sorted := make([]indexed, 0, len(edges))
	for i, e := range edges {
		if i == exclude {
			continue
		}
		sorted = append(sorted, indexed{e, i})
	}
	slices.SortFunc(sorted, func(a, b indexed) int {
		if a.Weight != b.Weight {
			return a.Weight - b.Weight
		}
		return strings.Compare(a.From+a.To, b.From+b.To)
	})

	uf := NewUF(nodes)
	var chosen []Edge
	total := 0
	for _, e := range sorted {
		if uf.Union(e.From, e.To) {
			chosen = append(chosen, e.Edge)
			total += e.Weight
		}
	}
	return chosen, total, uf.count == 1
}

// mstIndices: MST'de kullanılan kenarların indekslerini döndürür
func mstIndices(nodes []string, edges []Edge) ([]int, int) {
	type indexed struct {
		Edge
		idx int
	}
	sorted := make([]indexed, len(edges))
	for i, e := range edges {
		sorted[i] = indexed{e, i}
	}
	slices.SortFunc(sorted, func(a, b indexed) int {
		if a.Weight != b.Weight {
			return a.Weight - b.Weight
		}
		return strings.Compare(a.From+a.To, b.From+b.To)
	})

	uf := NewUF(nodes)
	var used []int
	total := 0
	for _, e := range sorted {
		if uf.Union(e.From, e.To) {
			used = append(used, e.idx)
			total += e.Weight
		}
	}
	slices.Sort(used)
	return used, total
}

// secondBestMST: MST kenarlarını tek tek yasaklayarak ikinci en iyiyi bulur
func secondBestMST(nodes []string, edges []Edge) ([]Edge, int, Edge, bool) {
	mstIdx, mstWeight := mstIndices(nodes, edges)

	bestWeight := 1 << 60
	var bestTree []Edge
	var removed Edge
	found := false

	for _, idx := range mstIdx {
		tree, weight, connected := kruskalExcluding(nodes, edges, idx)
		if !connected {
			continue // bu kenar köprü: çıkarılırsa graf kopar
		}
		if weight < bestWeight {
			bestWeight, bestTree, removed, found = weight, tree, edges[idx], true
		}
	}
	_ = mstWeight
	return bestTree, bestWeight, removed, found
}

func main() {
	nodes := []string{"A", "B", "C", "D"}
	edges := []Edge{
		{"A", "B", 1}, {"B", "C", 2}, {"C", "D", 3},
		{"A", "C", 4}, {"B", "D", 5}, {"A", "D", 6},
	}

	fmt.Println("kenarlar:")
	for i, e := range edges {
		fmt.Printf("  %d. %v\n", i, e)
	}

	mstIdx, mstWeight := mstIndices(nodes, edges)
	fmt.Println()
	fmt.Println("MST:")
	for _, i := range mstIdx {
		fmt.Printf("  %v\n", edges[i])
	}
	fmt.Println("  ağırlık:", mstWeight)

	second, secondWeight, removed, ok := secondBestMST(nodes, edges)
	fmt.Println()
	if !ok {
		fmt.Println("ikinci MST bulunamadı (graf çok kısıtlı)")
		return
	}
	fmt.Println("İKİNCİ en iyi kapsayan ağaç:")
	for _, e := range second {
		fmt.Printf("  %v\n", e)
	}
	fmt.Println("  ağırlık:", secondWeight)
	fmt.Println("  çıkarılan kenar:", removed)
	fmt.Println("  fark:", secondWeight-mstWeight)

	// Köprü kenarı olan graf
	fmt.Println()
	bridged := []string{"P", "Q", "R"}
	bridgeEdges := []Edge{
		{"P", "Q", 1}, {"Q", "R", 2},
	}
	_, w := mstIndices(bridged, bridgeEdges)
	_, _, _, ok2 := secondBestMST(bridged, bridgeEdges)
	fmt.Println("ağaç şeklindeki graf (MST ağırlığı", w, "):")
	fmt.Println("  ikinci MST var mı:", ok2)
	fmt.Println("  → her kenar köprü olduğu için başka kapsayan ağaç yok")
}