2

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);
}
}
1
  • 1
    Don't test string equality using ==, use equals(). Feb 14, 2015 at 3:39

2 Answers 2

1

Sorry to say, but you are doing so much wrong.

  1. 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.

  2. 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.

  3. 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?

  4. 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.

0

Make sure numconnections isn't going up in value while the for loop is running. This may be the reason

1
  • I added the city class. numconnections is hard coded its not affected by anything.
    – user23054
    Feb 14, 2015 at 3:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.