10.1 Definition of Topological Sorting
Topological Sorting is a linear ordering of vertices in a Directed Acyclic Graph (DAG) such that for every edge (u, v), vertex u comes before vertex v. This ordering is possible only for DAGs and cannot be done for graphs with cycles.
How about that definition? If you got it right off the bat, you probably have some good experience with algorithms.
Simply put, it's like this: you have a list of tasks (graph vertices) and a list of dependencies among them (edges in the graph). Arrange the tasks (vertices) such that all tasks that task "A" depends on are done before it. And now it makes sense, instead of "a linear ordering of vertices in a directed acyclic graph"...
Topological Sorting is a crucial algorithm in practice, which is why it has its own name rather than just the author's name. Let's see where it's needed:
Applications:
1. Task Scheduling:
Determining the order of execution for dependent tasks so that each task is executed only after all its dependencies.
Example:
Project planning in project management systems.
2. Code Compilation:
Determining the order of compilation for modules or source code files that depend on each other.
Example:
Optimizing the build process in software build systems (e.g., Makefile).
3. Dependency Resolution in Package Managers:
Ordering packages so all dependencies are installed before the package itself.
Example:
Simplifying software installation processes in package managers (e.g., npm, pip, apt).
4. Route Optimization:
Determining the order of visiting points or performing actions considering the dependencies among them.
Example:
Logistics and delivery route planning.
Time and Space Complexity of Topological Sorting:
Time Complexity:
Both main algorithms for topological sorting (DFS and Kahn's Algorithm) have a time complexity of O(V + E), where V is the number of vertices and E is the number of edges in the graph.
Space Complexity:
The space complexity of both algorithms is O(V + E), as storage is required for the graph and arrays for tracking visited vertices and predecessors.
10.2 Implementation via Depth-First Search (DFS)
Topological sorting can be achieved in different ways, one of which is based on Depth-First Search — DFS. The DFS algorithm for topological sorting uses a stack to track completed nodes.
Example Implementation:
def topological_sort_dfs(graph):
def dfs(vertex, visited, stack):
visited.add(vertex)
for neighbor in graph[vertex]:
if neighbor not in visited:
dfs(neighbor, visited, stack)
stack.append(vertex)
visited = set()
stack = []
for vertex in graph:
if vertex not in visited:
dfs(vertex, visited, stack)
return stack[::-1] # Result in reverse order
# Example usage:
graph = {
'A': ['C'],
'B': ['C', 'D'],
'C': ['E'],
'D': ['F'],
'E': ['H', 'F'],
'F': ['G'],
'G': [],
'H': []
}
result = topological_sort_dfs(graph)
print("Topological Order:", result)
Output:
Topological Order: ['B', 'D', 'F', 'G', 'A', 'C', 'E', 'H']
10.3 Implementation: Kahn's Algorithm
Another approach is called Kahn's Algorithm. Kahn's algorithm for topological sorting uses the concept of vertex in-degrees.
Example Implementation:
from collections import deque, defaultdict
def topological_sort_kahn(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])
top_order = []
while queue:
u = queue.popleft()
top_order.append(u)
for v in graph[u]:
in_degree[v] -= 1
if in_degree[v] == 0:
queue.append(v)
if len(top_order) == len(in_degree):
return top_order
else:
raise ValueError("Graph contains a cycle")
# Example usage:
graph = {
'A': ['C'],
'B': ['C', 'D'],
'C': ['E'],
'D': ['F'],
'E': ['H', 'F'],
'F': ['G'],
'G': [],
'H': []
}
result = topological_sort_kahn(graph)
print("Topological Order:", result)
Output:
Topological Order: ['A', 'B', 'D', 'C', 'E', 'H', 'F', 'G']
GO TO FULL VERSION