Topological Sorting is a method of sorting nodes in a Directed Acyclic Graph (DAG). It arranges all edges in such a way that they point from the upper node to the lower node. This sorting is mainly used in determining the order of tasks, dependencies, and various programming problems.
Problem Description
Given the number of classes N and a list of edges indicating the precedence relationships between classes, the problem is to determine the order in which the classes can be taken using the topological sorting algorithm.
Input Format
N = 6 edges = [(2, 1), (3, 1), (4, 1), (6, 4), (5, 2), (5, 3)]
Output Format
1 2 3 4 5 6 (One possible order in which the classes can be taken)
Problem Solving Process
1. Understanding the Problem
The topological sorting problem is to establish the precedence relationships through the given nodes (N) and edge information (edges), and then sort all the nodes. Here, edges is represented in the form of (A, B), indicating that A must be taken before B can be taken.
2. Handling Input Parameters
To implement topological sorting, we first need to construct the graph’s adjacency list and the in-degree array. The in-degree array counts the number of classes each node must attend.
from collections import deque
def topological_sort(N, edges):
# Initialize graph and in-degree
graph = [[] for _ in range(N + 1)]
in_degree = [0] * (N + 1)
# Register edge information in the graph and in-degree
for u, v in edges:
graph[u].append(v)
in_degree[v] += 1
3. Designing the Topological Sorting Algorithm
Now, let’s design the algorithm to perform topological sorting. We will add nodes with an in-degree of 0 to a queue, and as we remove nodes one by one from the queue, we will decrease the in-degrees of the nodes connected to that node. Nodes whose in-degree becomes 0 after the decrease will be added back to the queue. This process will be repeated until the queue is empty. Ultimately, we will return the sorted order of nodes.
# Add nodes with in-degree of 0 to the queue
queue = deque()
for i in range(1, N + 1):
if in_degree[i] == 0:
queue.append(i)
result = []
while queue:
current = queue.popleft()
result.append(current)
for neighbor in graph[current]:
in_degree[neighbor] -= 1
if in_degree[neighbor] == 0:
queue.append(neighbor)
return result
4. Writing and Executing the Complete Code
Now let’s integrate the entire code to write the final code. We can pass the processed input values to the function to check the results.
N = 6
edges = [(2, 1), (3, 1), (4, 1), (6, 4), (5, 2), (5, 3)]
sorted_order = topological_sort(N, edges)
print("Order of classes that can be taken:", sorted_order)
5. Results and Evaluation
Running the above code will allow us to find an order of classes that can be taken through topological sorting. Due to the nature of the graph, multiple correct answers may arise. Therefore, if the algorithm is functioning correctly, it is necessary to broadly validate the validity of the results.
6. Code and Algorithm Optimization
The time complexity of the topological sorting algorithm is O(V + E), where V is the number of vertices and E is the number of edges. This algorithm can operate efficiently even with large datasets, making it a useful tool for employment coding tests.
Conclusion
Topological sorting is a useful algorithm in graph theory, applicable to various problems. In this lecture, we implemented topological sorting using Python and provided content suitable for practical coding tests. We hope you will continue to understand and utilize such algorithmic problems in depth.