jQuery in Action, 2nd edition*
The moose likes Java in General and the fly likes Breadth first search Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Android Security Essentials Live Lessons this week in the Android forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "Breadth first search" Watch "Breadth first search" New topic
Author

Breadth first search

David Spencer
Greenhorn

Joined: May 04, 2006
Posts: 1
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();
journey.add(start);
routes.add(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))) {
continue;
} //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) {
continue;
} //if

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

// 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)) {
completeRoutes.add(new_journey);
} else {
updated_routes.add(new_journey);
} //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) {
break;
} //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) {
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Breadth first search
 
Similar Threads
Need help to convert from Con List to Link List
ArrayList add method causing Memory Overrun
Algorithm to find Nodes having largest distance in Binary tree.
Retrieving list from a map mapping to an arraylist
Graphs: Breadth First or Depth First?