Topological Sort Introduction - Graph / Directed Graph / Topological Sort

Implementation should account for cycles but currently does not. Returns result indiscriminately .

Agree with Rock, does not account for cycles.
At the final return value, it simply needs a check for if (graph.size == res.size) return res else return null (or empty list, something to show it isn’t possible as the graph has 1+ cycles)

when are you going to add c++ codes in all chapters and c++ templates

solutions will be added in May/June.

It would be good to write type hints for python code,
took a while to find out what the type of “graph” is,
had to check in on the javascript code to realize it is a dict.

I believe this line in the summarization step is “repeat until the queue is empty. If any nodes remain unprocessed, then there must be a cycle.”


a suggestion to the team: use consistent terminology as pervious graph sections.

  1. We’ve been using “neighbors” to refer to nodes connected to the node with an edge. In this section, they suddenly becomes parents/child again, which is quite confusing for me and need some mental effort to get used to the new terminology.

  2. “counts” is indeed number of incoming edges (i.e., in degree) of a node. Personally, “inDegree” will be more sensible for me.

Thank you for the suggestion. We have revised the content to use more appropriate terminology.

thanks, it’s been updated

No DFS implementation of Topological Sort?

I found the implementation templates to be unclear because they don’t define what the “graph” variable is. Without knowing that, it made the findIndegree function incomprehensible until I looked at one of the other example problems.

The input graph is a Map where the keys are the nodes and the value is an array of neighbors that it points to.

Like other Algomoster users, I was confused too with this template as it lacks clarification on certain aspects, especially on the expected data type of the graph. From the code provided, it seems the graph should be represented as a Map where each key is a node and its value is an array of neighboring nodes. However, this could have been explained more clearly.

Another crucial point of ambiguity is in the findInDegree function. Specifically, the line inDegree.set(node, neighbor.get(node) + 1); can be misleading as it implies that the neighbor is a Map when it is actually a node. Hence, neighbor.get(node) is not valid. The corrected line should be inDegree.set(neighbor, inDegree.get(neighbor) + 1); as we are intending to increment the in-degree of the neighbor, not the node.

In conclusion, clearer instructions and explanations of the expected data structures can help users understand the logic behind the code better and avoid confusion.