[graph] graph algorithms #algorithm

kahn.go

func topoTraverse(n int, edge [][]int) {
	graph := make(map[int][]int)
	inTable := make([]int, n)

	for _, edge := range edge {
		graph[edge[0]] = append(graph[edge[0]], edge[1])
		inTable[edge[1]]++
	}
	var queue []int
	for i, v := range inTable {
		if v == 0 {
			queue = append(queue, i)
		}
	}

	for len(queue) > 0 {
		for size := len(queue); size > 0; size-- {
			n := queue[0]
			queue = queue[1:]

			for _, c := range graph[n] {
				inTable[c]--
				if inTable[c] == 0 {
					queue = append(queue, c)
				}
			}
			delete(graph, n)
		}
	}
	for _, v := range inTable {
		if v > 0 {
			panic("cycle")
		}
	}
}