4

我是业余程序员，学习如何编程。我从来没有上过任何计算机科学课程，所以我很难解决这个小问题：

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 个，所以它不像面向矩阵的问题。你得到了结束房间，你必须找到从开始房间开始的最短路径（比较房间的名称）。结果应该是“方式”，如：

开始于：厨房

结束： 厕所

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

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

你们中的一些人可以帮助我吗？谢谢

4

2 回答 2

3

您正在寻找BFS。

在您的情况下，该图G = (V,E)实际上是V= { all rooms }E = {(u,v), (v,u) | u and v are neighboring rooms }

请注意，您不在乎在算法开始之前您没有所有边 [邻居] - 您知道如何使用该neighbors字段即时计算相关的边 [和房间] 集。
这是正确的，因为您需要用于路径的每个“边缘” - 当您发现距离源路径更近的房间时“发现”。

你可以看看这篇文章——如何在运行 BFS 后找到实际路径。

于 2012-03-24T21:30:43.123 回答
0

您想编写广度优先搜索。关于这个主题有很多可用的资源。

于 2012-03-24T21:31:10.130 回答