Grokking Graph Algorithms for Coding Interviews

0% completed

​

Solution: Topological Sort

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.

.....

.....

.....

Like the course? Get enrolled and start learning!
Z

zaid

· 3 years ago

5 [[4,2],[4,3],[2,0],[2,1],[3,1]]

Show 1 reply
S

sujay.gunjal

· 3 years ago

5

[[4,2],[4,3],[2,0],[2,1],[3,1]]

The expected output is not correct.

Show 1 reply
M

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]
W

wuinko

· 4 years ago

Is [6, 5, 3, 4, 0, 2, 1] also a valid sort output for example 3?

Show 1 reply
T

Tyler DeSouza

· 4 years ago

Is this Kahn's algorithm?

Show 1 reply
M

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?

Show 2 replies
M

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?

Show 1 reply
M

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.

Tobby Lie

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
Trang Luong

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:
  #