このグラフにDFSを使用して、このグラフ

Question

にDFSによって得られた溶液経路は何、ノードは、（複数の後続ノードのために、ノードは「フロンティアにプッシュされ、次の順序で訪問されます"）アルファベット順に：

S-> A-> E-> D-> F-> G

その訪問順序はaswell溶液パスですか？もしそうなら、なぜGはSの> A→E→Gではないのですか？

PS：新しいアルゴリズムですので、私が明確に概念を理解していない場合は、教えてください。

Answer 1

ノードにアクセスする場合、DFSアプローチは隣接リストの作成順序に基づいてグラフをトラバースします。

挿入ノードの順序は、E年代の後継は、次の方法であってもよく、例えば：

1- E-> D, G 
2- E-> G, D 

最初の方法では、直接D->F->G又はD->Gを横断し、両方のケースでは、ノードを訪問しますGがノードEのいずれかの後継ノードを通過する前に、ノードDまたはFからノードGが既に訪問されているため、S->A->E->Gのパスをトラバースできなくなります。

第二の方法では、直接E->Gを横断しますので、これはパスS->A->E->Gを横断になりますが、それはすでにノードEから訪問されるためにも、あなたはノードDかFからノードGにアクセスすることはできません。

trueまたはfalseで訪問している場合、前のシナリオは発生しますが、エッジのコストを使用して最短の経路を見つけようとする場合は、Dijkstraのアルゴリズムを使用してあなたがそれに精通していない場合はhereについてさらに読むことができます。

Answer 2

私は、次のノードを決定するためのヒューリスティックコストとエッジコストの両方を考慮していると仮定します。

それはその三つの可能性を見てSから：

A = 9 + 13 = 21 
B = 14 + 14 = 28 
C = 15 + 15 = 30 

それはその後、Aを選択し、Aからその利用可能のパスを見て、私たちは二つの可能性を持っているEからE.

に行きます：

D = 2 + 8 = 10 
G = 19 + 0 = 19 

その後、Dを選択すると、今では二つの可能性があります。

を

そのネクタイそうに依存するアルゴリズムは、それを設定して、あなたが与えた解決策は、それは、2つの可能性があるFに行く方法：

E = 6 + 7 = 13 
G = 6 + 0 = 6 

それはその後、Gになり、最終的にそれがこのことを認識し目標ノードであり、状態シーケンスを返す。