Algorithms: Graph & Tree

Adjacency List (sparse graph — thường dùng):
graph[0] = [1, 2]
graph[1] = [3]
graph[2] = [3, 4]

Adjacency Matrix (dense graph):
     0  1  2  3  4
0  [ 0  1  1  0  0 ]
1  [ 0  0  0  1  0 ]
2  [ 0  0  0  1  1 ]

func bfs(graph [][]int, start int) []int {
    visited := make([]bool, len(graph))
    queue := []int{start}
    visited[start] = true
    order := []int{}

    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
}

// BFS với distance tracking
func shortestPath(graph [][]int, start, end int) int {
    visited := make([]bool, len(graph))
    queue := []int{start}
    visited[start] = true
    dist := 0

    for len(queue) > 0 {
        size := len(queue) // process level by level
        for i := 0; i < size; i++ {
            node := queue[0]
            queue = queue[1:]
            if node == end { return dist }
            for _, nb := range graph[node] {
                if !visited[nb] {
                    visited[nb] = true
                    queue = append(queue, nb)
                }
            }
        }
        dist++
    }
    return -1 // not reachable
}

// Iterative DFS
func dfsIterative(graph [][]int, start int) {
    visited := make([]bool, len(graph))
    stack := []int{start}

    for len(stack) > 0 {
        node := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        if visited[node] { continue }
        visited[node] = true

        for _, nb := range graph[node] {
            if !visited[nb] {
                stack = append(stack, nb)
            }
        }
    }
}

// Recursive DFS
func dfs(graph [][]int, node int, visited []bool) {
    visited[node] = true
    for _, nb := range graph[node] {
        if !visited[nb] {
            dfs(graph, nb, visited)
        }
    }
}

func topoSort(numNodes int, edges [][]int) []int {
    inDegree := make([]int, numNodes)
    adj := make([][]int, numNodes)

    for _, e := range edges {
        adj[e[0]] = append(adj[e[0]], e[1])
        inDegree[e[1]]++
    }

    queue := []int{}
    for i := 0; i < numNodes; i++ {
        if inDegree[i] == 0 {
            queue = append(queue, i)
        }
    }

    result := []int{}
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        result = append(result, node)
        for _, nb := range adj[node] {
            inDegree[nb]--
            if inDegree[nb] == 0 {
                queue = append(queue, nb)
            }
        }
    }

    if len(result) != numNodes {
        return nil // cycle detected
    }
    return result
}

func topoSortDFS(numNodes int, adj [][]int) []int {
    visited := make([]int, numNodes) // 0=unvisited, 1=visiting, 2=done
    result := []int{}
    hasCycle := false

    var dfs func(node int)
    dfs = func(node int) {
        if hasCycle { return }
        visited[node] = 1 // mark as visiting
        for _, nb := range adj[node] {
            if visited[nb] == 1 {
                hasCycle = true
                return
            }
            if visited[nb] == 0 {
                dfs(nb)
            }
        }
        visited[node] = 2
        result = append([]int{node}, result...) // prepend
    }

    for i := 0; i < numNodes; i++ {
        if visited[i] == 0 {
            dfs(i)
        }
    }
    if hasCycle { return nil }
    return result
}

type UnionFind struct {
    parent []int
    rank   []int
    count  int // number of connected components
}

func NewUF(n int) *UnionFind {
    uf := &UnionFind{
        parent: make([]int, n),
        rank:   make([]int, n),
        count:  n,
    }
    for i := range uf.parent {
        uf.parent[i] = i
    }
    return uf
}

func (uf *UnionFind) Find(x int) int {
    if uf.parent[x] != x {
        uf.parent[x] = uf.Find(uf.parent[x]) // path compression
    }
    return uf.parent[x]
}

func (uf *UnionFind) Union(x, y int) bool {
    px, py := uf.Find(x), uf.Find(y)
    if px == py { return false } // already connected → cycle!
    // Union by rank
    if uf.rank[px] < uf.rank[py] {
        px, py = py, px
    }
    uf.parent[py] = px
    if uf.rank[px] == uf.rank[py] {
        uf.rank[px]++
    }
    uf.count--
    return true
}

Graph: A→B(1), A→C(4), B→C(2), B→D(5), C→D(1)
Dijkstra từ A:
  dist = {A:0, B:∞, C:∞, D:∞}
  Process A: dist[B]=1, dist[C]=4
  Process B: dist[C]=min(4,3)=3, dist[D]=6
  Process C: dist[D]=min(6,4)=4
  Process D: done
  Result: {A:0, B:1, C:3, D:4}

func dijkstra(graph [][]int, weights [][]int, src int) []int {
    n := len(graph)
    dist := make([]int, n)
    for i := range dist { dist[i] = math.MaxInt32 }
    dist[src] = 0

    // Min-heap: [dist, node]
    pq := &MinHeap{{0, src}}
    heap.Init(pq)

    for pq.Len() > 0 {
        curr := heap.Pop(pq).([2]int)
        d, u := curr[0], curr[1]
        if d > dist[u] { continue } // stale entry

        for i, v := range graph[u] {
            newDist := dist[u] + weights[u][i]
            if newDist < dist[v] {
                dist[v] = newDist
                heap.Push(pq, [2]int{newDist, v})
            }
        }
    }
    return dist
}

func bellmanFord(n int, edges [][]int, src int) []int {
    dist := make([]int, n)
    for i := range dist { dist[i] = math.MaxInt32 }
    dist[src] = 0

    // Relax edges n-1 times
    for i := 0; i < n-1; i++ {
        for _, e := range edges {
            u, v, w := e[0], e[1], e[2]
            if dist[u] != math.MaxInt32 && dist[u]+w < dist[v] {
                dist[v] = dist[u] + w
            }
        }
    }

    // Check negative cycle
    for _, e := range edges {
        u, v, w := e[0], e[1], e[2]
        if dist[u] != math.MaxInt32 && dist[u]+w < dist[v] {
            return nil // negative cycle exists
        }
    }
    return dist
}

// In-order (Left → Root → Right) — sorted order for BST
func inorder(root *TreeNode) []int {
    if root == nil { return nil }
    result := inorder(root.Left)
    result = append(result, root.Val)
    result = append(result, inorder(root.Right)...)
    return result
}

// Level-order — BFS
func levelOrder(root *TreeNode) [][]int {
    if root == nil { return nil }
    result := [][]int{}
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        level := []int{}
        size := len(queue)
        for i := 0; i < size; i++ {
            node := queue[0]; queue = queue[1:]
            level = append(level, node.Val)
            if node.Left != nil { queue = append(queue, node.Left) }
            if node.Right != nil { queue = append(queue, node.Right) }
        }
        result = append(result, level)
    }
    return result
}