Be insensitive, and keep a lifelong growth mindset.

0%

Data Structure & Algorithms Notes: Topological Sort

Posted onEdited onDisqus:

I. Topological Sort Definition

First of all, what is topological Sort? Here is the definition from WikiPedia

In the field of computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

Originally, say we have a graph like this.

After the topological sort, we will get a list like this:

II. Topological Sort Algorithm

III. Topological Sort Problems

1. Alien Dictionary

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

For example, Given the following words in dictionary, ["wrt", "wrf", "er", "ett", "rftt"]