multixlab

Topological sort using DFS

Algorithms  #algorithms  #sorting  #dfs  #graphs  #top-sort 

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.

Top sort using DFS

Vertices in a graph can be arranged topologically using depth-first search (DFS).

Steps

  1. Create an array with the same size as the number of vertices (we’ll call it a top-sort array).
  2. From any vertex, start DFS
  3. After visiting all of a vertex’s neighbours, add it to the top-sort array
  4. Top-sort arrays will contain vertices in topological order once DFS is complete

DFS Example

An example of top sort is shown in the following images. The DFS starts at vertex zero (A) and moves on to the next vertices (B…F). Visited vertices are greyed out and a top sort array is visible at the bottom of each image.

There is an important point to note here: the top-sort array is filled from right to left. It will be easier to do so if you keep track of the index of the next insertion position. If a list is used for storing top-sort values, it can be reversed before returning the value.

Verify that u comes before v for every edge (u, v) in the top-sort array shown above

Kotlin Code

  • This sample code performs a top-sort on the graph above.
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))
    }
    topSortDfs(adjacencyList).also {
        println("TopSort DFS: $it")
    }
}

//sampleStart
fun topSortDfs(adjacencyList: List<List<Int>>): List<Int> {
    // click + to see full script
    val visited = BooleanArray(adjacencyList.size)
    val sortedVertices = IntArray(adjacencyList.size)

    /**
     * insert position of a vertex in sortedVertices, starting with the last position
     */
    var nextInsertionIndexFromEnd = sortedVertices.size - 1

    // performs dfs traversal on vertex
    fun dfs(vertex: Int) {
        visited[vertex] = true
        adjacencyList[vertex].forEach { adjacentVertex ->
            if (visited[adjacentVertex].not()) {
                dfs(adjacentVertex)
            }
        }

        /**
         * if there are no other vertices to traverse from current vertex,
         * add this vertex to the next empty space in sortedVertices
         */
        sortedVertices[nextInsertionIndexFromEnd--] = vertex
    }

    // perform dfs on each vertex if not visited
    for (vertex in adjacencyList.indices) {
        if (visited[vertex].not()) {
            dfs(vertex)
        }
    }
    return sortedVertices.asList()
}
//sampleEnd

Time Complexity

Since DFS traverses all vertices (V) and edges (E) of a graph, topological sort has a time complexity of O(V+E).

Related posts

top