Topological Sort

Topological Sort is a linear ordering of the vertices in a Directed Acyclic Graph (DAG) such that for every directed edge from vertex u to vertex v, u comes before v in the ordering. It's important to note that topological sorting is only possible for DAGs.

Topological sorting is used in scheduling problems, such as determining the order of tasks in a build system or resolving dependencies in a software project.

Topological Sort (Kahn's Algorithm)

Step 1 of 0

Action

Ready to start

Current Node

None

Queue (in-degree 0)

[]

Topological Order

[]

Current Node

Processed

In Queue

In-degree 0

Has Dependencies

Removed Edge

Course Prerequisites Example: Each node represents a course, edges show prerequisites (A→C means A is prerequisite for C). Topological sort finds a valid order to take all courses.

Topological Sort Algorithm

Topological Sort is a linear ordering of the vertices in a Directed Acyclic Graph (DAG) such that for every directed edge from vertex u to vertex v, u comes before v in the ordering. It's commonly used for scheduling tasks with dependencies.

Algorithm Steps (Kahn's Algorithm)

Compute the in-degree (number of incoming edges) for each vertex.
Initialize a queue with all vertices with an in-degree of 0.
While the queue is not empty, do the following:
Dequeue a vertex and add it to the topological sort result.
For each of its neighbors, decrement their in-degree. If a neighbor's in-degree becomes 0, enqueue it.
If the number of nodes in the result is not equal to the total number of nodes, the graph has a cycle.

Topological Sort


from collections import deque

def topological_sort(graph):
    in_degree = {u: 0 for u in graph}
    for u in graph:
        for v in graph[u]:
            in_degree[v] += 1

    queue = deque([u for u in graph if in_degree[u] == 0])
    result = []

    while queue:
        u = queue.popleft()
        result.append(u)
        for v in graph[u]:
            in_degree[v] -= 1
            if in_degree[v] == 0:
                queue.append(v)

    if len(result) == len(graph):
        return result
    else:
        return []  # Cycle detected