アルゴリズムにおけるトポロジカルな並べ替えの正しい使用

Question

N語と標準辞書のk開始アルファベットを有するエイリアン言語のソートされた辞書が与えられると、タスクは言語の文字の順序を示す文字列を返す関数を完成させることです。

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

私はすでにオンラインいくつかの記事を参照してトポロジカルソートを使用して、質問のためのソリューションを実装しますが、それらのどれもが、彼らはトポロジカル・ソートを使用しての意思決定に到着したのか言及していませんか？

質問：質問を解決するために、トポロジカルソートのようなグラフや概念をいつ使用するのか、誰が知ることができますか？参考

：

溶液は、与えられたリストをトラバースし、次の各文字列を比較することです。最初の不一致が見つかるたびに、グラフの2つの文字の間にエッジを追加し、次の2つの文字列を比較するために移動します。

グラフが準備完了したら、トポロジカルソートを適用します。

Answer 1

問題をさらに練習し、問題を解決する直感を磨かなければなりません。トポロジカルについては、トポロジカルなソートを使用できるいくつかのフラグを特定することから始めることができます。 1.
フラグトポロジカルソートが唯一のグラフはあなたの例のように、いくつかの操作によってDAGに変換することができDAG
2.に適用することもできるので、有向非巡回グラフ（DAG）です。有向グラフを強連結成分をマージすることでDAGに変換することができますか、何らかの形で問題をDAGに減らすことができます ノード間で線形が必要ですか？ 4.
は、私が今のところ持っているすべてです

（トポロジカル順序も迅速に重み付け有向非巡回グラフを通る最短経路を計算するために使用することができます）あなたが最短経路を見つけたいですか、私はしておこうこの回答を後で更新する

Answer 2

実際、グラフについては、オブジェクト間の関係を表現する方法が考えられます。ここでは、オブジェクトはアルファベットで、あなたは（2文字のxとyのために）3例1を把握しようとしている。

1）文字xがy

2の前に来る）文字yは、xの前に来ます

3）xおよびyは1と2が同時に起こることができないので

しかしながら、我々は、DAG（有向非巡回グラフを持っている任意の順序）に来ることができます。したがって、「DAGで注文を検索しようとしています」はトポロジカルソートのためにベルを呼び出します。実際、問題はトポロジカルソートを教えるために使用される古典的な問題と非常によく似ています。つまり、タスクyの前にバンチタスクとタスクxを実行しなければなりません。

しかし、人生のあらゆるスキルがすぐに使用するアルゴリズムを区別できるように、経験と多くの練習の結果です。