multixlab

Topological sort using Kahn's algorithm

Algorithms  #algorithms  #sorting  #graphs  #top-sort 

Topological ordering

Topological ordering is the arrangement of nodes in a directed graph in such a way that u comes before v for every edge u -> v.

The topological ordering of a graph is not unique. For a given graph, there can be multiple topological orderings

A valid topological ordering can only be obtained with DAGs (Directed Acyclic Graphs) and rooted trees. Directed graphs with cycles will not produce a valid ordering.

Usage

Topological sort is commonly used to represent the precedence constraints between tasks in a scheduling problem, where some tasks must be completed before others can start.

Here are a few examples of situations where topological sort can be useful:

  • Dependency resolution in software engineering: A software build process requires certain libraries or components to be built before others. A topological sort of the dependencies can determine the correct order of building the components.

  • Course scheduling: In a university setting, some courses have prerequisites that must be taken before enrolling in the course. A topological sort of the courses can determine a linear order of courses such that all prerequisites are met.

  • Task scheduling: In a project management context, tasks can have dependencies such that one task must be completed before another can start. A topological sort of the tasks can determine a linear order of tasks such that all dependencies are satisfied.

Degree of a vertex

The degree of a vertex in a graph is the number of edges incident to that vertex. It represents the number of edges connected to a particular vertex. For a directed graph, degree = in-degree + out-degree

In-degree

In-degree of a vertex in a directed graph is the number of directed edges that are incoming to that vertex, i.e., the number of edges ending at that vertex.

Out-degree

Out-degree of a vertex in a directed graph is the number of directed edges that are outgoing from that vertex, i.e., the number of edges starting at that vertex.

Vertex 2 in the graph above has a degree of 3, an in-degree of 1, and an out-degree of 2.

Kahn’s Algorithm

Kahn’s algorithm is a topological sorting algorithm for directed acyclic graphs (DAGs). It determines the order in which vertices should be processed to ensure that all the dependencies are met. The algorithm works as follows:

  1. Select a vertex with no incoming edges (a source vertex) and add it to a queue.
  2. Remove the selected vertex from the graph, along with all its outgoing edges.
  3. Repeat steps 1 and 2 until there are no vertices left in the graph, or there are vertices with unprocessed incoming edges.
  4. If there are still vertices with unprocessed incoming edges, the graph has a cycle, and the algorithm fails.

The resulting order of vertices represents a valid topological sort of the graph.

Example

  • This sample code performs a top-sort on the graph above.
import java.util.*

fun main() {
    val adjacencyList = mutableListOf<List<Int>>().apply {
        add(0, listOf())
        add(1, listOf(0, 3))
        add(2, listOf(3, 4))
        add(3, listOf(4))
        add(4, listOf(5))
        add(5, listOf())
        add(6, listOf(2, 3, 5))
        add(7, listOf(2, 3))
    }
    topSortUsingKahnsAlgo(adjacencyList).also { println("top-sort: $it") }
}

//sampleStart
fun topSortUsingKahnsAlgo(adjacencyList: List<List<Int>>): List<Int> {
    // click + to see full script
    val inDegrees = IntArray(adjacencyList.size)
    val sortedVertices = mutableListOf<Int>()
    val vertexQueue = LinkedList<Int>()

    // calculate in-degree of all neighbours for each vertex
    for (vertex in adjacencyList) {
        vertex.forEach { adjacentVertex ->
            inDegrees[adjacentVertex]++
        }
    }

    // add vertices with in-degree = 0 to queue
    adjacencyList.indices.filter { vertex ->
        inDegrees[vertex] == 0
    }.forEach { vertexWithNoIncomingEdge ->
        vertexQueue.add(vertexWithNoIncomingEdge)
    }

    var visitedVerticesCount = 0

    while (vertexQueue.isNotEmpty()) {
        val currentVertex = vertexQueue.pop()
        // the degree of currentVertex is 0. Add it to sorted vertices
        sortedVertices.add(currentVertex)
        visitedVerticesCount++
        adjacencyList[currentVertex].forEach { adjacentVertex ->
            // remove incoming edge
            inDegrees[adjacentVertex] = inDegrees[adjacentVertex] - 1
            val hasInDegreeBecomeZero = inDegrees[adjacentVertex] == 0
            if (hasInDegreeBecomeZero) {
                vertexQueue.add(adjacentVertex)
            }
        }
    }

    // if all vertices were not visited then there is a cycle
    if (visitedVerticesCount != adjacencyList.size) {
        throw IllegalStateException("top sort not possible")
    }
    return sortedVertices
}
//sampleEnd

Time Complexity

The time complexity of Kahn’s algorithm is O(V+E), where V is the number of vertices and E is the number of edges in the directed acyclic graph (DAG).

The algorithm takes O(V) time to initialize the in-degree of all vertices and to add the source vertices to the queue. Then, in each iteration, it takes O(1) time to select a vertex from the queue and O(E) time to remove its outgoing edges and update the in-degree of its neighbors. Since each edge is processed once, the total time complexity is O(V+E).

Space Complexity

The space complexity of Kahn’s algorithm is O(V+E), where V is the number of vertices and E is the number of edges in the directed acyclic graph (DAG).

Auxiliary Space Complexity

In the case of Kahn’s algorithm, the auxiliary space is the space used by the algorithm in addition to the space required to store the graph. This includes the space required to store the in-degree count of all vertices, the queue used to store vertices with no incoming edges, and a set of vertices to keep track of processed vertices.

The auxiliary space complexity of Kahn’s algorithm is O(V), where V is the number of vertices in the directed acyclic graph (DAG)

Related posts

top