Graph Algorithms • Decoding

Alien Dictionary

Reconstruct the unknown alphabet of an alien language from a sorted dictionary. Build a dependency graph and use Topological Sort to reveal the hidden sequence.

Try Interactive Simulator

Lexicography

Comparing adjacent words reveals precedence. If "abc" comes before "abd", then 'c' comes before 'd'.

Directed Edges

Each precedence relation a → b is a directed edge in our character graph.

Topo Sort

We apply Kahn's Algorithm on the character graph. A valid sort order gives the alphabet. A cycle implies no valid order.

Complexity

Where N is total characters in words and K is alphabet size. We process every char once.

↔️ Drag nodes to reposition • 🖱️ Update dictionary above

Dictionary

wrt

wrf

ett

rftt

Result

Decoding...

Loading Lab...

Graph Algorithms • Decoding

Alien Dictionary

Reconstruct the unknown alphabet of an alien language from a sorted dictionary. Build a dependency graph and use Topological Sort to reveal the hidden sequence.

Try Interactive Simulator

Lexicography

Comparing adjacent words reveals precedence. If "abc" comes before "abd", then 'c' comes before 'd'.

Directed Edges

Each precedence relation a → b is a directed edge in our character graph.

Topo Sort

We apply Kahn's Algorithm on the character graph. A valid sort order gives the alphabet. A cycle implies no valid order.

Complexity

Where N is total characters in words and K is alphabet size. We process every char once.

↔️ Drag nodes to reposition • 🖱️ Update dictionary above

Dictionary

wrt

wrf

ett

rftt

Result

Decoding...