Welcome to this exciting journey into the world of Data Structures and Algorithms! Today, we're going to delve into a fascinating problem called the Alien Dictionary, which uses a technique called Topological Sort.
By the end of this lesson, you'll not only understand what Topological Sort is, but also how to solve the Alien Dictionary problem using it. Let's get started!
Imagine an alien language where words are written using an alphabet of 26 unique, unknown characters. We have a list of words from their dictionary, and we know that every word is formed by some of these characters. Our task is to find the lexicographical order of these words.
Topological Sort is a graph algorithm used to line up vertices in a directed acyclic graph (DAG) in a manner that every vertex with no incoming edges (in-degree 0) comes first. Once these vertices are removed, their adjacent vertices with no incoming edges become eligible to be removed, and so on, until the entire graph is processed.
This process is ideal for solving the Alien Dictionary problem because it allows us to arrange the words in the correct order based on their dependencies.
Let's implement a Topological Sort algorithm to solve the Alien Dictionary problem. We'll use an adjacency list and two helper functions: in_degree to calculate the in-degree of each word, and topological_sort to sort the words based on their dependencies.
from collections import defaultdict
def in_degree(adj, words):
degrees = defaultdict(int)
for word, neighbors in adj.items():
for neighbor in neighbors:
degrees[neighbor] += 1
return degrees
def topological_sort(adj, degrees, words):
sorted_words = []
queue = [word for word in words if degrees[word] == 0]
while queue:
word = queue.pop()
sorted_words.append(word)
for neighbor in adj[word]:
degrees[neighbor] -= 1
if degrees[neighbor] == 0:
queue.append(neighbor)
return sorted_words if sorted_words == words else None
# Example usage:
words = ["wrt", "wrf", "er", "ett", "rftt"]
adj = {
"wrt": ["wrf", "er"],
"wrf": ["wrt", "er"],
"er": ["wrt", "wrf", "ett"],
"ett": ["er"],
"rftt": []
}
sorted_words = topological_sort(adj, in_degree(adj, words), words)
print(sorted_words)In this example, we've defined a list of words and an adjacency list that represents their relationships. The in_degree function calculates the in-degree of each word, while the topological_sort function sorts the words based on their dependencies.
Congratulations on making it through this lesson on Topological Sort and the Alien Dictionary problem! By now, you should have a solid understanding of how to use Topological Sort to solve problems that involve dependencies between elements.
Keep practicing and applying this concept to other problems to reinforce your understanding. Happy coding! š