传递节点对象时，深度优先搜索无限循环

我正在尝试用Java实现深度优先搜索算法。知道为什么这个方法会进入一个无限循环吗？

    public static void searchmap(map Romania)
{

Problem?----->  citylist.push(current.getcity(nextCity));

正如您在CMD中看到的，当Drobeta没有添加到已访问城市的ArrayList中时，就会发生无限循环。有什么想法为什么不添加这个吗？

Step 1, In Arad, Distance       140
Zerind
[Arad]
Timisoara
[Arad]
Step 2, In Timisoara, Distance  258
Lugoj
[Arad, Timisoara]
Step 3, In Lugoj, Distance      369
Mehadia
[Arad, Timisoara, Lugoj]
Step 4, In Mehadia, Distance    444
Lugoj
[Arad, Timisoara, Lugoj, Mehadia]
Timisoara
[Arad, Timisoara, Lugoj, Mehadia]
Mehadia
[Arad, Timisoara, Lugoj, Mehadia]
**Drobeta**
[Arad, Timisoara, Lugoj, Mehadia]
Lugoj
[Arad, Timisoara, Lugoj, Mehadia]
Timisoara
[Arad, Timisoara, Lugoj, Mehadia]
Mehadia
[Arad, Timisoara, Lugoj, Mehadia]
**Drobeta**
[Arad, Timisoara, Lugoj, Mehadia]
Lugoj

直到第4步，一切都做得很好。

节点图如下所示：罗马尼亚树

这些是我的课程：

import java.util.ArrayList;

public class city
{
private String name;
private int numconnections = 0;
private ArrayList nextcity = new ArrayList();
private ArrayList distance = new ArrayList();
// Straight line distance to Bucharest
private int SLD;

// Hacks to make searching meaningful and illustrative. See source.
public int depth;
public city camefrom;
public boolean visited;
public city (String n, int s)
{
    this.name = n;
    this.SLD = s;
}
@SuppressWarnings ("unchecked") 
public void addconnection (city conn, int dist)
{
    numconnections++;
    nextcity.add (conn);
    distance.add (dist);
}
public int getSLD()
{
    return this.SLD;
}
public int getconnections()
{
    return numconnections;
}
public city getcity (int index)
{
    return (city)nextcity.get(index);
}
public int getdist (int index)
{
    return (int)distance.get(index);
}
public String getname()
{
    return this.name;
}
}


public class map
{
city Oradea =       new city ("Oradea", 380);
city Zerind =       new city ("Zerind", 374);
city Arad =     new city ("Arad", 366);
city Timisoara =    new city ("Timisoara", 329);
city Lugoj =        new city ("Lugoj", 244);
city Mehadia =      new city ("Mehadia", 241);
city Drobeta =      new city ("Drobeta", 242);
city Craiova =      new city ("Craiova", 160);
city Rimnicu =      new city ("Rimnicu", 193);
city Sibiu =        new city ("Sibiu", 253);
city Pitesi =       new city ("Pitesi", 100);
city Fagaras =      new city ("Fagaras", 176);
city Bucharest =    new city ("Bucharest", 0);
city Giurgiu =      new city ("Giurgiu", 77);
city Hirsova =      new city ("Hirsova", 151);
city Eforie =       new city ("Eforie", 161);
city Urziceni =     new city ("Urziceni", 80);
city Vaslui =       new city ("Vaslui", 199);
city Iasi =     new city ("Iasi", 226);
city Neamt =        new city ("Neamt", 234);
public map ()
{
    Oradea.addconnection (Zerind, 71);
    Oradea.addconnection (Sibiu, 151);
    Zerind.addconnection (Oradea, 71);
    Zerind.addconnection (Arad, 75);
    Arad.addconnection (Sibiu, 140);
    Arad.addconnection (Zerind, 75);
    Arad.addconnection (Timisoara, 118);
    Timisoara.addconnection (Arad, 118);
    Timisoara.addconnection (Lugoj, 111);
    Lugoj.addconnection (Timisoara, 111);
    Lugoj.addconnection (Mehadia, 70);
    Mehadia.addconnection (Drobeta, 75);
    Mehadia.addconnection (Lugoj, 70);
    Drobeta.addconnection (Mehadia, 75);
    Drobeta.addconnection (Craiova, 120);
    Craiova.addconnection (Drobeta, 120);
    Craiova.addconnection (Rimnicu, 146);
    Craiova.addconnection (Pitesi, 120);
    Rimnicu.addconnection (Craiova, 146);
    Rimnicu.addconnection (Sibiu, 80);
    Rimnicu.addconnection (Pitesi, 97);
    Sibiu.addconnection (Arad, 140);
    Sibiu.addconnection (Oradea, 151);
    Sibiu.addconnection (Fagaras, 99);
    Sibiu.addconnection (Rimnicu, 80);
    Pitesi.addconnection (Craiova, 120);
    Pitesi.addconnection (Rimnicu, 97);
    Pitesi.addconnection (Bucharest, 101);
    Fagaras.addconnection (Sibiu, 99);
    Fagaras.addconnection (Bucharest, 211);
    Bucharest.addconnection (Fagaras, 211);
    Bucharest.addconnection (Pitesi, 101);
    Bucharest.addconnection (Giurgiu, 90);
    Bucharest.addconnection (Urziceni, 85);
    Giurgiu.addconnection (Bucharest, 90);
    Urziceni.addconnection (Hirsova, 98);
    Urziceni.addconnection (Bucharest, 85);
    Urziceni.addconnection (Vaslui, 142);
    Hirsova.addconnection (Eforie, 86);
    Hirsova.addconnection (Urziceni, 98);
    Eforie.addconnection (Hirsova, 86);
    Vaslui.addconnection (Urziceni, 142);
    Vaslui.addconnection (Iasi, 92);
    Iasi.addconnection (Vaslui, 92);
    Iasi.addconnection (Neamt, 87);
    Neamt.addconnection (Iasi, 87);
}
}

很抱歉，你做错了太多。

看看你的地图。这些数字是从哪里来的？140是到锡比乌的距离。但你不是要去蒂米索拉吗？如果你从阿拉德开始，而你的访问城市列表中只包含阿拉德，为什么会有任何距离？看看你的输出和地图，看看它是否有意义。当然，直到第4步，它才开始工作。
如果你到达布加勒斯特，你将如何检测？它不在for循环中，这是你推动和弹出城市的地方。也许先检查一下布加勒斯特是否在连接列表中。
你打算怎么回到正轨？您不会在任何地方从访问列表中弹出城市。如果你没有到达布加勒斯特就走到了死胡同，会发生什么？
无限循环的产生是因为你在for循环的前半部分推送一个城市一次，然后在while循环中弹出它，但你的算法是错误的，所以你永远不会进步。它达到了一个循环，因为在这一点上，你只会在循环中推动一个城市，然后弹出它，再做一次。

要弄清楚你做错了什么，请在for循环和while循环的末尾打印出两个城市列表（visited和cityList），确保你可以从每一行的打印位置分辨出来。它们不是你想象的那样。

由于这是深度优先搜索，也许您应该考虑使用递归函数。

确保在for循环运行时numconnections的值不会上升。这可能是

的原因

相关内容

最新更新

热门标签：