Category: Directed Graph

Written by Bilbo

Topological Sort

DFS Use a stack to store nodes in topological order. Use a set to track visited node. Run dfs, where a node is pushed onto stack after all its children has been visited. This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file […]

Written by Bilbo

Alien Order

Alien Order Given a sorted dictionary of words of an alien language. Determine the alphabetical order of the alien language. Directed Graph Problem. Similar to reconstruct itinerary problem.  BFS/Topological Sort The core idea is to keep comparing two consecutive words, which gives one piece of information at a time of which char is before which […]