Kahn's algorithm computes a topological ordering of a directed acyclic graph (DAG). `n` is the number of vertices, `dependencies` is a list of directed edges, where each pair [a, b] represents a directed edge from a to b (i.e. b depends on a). Vertices are assumed to be labelled 0, 1, ..., n-1. If t
(n int, dependencies [][]int)
| 13 | // Vertices are assumed to be labelled 0, 1, ..., n-1. |
| 14 | // If the graph is not a DAG, the function returns nil. |
| 15 | func Kahn(n int, dependencies [][]int) []int { |
| 16 | g := Graph{vertices: n, Directed: true} |
| 17 | // track the in-degree (number of incoming edges) of each vertex |
| 18 | inDegree := make([]int, n) |
| 19 | |
| 20 | // populate g with edges, increase the in-degree counts accordingly |
| 21 | for _, d := range dependencies { |
| 22 | // make sure we don't add the same edge twice |
| 23 | if _, ok := g.edges[d[0]][d[1]]; !ok { |
| 24 | g.AddEdge(d[0], d[1]) |
| 25 | inDegree[d[1]]++ |
| 26 | } |
| 27 | } |
| 28 | |
| 29 | // queue holds all vertices with in-degree 0 |
| 30 | // these vertices have no dependency and thus can be ordered first |
| 31 | queue := make([]int, 0, n) |
| 32 | |
| 33 | for i := 0; i < n; i++ { |
| 34 | if inDegree[i] == 0 { |
| 35 | queue = append(queue, i) |
| 36 | } |
| 37 | } |
| 38 | |
| 39 | // order holds a valid topological order |
| 40 | order := make([]int, 0, n) |
| 41 | |
| 42 | // process the dependency-free vertices |
| 43 | // every time we process a vertex, we "remove" it from the graph |
| 44 | for len(queue) > 0 { |
| 45 | // pop the first vertex from the queue |
| 46 | vtx := queue[0] |
| 47 | queue = queue[1:] |
| 48 | // add the vertex to the topological order |
| 49 | order = append(order, vtx) |
| 50 | // "remove" all the edges coming out of this vertex |
| 51 | // every time we remove an edge, the corresponding in-degree reduces by 1 |
| 52 | // if all dependencies on a vertex is removed, enqueue the vertex |
| 53 | for neighbour := range g.edges[vtx] { |
| 54 | inDegree[neighbour]-- |
| 55 | if inDegree[neighbour] == 0 { |
| 56 | queue = append(queue, neighbour) |
| 57 | } |
| 58 | } |
| 59 | } |
| 60 | |
| 61 | // if the graph is a DAG, order should contain all the certices |
| 62 | if len(order) != n { |
| 63 | return nil |
| 64 | } |
| 65 | return order |
| 66 | } |