Utilisation correcte du tri topologique dans les algorithmes

Question

Étant donné un dictionnaire trié d'un langage alien ayant N mots et k alphabets de départ du dictionnaire standard, la tâche consiste à compléter la fonction qui renvoie une chaîne indiquant l'ordre des caractères dans la langue.

Input: Dict[] = { "baa", "abcd", "abca", "cab", "cad" }, k = 4 
Output: Function returns "bdac" 
Here order of characters is 'b', 'd', 'a', 'c' 

je l'ai déjà mis en œuvre une solution pour la question à l'aide tri topologique en se référant à certains articles en ligne, mais aucun d'entre eux ont mentionné sont-ils arrivés à la décision d'utiliser tri topologique?

Question: Comment quelqu'un peut-il savoir quand utiliser des graphiques ou ses concepts comme tri topologique pour résoudre des questions?

Pour référence:

La solution consiste à parcourir la liste donnée et comparer chaque chaîne avec la suivante. Chaque fois que la première discordance est trouvée, ajouter un bord entre les deux caractères dans le graphique et passer à autre chose pour comparer les deux chaînes suivantes. Une fois que le graphe est prêt, appliquer un tri topologique.

Answer 1

Vous devrez pratiquer plus de questions et développer une intuition pour résoudre les problèmes. En ce qui concerne la topologie, vous pouvez commencer par identifier certains indicateurs où vous pourriez utiliser le tri topologique.
1. Est-ce le drapeau d'un graphe acyclique orienté (DAG), car tri topologique ne peut être appliqué à DAG
2. le graphique peut être converti en un DAG par une manipulation, comme votre exemple . Un graphique orienté peut être converti en un DAG en fusionnant Composants fortement connectés ou pouvez-vous réduire le problème en quelque sorte dans un DAG
3. Avez-vous besoin d'une sorte de linéaire parmi les nœuds?
4. Voulez-vous trouver le chemin le plus court (L'ordre topologique peut également être utilisé pour calculer rapidement les chemins les plus courts grâce à un graphique orienté acyclique)

C'est tout ce que j'ai pour l'instant, je garderai mettre à jour cette réponse plus tard

Answer 2

En fait, la façon dont je penserais à un graphique est qu'il représente les relations entre les objets. Ici, les objets sont alphabets, et que vous essayez de comprendre l'un des trois cas (deux lettres x et y):

1) lettre x vient avant y

2) lettre y vient avant x

3) x et y peuvent venir dans l'ordre

Cependant, depuis le 1 et 2 ne peut se produire en même temps, nous avons un DAG (graphe orienté acyclique). Ainsi, "essayer de trouver une commande dans un DAG" sonne la cloche pour tri topologique. En fait, le problème est maintenant très similaire au problème classique utilisé pour enseigner le tri topologique, c'est-à-dire que nous avons un tas de tâches et qu'une tâche doit être effectuée avant la tâche y, etc., trouver un ordre valide pour les tâches à effectuer.

Cependant, comme dans toutes les autres compétences de la vie, étant capable de distinguer quel algorithme utiliser immédiatement, est le résultat de l'expérience et beaucoup de pratique :)