java - 在Java中使用BFS的两个城市之间的路径

Question

我试图建立一个数据结构来存储地图内容，例如道路和城市信息。我正在使用顶点/城市的链表，当创建一个顶点/城市时，它将在其构造函数中创建边的另一个链表。
我需要一种算法来找到两个随机城市之间的最短路径。
我修改过的BFS算法无法正常工作。
算法：

public void getPath(String from, String to) {
        Queue<cVertex> Q = new LinkedList<cVertex>();
        List<cVertex> visited = new LinkedList<cVertex>();
        cVertex l = null;
        for (int i = 0; i < c.size(); i++) {
            if (c.get(i).cityName.equals(to)) {
                l = c.get(i);
                break;
            }
        }
        for (cVertex a : c) {
            if (a.cityName.equals(from)) {
                // System.out.println(a.cityName);
                Q.add(a);
                System.out.println("\nPath from " + a.cityName + " to "
                        + l.cityName);
                break;
            }
        }
        while (!Q.isEmpty()) {
            cVertex u = Q.remove();
            System.out.print(u.cityName);
            if (u.cityName.equals(l.cityName)) {
                return;
            }
            System.out.print("-->");
            visited.add(u);
            for (cVertex w : c) {
                for (Edge e : w.list) {
                    Edge n = e;
                    for (cVertex d : c) {
                        if (d.cityName.equals(e.to)) {
                            if (!visited.contains(d) && !Q.contains(d))
                                Q.add(d);
                        }
                    }
                }
            }
        }
    }

我需要帮助！
e.to表示“ to”是与此边缘连接的城市名称。

Answer 1

您应该在问题中说“ c”是静态变量，并且它是cVertex的数组。
还显示在getPath函数中使用的所有类的声明和定义，例如：
您的问题中的cVertex和Edge类的字段，属性和方法。

我还希望您向我解释在Java中如何将LinkedList隐式转换为Queue和LinkedList转换为List。我只是想知道。我很感兴趣，因为在C＃中所有这些类都存在于System.Collections.Generic命名空间中，但是您不能将LinkedList隐式或显式地转换为Queue或List。

对于C＃：

Queue<cVertex> Q = new LinkedList<cVertex>();
List<cVertex> visited = new LinkedList<cVertex>();

即使在某处声明和定义了cVertex类，也禁止这样做，并且会出错。

但是无论如何，您的问题都很棒且具有挑战性。

不幸的是，我从未学习过Java，所以我无法向您发布我的语法和语法可能不正确的代码，但是我仍然理解了您的聪明问题，并且仍然可以为您提供帮助，所以我只告诉您我的想法和您必须做什么才能回答您的问题。

首先，从项目中删除或至少从getPath函数中使用的cVertex和Edge类中删除，并添加一个新类。将该类称为“城市”。此类的实例应将城市名称存储为字符串和类型为City的数组。
在此数组中，指的是您可以从this市通过一条道路，一辆公共汽车甚至是步行去的所有​​城市。

下一步是创建City类的实例，直到您在领土上创建了该国家的所有城市并将它们全部存储在一个阵列中为止。如果您想将此数组称为“ c”，则可以使用。当然，我了解该数组是静态的这一点非常重要，因此您将能够在许多其他函数中使用它。

现在，您需要一个函数，该函数接收字符串的一个参数（这是城市的名称），并从静态数组中返回对该名称的City实例的引用。

实现此功能非常简单。您只需进行for循环（遍历所有城市），然后检查for循环中当前城市的名称是否与string参数匹配。如果是，则在for循环中返回当前城市的参考，该功能将自动停止。如果找不到使用该名称的城市，则该函数当然会返回null。

您可以通过名称“ findCityByName”来调用此函数。

完成此功能后，下一步是将功能getPath从“ getPath”重命名为“ getPaths”（只需添加以在's'字母结尾），然后将此函数的返回类型从void更改为Boolean。此更改是好的，因为此函数的返回值将通知您该函数是成功还是失败。如果输入参数无效，该函数将失败并返回false。否则函数成功并返回true。

现在添加三个附加的非常必要的参数，以使该功能正常工作。

此函数的前两个参数仍然是两个城市的两个名称，您要像在问题中所张贴的那样使用字符串，但是第三个参数应该是City类型的列表。此列表存储对所有访问过的城市的引用。您可以通过名称“ visited”来访问此参数。您的错误是将“访问”定义为局部变量，而不是参数。

第四个参数也应该是一个列表，但必须是City类型的array类型。此列表中的每个数组仅存储对您必须先走的所有城市的引用，然后才能从外出的城市到达目标城市。该列表中的每个数组实际上都是一个路径。
此列表仅包含从“城市”到达目标城市的所有可能路径，其名称在此函数的前两个参数中指定为字符串。该列表实际上包含您期望从此功能获得的内容。

您可以通过名称“路径”来调用此参数。

第五个最后一个参数也应该是类型为City的列表，例如第三个参数的类型-“ visited”，但是此列表存储对访问过的城市的引用，但并不像“ visited”列表参数中那样存储对所有访问城市的引用。这是“已访问”列表参数与该参数之间的差异。每次对getPaths函数的调用结束时，都会删除此列表的最后一个元素，这与“已访问”列表参数中的情况不同。
“已访问”列表仅将城市引用添加到其自身。它永远不会删除它们，但是最后一个参数中的列表会删除它们。

您可以使用其他名称“ currentPath”来调用此参数。

请注意，您必须多次在此函数内调用此函数，此函数才能起作用！

此函数必须是递归的！

这些都是该函数的所有参数，但是始终要传递最后三个附加参数（第3、4和5）作为参考，而不是作为副本，这非常重要！！！

如果您将这些参数作为副本传递，则该功能将无法正常工作。

现在，终于让我们开始重写该函数的实现代码。

首先，调用“ findCityByName”函数两次，以获取用于查找城市之间所有可能路径的城市。如果其中一个或两个都是null，则return false立即停止功能，因为您无法计算两个都不存在或两个都不存在的城市之间的路径！该功能也会失败，因为前两个参数之一或两者均无效！

如果两个都不为空，那么两个城市都存在，那么您可以开始循环访问“出发”城市数组中的所有城市。

如果for循环中的当前城市是您要前往的目标城市，请分配一个大小为“ currentPath”列表的新数组，并将“ currentPath”列表中的所有引用复制到此数组，然后将其添加到“路径”列表并返回true以立即停止当前函数，因为找到了路径，并且参数对于当前getPath函数也有效。

否则（如果for循环中的当前城市不是目标城市，则）
在“已访问”和“ currentPath”两个列表中添加for循环中当前城市的引用，并调用getPaths函数，并在第一个参数中输入for循环中当前城市的名称。在第二，第三，第四和第五个参数中，分别输入当前调用的getPaths函数的第二，第三，第四和第五个参数（从标题中选取）。仍然不要忘记将第3，第4和第5参数作为引用传递，而不是将副本或函数传递不起作用！

我在else语句中告诉您要做的所有事情只有在“访问”列表中尚未包含对for循环中当前城市的引用时才发生！否则，循环继续到下一个城市。
重要的是先检查一下。

最后（在for循环之后），如果“ currentPath”不为空，则仅从“ currentPath”而不是“ visited”中删除最后一个引用！！！

然后return true。第一次调用getPaths函数的前两个参数有效。功能可能会成功。

这就是getPaths函数的所有声明，定义和实现。

请注意，每次调用此函数之前，必须为该函数在最后三个参数中获得的三个列表分配内存。在通过引用此函数传递这些列表之前，请通过空的构造函数，没有参数的构造函数或首先将新列表初始化为空的构造函数分配它们。这在第一次调用getPaths函数时非常重要，该函数全部列出了最后三个参数为空。

当对getPaths函数的第一次调用结束并且该函数成功执行时，只有“ currentPath”将保持为空。否则，只有“已访问”不会保留为空。如果函数成功，并且至少找到一条路径，则“路径”将填充数据。
只有“路径”很有趣，其他两个都不有趣，因为这是getPaths函数给出的答案。

准备好该路径列表之后，现在您需要通过以该列表的大小分配一个新数组，然后将其所有引用复制到该数组，从而将其转换为City的大型数组。

假数组是一个数组，它的类型也是数组。

现在让我们定义一个新函数：getShortestPath

此函数仅接收杂散的City数组的一个参数，并返回City数组。

实际上，它接收路径并返回最短路径。实现此功能的算法非常简单。

首先定义新的局部变量：名称“ minSize”，然后键入int并将其分配给虚拟数组中第一个数组的大小。

然后定义另一个新的局部变量：名称“ shortestPath”，并键入“ City的数组”，并将其设置为“假数组”中第一个数组的引用。

然后for循环其余数组（从第二个数组开始到最后一个数组），如果当前数组的大小小于“ minSize”的值，则将两个“ minSize”都设置为for中当前数组的大小循环和“ shortestPath”到for循环中当前数组的引用。

最后，在for循环之后，返回“ shortestPath”。

如果您有许多城市，并且getPaths工作时间过多，则可以将位置添加到City类中（X和Y坐标为双精度）。

然后删除或注释getShortestPath函数，并将函数getPaths从“ getPaths”重命名为“ getShortestPath”，然后删除或注释“ paths”参数以及与此参数有关的所有代码。还将参数“ currentPath”的名称更改为“ path”，并将此更改应用于函数中的所有匹配项。

还要在if语句中添加另一个AND条件，该条件是for循环中的else语句。
在其他条件下，检查for循环中的当前城市是否最接近目标城市。要知道您需要先在for循环之前向“ from”数组中的所有城市添加另一个for循环，请计算所有这些城市到目标城市的距离并将其添加到您之前分配的新双打本地列表中。然后声明，定义和实现一个函数，该函数返回双精度数列表中的最小双精度数。然后调用此函数以获取最近的城市到目标城市的距离，并将其保留在新的本地变量中：名称“ min”并键入double

在附加条件下，如果当前城市到目标城市的计算距离近似等于“ min”的值，则当前城市是最接近目标城市的城市。

还要定义，声明和实现一个新函数，该函数将接收City的两个参数，并将它们之间的距离返回两倍，并使用此函数为您提供帮助。

计算两点距离的数学表达式为：

sqrt（pow（x2-x1，2）+ pow（y2-y1，2））或sqrt（（x2-x1）^ 2 +（y2-y1）^ 2）

pow（a，b）= a ^ b，pow（n，2）= n ^ 2

同样在getShortestPath函数中（曾经被称为“ getPaths”调用）删除或注释了所有从“ path”中移除元素的行（曾经被称为“ currentPath”的调用）

在调用getShortestPath函数之前，新分配的列表路径为空，但是在调用之后以及通过引用传递它之后，将填充数据“ path”。它应该是“从”城市到“到”城市之间的最短路径。

发表评论，告诉我您是否也了解C＃，不仅Java。

我知道C＃，所以如果您告诉我，那么我会将代码发布到C＃中。

就这些。我希望这回答了你的问题。尝试这个想法，并发表评论以告诉我是否有帮助。

我祝你好运！ ：D