{"id":34494,"date":"2024-11-01T09:28:37","date_gmt":"2024-11-01T09:28:37","guid":{"rendered":"http:\/\/atmokpo.com\/w\/?p=34494"},"modified":"2024-11-01T11:41:02","modified_gmt":"2024-11-01T11:41:02","slug":"javascript-coding-test-course-topological-sort","status":"publish","type":"post","link":"https:\/\/atmokpo.com\/w\/34494\/","title":{"rendered":"JavaScript Coding Test Course, Topological Sort"},"content":{"rendered":"
\n

\n In modern software development environments, algorithms play a crucial role. Let’s take a look at topological sorting,
\n which is one of the problems frequently encountered in coding tests. Topological sorting is a technique for
\n ordering all nodes in a directed graph by considering the direction of edges. It is primarily used to
\n express dependencies between tasks.\n<\/p>\n

Problem Description<\/h2>\n

\n Let’s explore a problem that receives input as follows. Given the precedence between the tasks,
\n the problem is to output the order in which all tasks can be completed using topological sorting.\n<\/p>\n

\nExample Problem:<\/strong>
\n There are N tasks, and each task is identified by a number from 1 to N.
\n M edges are given, which define the precedence between the tasks.
\n Check if the given tasks can be processed through topological sorting and output that order.\n<\/p>\n

\nInput Example:<\/strong>
\n 6 6
\n 6 5
\n 5 4
\n 4 3
\n 2 5
\n 3 1
\n 1 2<\/p>\n

Output Example:<\/strong>
\n 6 5 4 3 1 2\n<\/p>\n

Problem Solving Process<\/h2>\n

1. Understanding the Problem<\/h3>\n

\n First, we need to understand what topological sorting is and what is required in this problem.
\n Topological sorting is the process of ordering each node in a directed graph while respecting the direction of all edges.
\n Based on the direction of the given edges, we can define the order in which each task should precede.
\n A graph that allows for topological sorting must be acyclic (Directed Acyclic Graph, DAG).\n <\/p>\n

2. Approach to Solve the Problem<\/h3>\n

\n The basic approach to solving the problem is as follows:\n <\/p>\n

    \n
  1. Represent the precedence between the given tasks as a graph.<\/li>\n
  2. Calculate the indegree for each task.<\/li>\n
  3. Add tasks with an indegree of 0 to a queue.<\/li>\n
  4. Process tasks one by one from the queue and decrease the indegree of tasks connected to it.
    \n Tasks that become 0 indegree are added back to the queue.<\/li>\n
  5. Repeat until all tasks are processed.<\/li>\n
  6. Output the result of the topological sorting.<\/li>\n<\/ol>\n

    3. Implementation in JavaScript<\/h3>\n

    \n Now, let’s implement the JavaScript code according to the above steps.
    \n The code below performs topological sorting based on the given input.\n <\/p>\n

    \n        \n        function topologicalSort(N, edges) {\n            const graph = {};\n            const indegree = new Array(N + 1).fill(0);\n            const result = [];\n\n            \/\/ Create graph and initialize indegree\n            edges.forEach(([u, v]) => {\n                if (!graph[u]) graph[u] = [];\n                graph[u].push(v);\n                indegree[v]++;\n            });\n\n            const queue = [];\n            \n            \/\/ Add tasks with indegree of 0\n            for (let i = 1; i <= N; i++) {\n                if (indegree[i] === 0) {\n                    queue.push(i);\n                }\n            }\n\n            while (queue.length > 0) {\n                const node = queue.shift();\n                result.push(node);\n                \n                \/\/ Decrease indegree of connected nodes\n                if (graph[node]) {\n                    graph[node].forEach(neighbor => {\n                        indegree[neighbor]--;\n                        if (indegree[neighbor] === 0) {\n                            queue.push(neighbor);\n                        }\n                    });\n                }\n            }\n\n            \/\/ Check if topological sorting was possible.\n            if (result.length !== N) {\n                return \"A cycle exists.\";\n            }\n\n            return result;\n        }\n\n        \/\/ Input Example\n        const N = 6;\n        const edges = [\n            [6, 5],\n            [5, 4],\n            [4, 3],\n            [2, 5],\n            [3, 1],\n            [1, 2],\n        ];\n        console.log(topologicalSort(N, edges));\n        <\/code>\n    <\/pre>\n
    4. Code Explanation<\/h3>\n
    \n        I will now explain how to implement topological sorting through the above code.\n    <\/p>\n