java在迷宫中寻找最短路径

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，所以这不像是面向矩阵的问题。你有一个末端房间，你必须找到从起始房间开始的最短路径（比较房间的名称）。结果应该是这样的：

开始：厨房

完：厕所

路径：厨房、客厅、走廊、卧室、卫生间

我想我必须对房间使用一些递归，我想我应该保存我已经在堆栈中的位置。但我真的不知道如何开始

你们几个CS能帮我吗？谢谢

Answer 1

你想写一个广度优先的搜索。关于这个话题，有很多可用的资源

Answer 2

你在找BFS

在您的例子中，图G = (V,E)实际上是V= { all rooms }和E = {(u,v), (v,u) | u and v are neighboring rooms }

请注意，在算法开始之前，您并不关心没有所有边[邻居]——您知道如何使用neighbors字段动态计算相关的边集[和房间]。
这是真的，因为你需要使用的每一条“边”都是在你发现路径中距离源较近的房间时“发现”的

你可以看看this post——运行BFS后如何找到实际路径