How do I implement topological sort in Go?

Topological sort is an important algorithm used in graph theory, particularly in scenarios where a directed graph needs to be organized in a linear order. It is primarily applicable to Directed Acyclic Graphs (DAGs). In Go, you can implement a topological sort using depth-first search (DFS). Below is an example of how to perform a topological sort in Go.

package main

import (
    "fmt"
)

type Graph struct {
    vertices int
    adj      [][]int
}

func NewGraph(vertices int) *Graph {
    g := &Graph{vertices: vertices}
    g.adj = make([][]int, vertices)
    return g
}

func (g *Graph) AddEdge(from, to int) {
    g.adj[from] = append(g.adj[from], to)
}

func (g *Graph) topologicalSortUtil(v int, visited []bool, stack *[]int) {
    visited[v] = true
    for _, neighbor := range g.adj[v] {
        if !visited[neighbor] {
            g.topologicalSortUtil(neighbor, visited, stack)
        }
    }
    *stack = append(*stack, v)
}

func (g *Graph) TopologicalSort() []int {
    visited := make([]bool, g.vertices)
    stack := []int{}

    for i := 0; i < g.vertices; i++ {
        if !visited[i] {
            g.topologicalSortUtil(i, visited, &stack)
        }
    }

    // Reverse the stack to get the topological sorting order
    for i, j := 0, len(stack)-1; i < j; i, j = i+1, j-1 {
        stack[i], stack[j] = stack[j], stack[i]
    }

    return stack
}

func main() {
    g := NewGraph(6)
    g.AddEdge(5, 2)
    g.AddEdge(5, 0)
    g.AddEdge(4, 0)
    g.AddEdge(4, 1)
    g.AddEdge(3, 1)
    g.AddEdge(2, 3)

    sortedOrder := g.TopologicalSort()
    fmt.Printf("Topological Sort: %v\n", sortedOrder)
}