In modern software development environments, algorithms play a crucial role. Let’s take a look at topological sorting,
which is one of the problems frequently encountered in coding tests. Topological sorting is a technique for
ordering all nodes in a directed graph by considering the direction of edges. It is primarily used to
express dependencies between tasks.
Problem Description
Let’s explore a problem that receives input as follows. Given the precedence between the tasks,
the problem is to output the order in which all tasks can be completed using topological sorting.
Example Problem:
There are N tasks, and each task is identified by a number from 1 to N.
M edges are given, which define the precedence between the tasks.
Check if the given tasks can be processed through topological sorting and output that order.
Input Example:
6 6
6 5
5 4
4 3
2 5
3 1
1 2
Output Example:
6 5 4 3 1 2
Problem Solving Process
1. Understanding the Problem
First, we need to understand what topological sorting is and what is required in this problem.
Topological sorting is the process of ordering each node in a directed graph while respecting the direction of all edges.
Based on the direction of the given edges, we can define the order in which each task should precede.
A graph that allows for topological sorting must be acyclic (Directed Acyclic Graph, DAG).
2. Approach to Solve the Problem
The basic approach to solving the problem is as follows:
- Represent the precedence between the given tasks as a graph.
- Calculate the indegree for each task.
- Add tasks with an indegree of 0 to a queue.
- Process tasks one by one from the queue and decrease the indegree of tasks connected to it.
Tasks that become 0 indegree are added back to the queue. - Repeat until all tasks are processed.
- Output the result of the topological sorting.
3. Implementation in JavaScript
Now, let’s implement the JavaScript code according to the above steps.
The code below performs topological sorting based on the given input.
function topologicalSort(N, edges) {
const graph = {};
const indegree = new Array(N + 1).fill(0);
const result = [];
// Create graph and initialize indegree
edges.forEach(([u, v]) => {
if (!graph[u]) graph[u] = [];
graph[u].push(v);
indegree[v]++;
});
const queue = [];
// Add tasks with indegree of 0
for (let i = 1; i <= N; i++) {
if (indegree[i] === 0) {
queue.push(i);
}
}
while (queue.length > 0) {
const node = queue.shift();
result.push(node);
// Decrease indegree of connected nodes
if (graph[node]) {
graph[node].forEach(neighbor => {
indegree[neighbor]--;
if (indegree[neighbor] === 0) {
queue.push(neighbor);
}
});
}
}
// Check if topological sorting was possible.
if (result.length !== N) {
return "A cycle exists.";
}
return result;
}
// Input Example
const N = 6;
const edges = [
[6, 5],
[5, 4],
[4, 3],
[2, 5],
[3, 1],
[1, 2],
];
console.log(topologicalSort(N, edges));
4. Code Explanation
I will now explain how to implement topological sorting through the above code.
-
Graph Construction:
The graph is created in the form of an adjacency list based on the given list of edges.
The indegree of each node is recorded, indicating how many edges depend on that node. -
Finding Nodes with Indegree of 0:
Check all nodes and add those with an indegree of 0 to the queue. -
Processing via BFS:
Process nodes one by one from the queue and reduce the indegree of connected nodes.
If a node’s indegree becomes 0, add it to the queue. -
Check the Length of the Result:
If all tasks are processed, the length of the result array should be the same as the number of nodes,
indicating that topological sorting has been successfully performed.
5. Conclusion and Lessons Learned
Topological sorting is very useful when tasks need to be performed in a specific order based on dependencies.
Through this tutorial, we learned the fundamental idea of topological sorting and how to implement it in JavaScript.
Having opportunities to utilize various data structures and algorithms is essential for successful performance in coding tests.
Since there are many scenarios in real problems that require topological sorting,
it is important to understand the characteristics of each problem and solve it using the appropriate data structures and algorithms.
Keep practicing various problems to improve your skills!