迷路で最短経路を見つける

Question

私はプログラムする方法を学ぶアマチュアプログラマーです。

class Room { 
    String name; 
    ArrayList<Room> neighbors = new ArrayList<Room>(); 

    // constructor with name 
    // getters 
    void addNeighbor(Room room) { 
     neighbors.add(room); 
    } 
} 

class Finder { 
    void findShortestPath(Room start, Room end) { 
     // ? 
    } 
} 

すべての部屋には、いくつかの隣人を持っている：私はこの些細な問題でつらい時を持っているので、 は、私は任意のコンピュータサイエンスのコースを持っていたことがありません。 4を超えると、マトリックス指向の問題に似ていません。あなたは終わりの部屋を与えられています。部屋の名前を比較して、最初の部屋から最短の経路を見つけなければなりません。

スタート：：キッチン

終了：トイレ

パス：キッチン、リビングルーム、廊下、ベッドルーム、トイレ

私は私はいくつかの再帰を使用しなければならないと思う結果が「道」のようにする必要があります部屋と私は私がすでにいくつかのスタックにあった場所を保存する必要がありますと思う。しかし、私は実際に始める方法を知らない。

あなたのうちの何人かは私を助けてくれますか？ありがとう

Answer 1

あなたはBFSをお探しですか？あなたは、関連セットを計算する方法を知っている - あなたの場合

は、グラフG = (V,E)は、実際には、アルゴリズムが始まる前に、あなたはすべてのエッジ[隣人]を持っていない気にしないV= { all rooms }とE = {(u,v), (v,u) | u and v are neighboring rooms }

注意ですneighborsフィールドを使用して、オンザフライでエッジと客室を検索します。
これは、パスに使用する必要があるすべての「エッジ」 - ソースに近い部屋を発見したときに「発見」されたためです。

this postを見ることができます.BFSを実行した後の実際のパスはどのようになっていますか。

Answer 2

幅優先検索を作成します。このトピックでは多くのリソースを利用できます。