• Post Reply Bookmark Topic Watch Topic
  • New Topic

Breadth first search

David Spencer
Posts: 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi, im new to the ranch and i know this is a big question for a first time!But here goes

Ive got the code given below which can only bee changed ion the main method.
It does a Breadth first search between two islands. Now i have made classes that represtent the islands and there ok, but the method requires a journey class and i have no idea what it needs to do as im having difficulty trying to work out what the method uses from it.
In the main method i will creat teh variables that the method needs, but im stuck on journey class and the mothods they contain. (journey(), getLastIsland() add()inRoute()

ANy helpo much appreciated

public class Search {
* Carries out a breadth first search between two islands. Method
* is provided with start and end islands, a list of islands to
* search through and the maximum distance that can be travelled
* between islands in a single step.
* @param start Island at start of journey
* @param end Island at end of journey
* @param islands list of Island objects to be searched
* @param max_jump maximum distance which can be travelled between islands
* in any step
public Journey BreadthFirstSearch(Island start,
Island end,
ArrayList islands,
int max_jump) {

// routes contains a list of possible routes through the islands
// of a particular length as they are being generated
ArrayList routes = new ArrayList();

// List of complete possible routes between the two islands
ArrayList completeRoutes = new ArrayList();

// Create the first route which just consists of the start island
// add add it to routes
Journey journey = new Journey();

while(true) {
// List of routes that are found this iteration
ArrayList updated_routes = new ArrayList();

// Extend each journey by trying to add each island to it.
// Don't add an island if (1) it is already in the journey
// or (2) the distance between the last island in the route and
// the one being added is too far
for(int i = 0; i < routes.size(); i++) {
Journey jor = (Journey)routes.get(i);

for(int j = 0; j < islands.size(); j++) {

// Check that this island isn't already in the route
if(jor.inRoute((Island)islands.get(j))) {
} //if

// Check that the distance from this island to the last one
// isn't too long
Island isl = jor.getLastIsland();
if(isl.getDistance((Island)islands.get(j)) >
max_jump) {
} //if

// Create a new journey by adding this island to a copy
// of the curent one
Journey new_journey = ((Journey)routes.get(i)).copy();

// If this journey is a complete route between the start
// and end islands then store it as a possibleRoute.
// Otherwise it is a partial route so store it to be
// extended at the next iteration
if(((Island)islands.get(j)).equals(end)) {
} else {
} //if/else

} //for

// Replace routes with updated routes
routes = updated_routes;
} //for

// Don't try to extend the routes if none were genereted
// this time
if(updated_routes.size() == 0) {
} //if

} //while

// Check to see whether any possible routes were generated
// If there were none then create a route with no islands and
// return that
if(completeRoutes.size() == 0) {
// Return an empty journey
Journey empty = new Journey();
return empty;
} else {
// If some routes were created then go through them and
// find the shortest one
Journey shortest_route = (Journey)completeRoutes.get(0);
for(int i = 0; i < completeRoutes.size(); i++) {
if(((Journey)completeRoutes.get(i)).length() <
shortest_route.length()) {

shortest_route = (Journey)completeRoutes.get(i);
} //if
} //for

return shortest_route;
} //if/else

} // public BreadthFirstSearch
public static void main(String[] args) {
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!