特定の長さのグラフを1点で表示する

Question

私はすべての経路を与える方法が必要なセル番号 "n"との関係を持つすべてのセル番号を与えるメソッド "connection（int n）"を持っています特定の長さ "myLength"がセル番号 "start"から始まり、ちょうど一方向に（通常通り）私はいくつかのセルを複数回渡すことが許されないことを意味します あなたの助けを前もって感謝します PS私は地図ツール、グラフツール、基本ツールを使用することはできません。

Answer 1

あなたはBFSを探しています。標準BFSに加えて

モデルgraphG = (V,E)なV = {1,...,n} [すべての可能な値]とE = { (u,v) | connection(u) returns v }とあなたの問題[uとvごconnection()方法を使用しての間の接続がある]

、あなたがする必要があります。限られた長さに達したときに別の停止条件を追加してください。

EDIT：
注このソリューションは、あなたがアップまでの長さパスを探していると仮定し、そしてない正確に長さこと。
正確にはのが必要な場合は、カウンタの例がcliqueの場合、BFSは機能しません。

正確に長さの簡単なパスを持っているすべての頂点を取得するには - あなたはおそらくループを回避DFSは、[各反復修正されsetを維持することによって行うことができます]が、より各頂点を探索することができますが必要になりますが一度。