Hello! In this article, we will learn about topological sorting<\/strong>. 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.<\/p>\n Let’s solve the following problem.<\/p>\n 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.<\/p>\n<\/div>\n The first line contains the number of vertices The next Print the order in which the tasks can be performed, separated by spaces in a single line. If the order is not possible, print Topological sorting can be implemented using two methods: DFS (Depth First Search)<\/strong> and BFS (Breadth First Search)<\/strong>. Here, we will introduce Kahn’s algorithm using BFS. Kahn’s algorithm proceeds as follows.<\/p>\n Below is a basic implementation of topological sorting in C++.<\/p>\n In the above code, we first declare an array called The time complexity of topological sorting is Deepen your understanding and application of topological sorting through the following additional practice problems.<\/p>\nProblem Description<\/h2>\n
Problem: Task Scheduling<\/h3>\n
Input<\/h2>\n
N<\/code> (1 \u2264 N \u2264 1000) and the number of edges M<\/code> (0 \u2264 M \u2264 10000).<\/p>\nM<\/code> lines contain pairs of x<\/code> y<\/code>, which means that task x<\/code> must be performed before task y<\/code>.<\/p>\nOutput<\/h2>\n
-1<\/code>.<\/p>\nExample Input<\/h2>\n
\n 6 6\n 1 2\n 1 3\n 2 4\n 3 4\n 4 5\n 5 6\n <\/pre>\n
Example Output<\/h2>\n
1 2 3 4 5 6<\/pre>\n
Principle of Topological Sorting<\/h2>\n
\n
-1<\/code>.<\/li>\n<\/ol>\nBasic Code Implementation<\/h2>\n
\n#include <iostream>\n#include <vector>\n#include <queue>\nusing namespace std;\n\nvoid topologicalSort(int n, vector<vector<int>> &graph) {\n vector<int> inDegree(n + 1, 0);\n vector<int> result;\n\n \/\/ Calculate in-degree\n for (int i = 1; i <= n; i++) {\n for (int j : graph[i]) {\n inDegree[j]++;\n }\n }\n\n queue<int> q;\n\n \/\/ Insert vertices with in-degree 0 into the queue\n for (int i = 1; i <= n; i++) {\n if (inDegree[i] == 0) {\n q.push(i);\n }\n }\n\n while (!q.empty()) {\n int u = q.front();\n q.pop();\n result.push_back(u);\n\n for (int v : graph[u]) {\n inDegree[v]--;\n if (inDegree[v] == 0) {\n q.push(v);\n }\n }\n }\n\n \/\/ Check for cycles\n if (result.size() != n) {\n cout << -1 << endl;\n } else {\n for (int i = 0; i < result.size(); i++) {\n cout << result[i] << ' ';\n }\n cout << endl;\n }\n}\n\nint main() {\n int n, m;\n cin >> n >> m;\n vector<vector<int>> graph(n + 1);\n\n for (int i = 0; i < m; i++) {\n int x, y;\n cin >> x >> y;\n graph[x].push_back(y);\n }\n\n topologicalSort(n, graph);\n return 0;\n}\n <\/code><\/pre>\nCode Explanation<\/h2>\n
inDegree<\/code> 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<\/code> list is not equal to the number of vertices, it indicates that a cycle exists, so we print -1<\/code>.<\/p>\nComplexity Analysis<\/h2>\n
O(N + M)<\/code>, where N<\/code> is the number of vertices and M<\/code> is the number of edges. It takes O(M)<\/code> time to count the in-degrees, and updating the in-degrees for each vertex also takes O(M)<\/code>. Therefore, the overall time complexity is O(N + M)<\/code>. The space complexity is O(N + M)<\/code>, considering the list to store the graph and the in-degree array.<\/p>\nAdditional Practice Problems<\/h2>\n