Hello! In this article, we will learn about topological sorting. Topological sorting is an algorithm for linearly arranging the vertices in a directed acyclic graph (DAG), which is useful when a specific order needs to be maintained. For example, it is used when handling task dependencies or for compilers to determine the execution order of code.
Problem Description
Let’s solve the following problem.
Problem: Task Scheduling
Given multiple tasks, each task requires specific prerequisite tasks. You can only perform the task after all its prerequisite tasks have been completed. The vertices of the graph represent tasks, and the edges represent the prerequisites. List the given tasks in a possible order.
Input
The first line contains the number of vertices N (1 ≤ N ≤ 1000) and the number of edges M (0 ≤ M ≤ 10000).
The next M lines contain pairs of x y, which means that task x must be performed before task y.
Output
Print the order in which the tasks can be performed, separated by spaces in a single line. If the order is not possible, print -1.
Example Input
6 6
1 2
1 3
2 4
3 4
4 5
5 6
Example Output
1 2 3 4 5 6
Principle of Topological Sorting
Topological sorting can be implemented using two methods: DFS (Depth First Search) and BFS (Breadth First Search). Here, we will introduce Kahn’s algorithm using BFS. Kahn’s algorithm proceeds as follows.
- Record the in-degree of all vertices.
- Add the vertices with in-degree 0 to a queue.
- Remove one vertex from the queue at a time and add it to the result list.
- Remove all the edges going out from the removed vertex and update the in-degree of each destination vertex. Add any vertices that have an in-degree of 0 to the queue.
- Repeat until the queue is empty. If the size of the result list is not equal to the number of input vertices, it means a cycle exists, so return
-1.
Basic Code Implementation
Below is a basic implementation of topological sorting in C++.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void topologicalSort(int n, vector<vector<int>> &graph) {
vector<int> inDegree(n + 1, 0);
vector<int> result;
// Calculate in-degree
for (int i = 1; i <= n; i++) {
for (int j : graph[i]) {
inDegree[j]++;
}
}
queue<int> q;
// Insert vertices with in-degree 0 into the queue
for (int i = 1; i <= n; i++) {
if (inDegree[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
result.push_back(u);
for (int v : graph[u]) {
inDegree[v]--;
if (inDegree[v] == 0) {
q.push(v);
}
}
}
// Check for cycles
if (result.size() != n) {
cout << -1 << endl;
} else {
for (int i = 0; i < result.size(); i++) {
cout << result[i] << ' ';
}
cout << endl;
}
}
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n + 1);
for (int i = 0; i < m; i++) {
int x, y;
cin >> x >> y;
graph[x].push_back(y);
}
topologicalSort(n, graph);
return 0;
}
Code Explanation
In the above code, we first declare an array called inDegree to hold the in-degrees. After computing the in-degrees of each vertex, we add the vertices with in-degree 0 to the queue. Next, we take a vertex from the queue, remove all edges going out from that vertex, and update the in-degrees. If the size of the result list is not equal to the number of vertices, it indicates that a cycle exists, so we print -1.
Complexity Analysis
The time complexity of topological sorting is O(N + M), where N is the number of vertices and M is the number of edges. It takes O(M) time to count the in-degrees, and updating the in-degrees for each vertex also takes O(M). Therefore, the overall time complexity is O(N + M). The space complexity is O(N + M), considering the list to store the graph and the in-degree array.
Additional Practice Problems
Deepen your understanding and application of topological sorting through the following additional practice problems.
- Create various combinations of tasks based on the given tasks and apply topological sorting.
- Implement appropriate error handling when given a graph that contains cycles.
- If there are multiple vertices with the same in-degree, implement it so that one of the vertices is randomly selected.
Conclusion
In this post, we learned about the concept and implementation of topological sorting, as well as how to apply it through an example problem. Topological sorting is an algorithm that is widely used in various fields, so it is important to understand it well and practice sufficiently.
Now you should feel confident using topological sorting to organize and manage complex tasks. Keep practicing and solving various problems!