0% completed
Topological Sort (medium)
Topological Sort is used to find a linear ordering of elements that have dependencies on each other. For example, if event B is dependent on event A, A comes before B in topological ordering.
This pattern defines an easy way to understand the technique for performing topological sorting of a set of elements and then solves a few problems using it.
Let's see this pattern in action.
.....
.....
.....
Faraz Ahmed
· 3 months ago
more straight forward answer in js:
class Solution {
sort(vertices, edges) { const result = []; const graph = Array.from({length:vertices},() => [])
//adjacency list for(let [u,v] of edges) { graph[u].push(v) }
let inDegreeList = Array(vertices).fill(0)
for(let neighbors of graph) { for(let neighbor of neighbors) { inDegreeList[neighbor]++ } }
const queue = []
for(let i=0; i< vertices;i++) { if(inDegreeList[i] === 0) { queue.push(i) } } while(queue.length) { const curr = queue.shift() result.push(curr) //explore neighbors for(let neighbor of graph[curr]) { inDegreeList[neighbor]--
if(inDegreeL
Trang Luong
· a year ago
from collections import deque, defaultdict class Solution: # BFS # def sort(self, vertices, edges): # in_degree = [0] * vertices # adj_list = defaultdict(list) # for from_node, to_node in edges: # adj_list[from_node].append(to_node) # in_degree[to_node] += 1 # queue = deque() # for node_index in range(len(in_degree)): # if in_degree[node_index] == 0: # source node, can be processed and remove # queue.append(node_index) # result = [] # while queue: # current_node = queue.popleft() # result.append(current_node) # for neighbor in adj_list[current_node]: # in_degree[neighbor] -= 1 # if in_degree[neighbor] == 0: # queue.append(neighbor) # if len(result) != vertices: #
makarand.h
· 2 years ago
For input
7, [[6, 4], [6, 2], [5, 3], [5, 4], [3, 0], [3, 1], [3, 2], [4, 1]],
This is a valid output but it's not accepting:
[5,6,3,4,0,1,2]
Tobby Lie
· 2 years ago
I believe this is a wrong evaluation of a valid test case
Wrong Answer 0.134 ms
Your Input
4
[[3,2],[3,0],[2,0],[2,1]]
Output
[3,2,1,0]
Expected
[3,2,0,1]
It's clearly valid from the example 2
Example 2
Input: Vertices=4, Edges=[3, 2], [3, 0], [2, 0], [2, 1] Output: Following are the two valid topological sorts for the given graph: 1) 3, 2, 0, 1 2) 3, 2, 1, 0
Here is my code using a dfs approach
from collections import defaultdict class Solution: def top_sort_util_dfs(self, graph, node, visited, in_progress, stack): visited[node] = True in_progress.add(node) for neighbor in graph[node]: if neighbor in in_progress: return False # Cycle detected if not visited[neighbor]: if not self.top_sort_util_df
sujay.gunjal
· 3 years ago
5
[[4,2],[4,3],[2,0],[2,1],[3,1]]
The expected output is not correct.
zaid
· 3 years ago
5 [[4,2],[4,3],[2,0],[2,1],[3,1]]
Mikhail Putilov
· 3 years ago
I stumbled upon on different sources that DFS as well can be used to solve this task. I can't say how important that is, but it seems that it is important. At least, reading the article gives an intuition that only BFS is the viable approach.
Matthew Espinoza
· 4 years ago
I'm confused on the line:
inDegree.put(i,0); graph.put(i, new ArrayList());
what exactly are they looking to achieve?
wuinko
· 4 years ago
Is [6, 5, 3, 4, 0, 2, 1] also a valid sort output for example 3?
Mike Palarz
· 4 years ago
It's not clear to me why this is indicative of a cycle in the graph:
if (sortedOrder.size() != vertices) // topological sort is not possible as the graph has a cycle return new ArrayList();
If there's a cycle, then wouldn't the algorithm have just ran endlessly?
Reading Progress
0%