Reputation: 21
I'm trying to implement a depth first search algorithm in Java. Any idea why this method is going into an infinite loop?
public static void searchmap(map Romania)
{
Problem?-----> citylist.push(current.getcity(nextCity));
As you can see in the CMD, the infinite loop occurs when Drobeta is not added to the ArrayList of visited cities. Any ideas why this is not added?
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
Up until the Step 4, everything was done right.
A graph of the nodes can be seen here: Romania Tree
These are my classes:
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);
}
}
Upvotes: 2
Views: 312
Reputation: 2536
Sorry to say, but you are doing so much wrong.
Look at your map. Where are the numbers coming from? 140 is the distance to Sibiu. But weren't you going to Timisoara? Why is there any distance at all if you start in Arad and your list of visited cities only contains Arad? Look at your output and the map and see if it makes any sense. It was certainly not working up until step 4.
How are you going to detect if you arrive at Bucharest? It isn't in the for loop which is where you're pushing and popping cities. Maybe check if Bucharest is in the list of connections first.
How are you going to back-track? You are not popping cities from the visited list anywhere. What happens if you reach a dead end without getting to Bucharest?
The infinite loop comes about because you're pushing a city once in the first half of your for loop and popping it in the while loop, but your algorithm is wrong so you never progress. It reaches a cycle because at that point it just happens that you're only pushing one city in the for loop, then popping it and doing it again.
To figure out what you're doing wrong, print out the two city lists (visited and cityList) at the end of the for loop and in the while loop, making sure you can tell from where each line is being printed. They are not what you think they are.
Since this is depth first search, maybe you should consider using a recursive function.
Upvotes: 1
Reputation: 15903
Make sure numconnections
isn't going up in value while the for loop is running. This may be the reason
Upvotes: 0