1. What is Topological Sorting?
Topological sorting is a method of linearly ordering nodes in a directed graph. The main characteristic of this sorting is that all edges in the graph follow the order of the sorted nodes. In other words, if there is an edge from node A to node B, node A must precede node B. Topological sorting, which possesses this property, is mainly used for determining the order of tasks or in scheduling problems.
Topological sorting can only be applied in Directed Acyclic Graphs (DAGs). If a cycle exists, topological sorting cannot be performed, which signifies an impossible state due to the nature of the graph. There are two main methods to implement topological sorting:
1) DFS (Depth First Search) based method
2) Kahn’s algorithm
2. Problem Description
The following is a problem that requires the use of topological sorting.
Problem: Course Completion Order
You are a college student. You need to complete several courses to graduate. The prerequisites for each course are that other courses must be completed first. Based on this information, print the order in which each course should be completed. If the ordering is not possible, print “IMPOSSIBLE”.
Input Format:
– The first line contains the number of courses N (1 ≤ N ≤ 1000) and the number of prerequisites M (0 ≤ M ≤ 100,000).
– The next M lines contain two integers u, v representing the prerequisite relationships. In this case, course u must be completed before course v.
Output Format:
– Print the order of course completion, one per line.
– If the ordering is not possible, print “IMPOSSIBLE”.
3. Problem Solving Process
First, we need to understand the number of courses and the prerequisite relationships through input. To do this, we use an adjacency list to represent the graph. We also need to create an array to store the in-degrees of each node. The in-degree represents the number of prerequisites for that node.
1) Graph Construction:
– Construct the adjacency list and in-degree array based on the prerequisite relationships given in the input.
2) Topological Sorting Using In-Degree:
– Add nodes with an in-degree of 0 to the queue. In this case, the course has no prerequisites, hence can be completed first.
– Remove a node from the queue and decrease the in-degree of its connected nodes by 1. If the in-degree becomes 0, add that node to the queue.
– Repeat this process to process all nodes. If the number of processed nodes is not equal to the total number of courses, it indicates the presence of a cycle, so “IMPOSSIBLE” should be printed.
4. C# Code Implementation
using System;
using System.Collections.Generic;
class Program
{
static void Main()
{
// Receiving input
int N = int.Parse(Console.ReadLine());
int M = int.Parse(Console.ReadLine());
// Initializing adjacency list and in-degree array
List[] graph = new List[N + 1];
int[] inDegree = new int[N + 1];
for (int i = 1; i <= N; i++)
{
graph[i] = new List();
}
// Receiving prerequisite relationships
for (int i = 0; i < M; i++)
{
string[] input = Console.ReadLine().Split();
int u = int.Parse(input[0]);
int v = int.Parse(input[1]);
graph[u].Add(v);
inDegree[v]++;
}
// Initializing queue and result list
Queue queue = new Queue();
List result = new List();
// Adding nodes with an in-degree of 0 to the queue
for (int i = 1; i <= N; i++)
{
if (inDegree[i] == 0)
{
queue.Enqueue(i);
}
}
// Topological Sorting
while (queue.Count > 0)
{
int node = queue.Dequeue();
result.Add(node);
foreach (int neighbor in graph[node])
{
inDegree[neighbor]--;
if (inDegree[neighbor] == 0)
{
queue.Enqueue(neighbor);
}
}
}
// Output result
if (result.Count != N)
{
Console.WriteLine("IMPOSSIBLE");
}
else
{
foreach (int course in result)
{
Console.WriteLine(course);
}
}
}
}
This code demonstrates how to perform topological sorting based on the number of given courses and prerequisite relationships.
It allows linear sorting of each course according to the prerequisite relationships in the graph.
5. Conclusion
Topological sorting is one of the most important algorithms in graph theory.
It can be applied in many practical problems and is a topic often covered in programming tests.
I hope this problem helped you understand how to utilize topological sorting.
Now you have the skills to implement topological sorting using C# and adapt to various problems that require it.
I encourage you to continue challenging yourself with a variety of problems that necessitate topological sorting.