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

Question

我正在尝试用 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

直到第四步，一切都做对了。

可以在此处看到节点图: Romania Tree

这些是我的类(class):

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);
}
}

Answer 1

很抱歉，你做错了很多。

1. 看看你的 map 。这些数字来自哪里？ 140是到锡比乌的距离。但你不是要去蒂米什瓦拉吗？如果您从阿拉德开始，而您访问过的城市列表只包含阿拉德，为什么会有任何距离？查看您的输出和 map ，看看它是否有意义。直到第 4 步它肯定不会工作。

2. 如果您到达布加勒斯特，您将如何检测？它不在你插入和弹出城市的 for 循环中。也许先检查布加勒斯特是否在连接列表中。

3. 你打算如何回溯？您不会在任何地方从访问过的列表中弹出城市。如果你没有到达布加勒斯特就走到了死胡同，会发生什么？

4. 无限循环的出现是因为您在 for 循环的前半部分插入一个城市一次，然后在 while 循环中将其弹出，但是您的算法是错误的，所以您永远不会前进。它进入了一个循环，因为此时恰好您只是在 for 循环中插入一个城市，然后弹出它并再次执行。

要找出您做错了什么，请在 for 循环末尾和 while 循环中打印出两个城市列表(visited 和 cityList)，确保您可以分辨出每一行的打印位置。他们不是你想的那样。

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