リンクされた単語を探す

Question

現在、私は特定のカテゴリにリンクされた単語を表す有向グラフを持っています。ここに小さな表記があります。

私が解決しようとしている問題は、例えば、 cyclingために、私は（写真のように切断されたグラフのような1つまたは接続をすることができる）のカテゴリを見つける必要があり、単語が与えられ

。 cyclingには、exerciseとentertainment

の2つのカテゴリがあります。どのトラバーサルアルゴリズムが問題を解決するのに最適でしょうか？データ構造の面では、与えられた入力ワードの直近のカテゴリを探す際に、より多くのメモリと時間効率がある他の選択肢がありますか？

Answer 1

ノードはラベル付けされていますか？頂点にラベルを追加することができます。各頂点にcategoryとnon-categoryとラベルを付けます。

シンプルなソリューション

最初にあなたがして、グラフ内の単語を検索するすべてのカテゴリとサブカテゴリを見つけるためDFSを使用する必要があります。

解決策2あなたがカテゴリの一つの層を持っている場合にのみ

• は、グラフ内のランダムなノードを選択してください。
• このノードのカテゴリを検索
• あなたの単語が存在する場合は、各カテゴリを検索してください。
• このカテゴリに含まれるすべての単語には、
• すべてのノードが使用されるまでこの手順を繰り返します。