#C - 単純なパス - 有向グラフ - 再帰

Question

私はグラフを学んだだけで、練習しようとしています。 R. Sedgewickの私の本には、私にとっては挑戦的な挑戦があります。再帰を伴う有向グラフ上の単純なパスを見つけなければならない。どこから始めたらいいのか分かりません。 手がかりは何ですか？

Answer 1

アルゴリズム的に言えば、開始頂点から所望の末端頂点までの単純な経路が存在する場合、これはによって見つけることができる。このアプローチは再帰的であり、再帰的にも反復的にも（明示的なスタックを使用して）実装できます。

実装上は、グラフをどのようにデータ構造内に表現するかを計画することは価値あることです。最も一般的な実装は、各ノードが後継者のリスト（Cでは、ノードを表すstructであり、idと後継ノードである他のノードへのポインタのリストを持つ）または接近行列としての表現です。