Breadth first search with java


DevX Home    Today's Headlines   Articles Archive   Tip Bank   Forums   

Page 1 of 2 12 LastLast
Results 1 to 15 of 27

Thread: Breadth first search with java

Hybrid View

  1. #1
    Join Date
    May 2005
    Posts
    115

    Breadth first search with java

    I have some problems building my breadth first search algorithm with java, hope u guys can help me..

    BFS basically is used to search a graph by dividing the graph into levels and searching a node, and its neighbour and its neighbour's neighbour (hope i'm correct with d concept)

    However, in my case i have to solve a travelling salesman problem where i have a distance table of 10 cities, A to J

    Code:
      public static DistanceTable getDefault(){
        String[] legends = {"A", "B", "C", "D", "E", "F", "G", "H", "I", "J"};
        double[][] distance = {{0.0},
                               {1.3, 0.0},  
                               {2.5, 5.8, 0.0},
                               {3.6, 4.3, 6.3, 0.0},
                               {4.2, 8.9, 4.5, 7.1, 0.0},
                               {5.9, 6.7, 8.1, 8.6, 7.6, 0.0},
                               {6.7, 5.4, 7.8, 6.4, 2.4, 4.8, 0.0},
                               {7.1, 2.6, 1.6, 2.1, 3.6, 6.3, 7.1, 0.0},
                               {8.4, 7.1, 3.8, 7.6, 1.2, 7.2, 5.5, 2.6, 0.0},
                               {9.8, 8.6, 1.0, 2.6, 4.5, 1.8, 4.6, 7.5, 9.9, 0.0},
                              };
    With this table, basically all nodes will have all other 9 nodes as neighbours. In this case, it is not possible to divide them into levels like a tree right?

    I'm suppose to list the top 10 solutions to this distance table and display the best solution.

    My idea to solving this problem is assuming A is the starting node. I'll compare all the other 9 neighbours of A and take the shortest edge, then i put the 2 nodes into the path list and compare the neighbours of the 2nd node, and so on..until i get a list of shortest paths through all 10 nodes and back to A. Is there any problem with this implementation?

    This is my assignment and i'm not asking for solutions here. I would appreciate if u guys could help me with d concepts..thx guys..

  2. #2
    Join Date
    Aug 2003
    Posts
    313
    If I understand your algorithm you are using what is termed a "greedy" approach. This is fine, but it does not garantee the best solution. For instance, the best path may start out with a very long edge, but as a whole the path is the shortest. In order to be garanteed to find the best possible solution, you will need to search all possible paths (however there are possible optimizations). Because cycles are not allowed in an optimal path, the easiest solution to this problem would probably be a depth-first search. i.e. assume A is the starting point then find the best path with A-B as the first edge then B-C the second edge, and so on. Then go back to A-C and C-B and so forth until you have traversed all possible permutations. There are several implementations of this algorithm, but ultimately to be garanteed the best solution, you will need to traverse the entire tree.

    A nice optimization to perform is to stop transversing a path once it gets longer than your shortest path.

    Hope this helps.
    ~evlich

  3. #3
    Join Date
    May 2005
    Posts
    115
    Thx 4 ur reply evlich..

    yeah, i've checked the results after i built my algo..it doesn't produce the best solution...after consulting with my lecturer, i guess i'm stuck with d exhaustive approach...

    about dfs, coz this is an assignment so im stuck with bfs...

  4. #4
    Join Date
    Aug 2003
    Posts
    313
    If you are stuck with BFS, then remember you will need to keep track of the nodes that you have visited for each node in the queue.
    ~evlich

  5. #5
    Join Date
    May 2005
    Posts
    115
    If i have 10 cities. That means that i have 9*8*7*6*5*4*3*2*1 = 362880 solutions rite?

  6. #6
    Join Date
    Jan 2005
    Location
    Reisterstowwn, MD
    Posts
    72
    Quote Originally Posted by Ant_Magma
    If i have 10 cities. That means that i have 9*8*7*6*5*4*3*2*1 = 362880 solutions rite?
    Yes 9! is the number of possible solutions.

    However I think you have some confusion about BFS or maybe i just misread your post. BFS will exhaust every path to every node that it hasn't already visited, so you can't just take take the shortest path off one node, thus eliminating all other paths, this is no longer a BFS search if your do.

    In your algorithm you should have a queue (to keep track of the next node to make the "current" node), an array (to keep track of which nodes have been visited), and an adjacency list (to keep track of the structure). If you don't know what an adjancey list is it is simply an array of linked lists.

    here is pesuedo code for a BFS algorithm:

    inputs:
    adj - adjacency list
    start - the start node

    Code:
    bfs(adj, start){
       n = adj.last
       for i = 1 to n
          visit[i] = false
       visit[start] = true
       q.enqueue(start) //same thing as adding, just a fancy word
       while(!q.empty()){
          current = q.front()
          q.dequeue() //same thing as removing
          trav = adj[current]
          while(trav != null){
             v = trav.ver
             if(!visit[v]){
                visit[v] = true
                q.enqueue(v)
             }
             trav = trav.next
           }
       }
    }
    This puesedo code is quoted from Richard Johnsonbaugh and Marcus Schaefer's book entitled "Algorithms" (p. 183).

    the objects in your adjancey list are simply nodes that hold information about the city they represent and have a link to another node (thus a linked list).

    Now, with all that said, this is the base you use to buid an algorithm that finds the shortest paths. Like evilich said you seem to have a greedy approach, which is fine, but may not always give you the optimal answer. However, there is a greedy algorithm, that always finds the shortest path from a start to end vertex. It's name is Dijkstra's Algorithm. But for your case I think there needs to be a different approach.

    Since you have to compute a top 10 list, it might be best to just run the BFS and then have an algorithm that computers every single possible path from the adjancey list, and as its computing these paths it places them in an array of size 10 based on their total cost (the first 10 computations will go into the array no matter what). If the cost of the path is not greater than the last position in the array, then you know it should be added somewhere and the rest should get bumped back. The only problem with this approach is in worst case it will take O(n3) time (n time to compute all paths, n time to place the value to the front of the array, n time to shift the array, cubic, not good!). But you can eliveate this by using a smart search algorithm on your array that holds the top 10. Personally, I would use the last method I suggest (run the BFS, and then use the adjacency list to compute the value of all paths, keeping an array of top 10 as you do so). With a proper algorithm to parse your top 10 array, I think the full process could be ran in a O(n lg n) time.

    Anyways I hope I helped, I know this stuff can be confusing.
    Java has 99 problems but a pointer ain't one

  7. #7
    Join Date
    May 2005
    Posts
    115
    Thx alot customwoodtek. It seems u have really put it some time to reply my thread. Appreciate it alot...

    Question:
    For java, how do i implement this 'queue'? using Arrays? I haven't learned linked lists yet, so i'm sort of stuck with arrays at this moment...

    I'm currently experimenting and developing my algorithm for the exhaustive method. Alot of problems with the logic and loops. My lecturer has made it 'easy' for us by setting the starting point at A (instead of any points from A to J). When i have some codes working, i'll post it here and u guys can take a looks...

    Thx alot guys...

  8. #8
    Join Date
    Jan 2005
    Location
    Reisterstowwn, MD
    Posts
    72
    Quote Originally Posted by Ant_Magma
    Thx alot customwoodtek. It seems u have really put it some time to reply my thread. Appreciate it alot...

    Question:
    For java, how do i implement this 'queue'? using Arrays? I haven't learned linked lists yet, so i'm sort of stuck with arrays at this moment...

    I'm currently experimenting and developing my algorithm for the exhaustive method. Alot of problems with the logic and loops. My lecturer has made it 'easy' for us by setting the starting point at A (instead of any points from A to J). When i have some codes working, i'll post it here and u guys can take a looks...

    Thx alot guys...
    Don't take this personally, but if you do not understand the implementation of basic data structures such as a queue and linked lists than i'm afraid this problem might be over your head. This is not your fault but rather sounds like your school's/teacher's fault. I take it you are in some type of algorithms class, this class should have a prerequsite Data Structures class or the teacher should be teaching you these data structures as they are needed to implement the algorithm.

    this shouldn't discourage you thought becaue luckily these data structures are simple in concept and also are already implemented in the Collections framework in java's standard libraries (however you should also know how to implement them yourself as it will help you better understand them.

    You can find an already implemented queue in java's Collection framework, more specifically java.util.concurrent.ArrayBlockingQueue

    As for a linked list, here is a quick breakdown. A linked list is a lot like an array. It has "areas" or "boxes" of storage where you place your data. Arrays are good for times when you know the location of an object or piece of data and you want to access it in constant time, but it is bad for insertions and deletions when there can be no gaps in your data (you essentially have to "shift" all the data, which takes linear time). Linked lists are good for inserting and deleting in constant time, but bad when trying to access an item (beacause unless you keep a pointer to each node or "box" you have to parse the list everytime to locate an item). Anyways, a linked list is a list of nodes. In a singly linked list each node has a pointer to the next node in the list, and you will have a head pointer that always points to the front of this list. Also the node will hold a pointer to an object that contains the data you whish to store. Here is a simple example:

    You have a bunch of cities you whish to store in a linked list. First you would crreate a cities class that holds relevant information about the city. In your case this might be the name, its adjacent cities, and the distance to them. You would then create a node class that stores a pointer to another node and a pointer to your city object. You would then create a class called LinkedList that has a pointer to the first node in the llist, and a method to create a new node (which would probably consist of calling the city constructore, and then calling the node constructor passing it the city object as a parameter.

    This is all easy to do but fournately the nice java developers already implement a linked list for you (java.util.LinkedList). So now you just need to create a city class and create a linked list of cities. In j2se 1.5 that would go something like this

    Code:
    LinkedList<MyCityClass> cityList = new LinkedList<MyCityClass>();
    
    MyCityClass cityA = new MyCityClass("city a", new String[] {"b","c","d"}, new int[] {3, 56, 12});
    
    cityList.add(cityA);
    If you get an error abaout the < > symbols you are using j2se 1.4.2 or previous, just remove them, and any time you pull something out of the list you have to cast it.

    I could show you a lot more, but I figured this should be enough for you to chew for now. If this feels beyond you for some reason then scrap everything i'm saying and ask your professor for some help. If you think your ok feel free to ask more questions.
    Java has 99 problems but a pointer ain't one

  9. #9
    Join Date
    May 2005
    Posts
    115
    Since my teacher haven't taught linked list, so i had to use arrays for now. I'll try to study ahead on linked list..thx customwoodtek

  10. #10
    Join Date
    May 2005
    Posts
    115
    This is what i've done so far. I'm trying on 3 cities first instead of 10 cities..i'm sorry its kinda messy...

    Code:
    public class Test3{
    	private String[] legends;
    	private double[][] length;
    
    
    
    
    	public Test3(String[] legends, double[][] length){
    		this.legends = legends;
    		this.length = length;;
    	}
    
    	public double getDistance(int from, int to){
    		if(from > to)
    			return length[from][to];  
    		else
    			return length[to][from];
      		}
    
    
    	public static Test3 getDefault(){
    		String[] legends = 	{"A", "B", "C", "D", "E", "F", "G", "H", "I", "J"};
    		double[][] distance =	{{0.0},
    					{1.3, 0.0},  
             				{2.5, 5.8, 0.0},
           					{3.6, 4.3, 6.3, 0.0},
    		          		{4.2, 8.9, 4.5, 7.1, 0.0},
    		                 	{5.9, 6.7, 8.1, 8.6, 7.6, 0.0},
    		                       	{6.7, 5.4, 7.8, 6.4, 2.4, 4.8, 0.0},
    		                       	{7.1, 2.6, 1.6, 2.1, 3.6, 6.3, 7.1, 0.0},
    		                       	{8.4, 7.1, 3.8, 7.6, 1.2, 7.2, 5.5, 2.6, 0.0},
    		                     	{9.8, 8.6, 1.0, 2.6, 4.5, 1.8, 4.6, 7.5, 9.9, 0.0},
            				};
    
      		return new Test3(legends, distance);
    	}
    
    //------------------------------------------------------------------------------------------
    public static void main(String[] args){
    	String[] list={"B","C"};
    	String[][] path=new String[2][3];
    
    	Test3 dt = Test3.getDefault();
    	System.out.println("City A is set as starting point.");
    	path[0][0] = "A";
    	path[1][0] = "A";
    //---------------------------------------------------------------------------------------
    	String[] mark={"B","C"};
    	String[] mark2=new String[2];
    	
    	int pathIndex1=0;
    	for(int x=0;x<2;x++){
    		int pathIndex2=1;
    		System.arraycopy(mark,0,mark2,0,mark.length);
    		path[pathIndex1][pathIndex2]=mark2[x];
    		mark2[x]=null;
    
    		for(int y=0;y<2;y++){
    			if(mark2[y]==null)
    				continue;
    			else{
    				System.out.println(y+ "---");
    				pathIndex2++;
    				path[pathIndex1][pathIndex2]=mark2[y];
    				pathIndex1++;
    			}			
    		}
    	}
    
    
    	for(int x=0;x<2;x++){
    		for(int y=0;y<3;y++)
    			System.out.println("[" +x+ "," +y+ "] : " +path[x][y]);
    	}
    
    //----------------------------------------------------------------------------------------
      }
    }

  11. #11
    Join Date
    May 2005
    Posts
    115
    customwoodtek, i have some problems understanding the pseudocode. If its not 2 much trouble, can you briefly explain it to me? I'm trying2 implement it using ArrayList..

    Code:
    1 bfs(adj, start){
    2   n = adj.last
    3    for i = 1 to n
    4      visit[i] = false
    5   visit[start] = true
    6    q.enqueue(start) //same thing as adding, just a fancy word
    7    while(!q.empty()){
    8       current = q.front()
    9       q.dequeue() //same thing as removing
    10       trav = adj[current]
    11      while(trav != null){
    12          v = trav.ver
    13          if(!visit[v]){
    14             visit[v] = true
    15             q.enqueue(v)
    16          }
    17          trav = trav.next
    18       }
    19    }
    20 }

  12. #12
    Join Date
    Aug 2003
    Posts
    313
    I might be jumping into the middle of this, but I'll give a quick explaination maybe it will help.

    For the BFS you get a work queue of things that you are processing for simplicity my example will using strings of letters, i.e. the path A-B-C will be represented by the string "ABC". You start by adding your initial path to the queue in this case it will be "A". Then you perform a loop which continues until the queue is not empty. In the loop you remove the first element, and, if the path is complete, i.e. all the cities have been visited, then you compute the distance, compare it to your shortest and update the shortest if necessary. Otherwise you loop over the cities which have not been visited and append each to the end of the string and put it on the queue. Pseudo code might look like this.
    Code:
    add "A" to queue
    while queue is not empty {
      let current = first element of queue (this should also remove that element)
      if the length of current is the total length then {
        compute the distance to travel the path
        if the distance is smaller than the current shortest path then
          set this path to the current shortest path
      }
      else {
        for each city (all of them) { 
           if the city has not been visited in the string then 
             append city to path and add it to the queue
        }
      }
    }
    when you are done, shortest will be your shortest path.
    Hope this helps.
    ~evlich

  13. #13
    Join Date
    Jan 2005
    Location
    Reisterstowwn, MD
    Posts
    72
    Magma, i need more detail to understand what your asking. What are you trying to implement with an ArrayList??
    Java has 99 problems but a pointer ain't one

  14. #14
    Join Date
    Aug 2003
    Posts
    313
    BFS's are implemented using Queues. ArrayLists can be used as queues. But actually on second inspection, LinkedLists are probably better.
    Code:
    LinkedList queue = new LinkedList(); // make an empty queue
    queue.addFirst("A"); // enqueue "A"
    String cur = queue.removeFirst(); // dequeue
    queue.isEmpty(); // determine if the queue is empty
    Hope this helps.
    ~evlich

  15. #15
    Join Date
    May 2005
    Posts
    115
    I'm a little bit confused...
    You start by adding your initial path to the queue in this case it will be "A".
    r u saying that in the beginning the queue will only contain 1 element, the starting node "A"? if so, where r all rest of of the nodes?

    Then you perform a loop which continues until the queue is not empty.
    Since the line 'add "A" to queue' is outside the while loop, wont the queue b never empty?

    Code:
      else {
        for each city (all of them) { 
           if the city has not been visited in the string then 
             append city to path and add it to the queue
        }
      }
    }
    If lets say the sample contains A-B-C-D. A is my starting node, with BCD unvisited. If i code it like above, i will get the path ABCD right? but how about other paths like ACDB etc? because, after ABCD, C would already b labeled as visited, so how would it detect paths like ACDB?

    I'm very confused right now

Similar Threads

  1. Java vs. .Net. A questionnaire
    By Basil in forum .NET
    Replies: 1
    Last Post: 05-13-2005, 06:46 AM
  2. java search
    By wakum in forum Java
    Replies: 2
    Last Post: 04-18-2005, 03:03 PM
  3. Replies: 0
    Last Post: 06-17-2001, 09:22 AM
  4. Replies: 0
    Last Post: 06-17-2001, 09:17 AM
  5. Replies: 0
    Last Post: 06-17-2001, 09:07 AM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  
HTML5 Development Center
 
 
FAQ
Latest Articles
Java
.NET
XML
Database
Enterprise
Questions? Contact us.
C++
Web Development
Wireless
Latest Tips
Open Source


   Development Centers

   -- Android Development Center
   -- Cloud Development Project Center
   -- HTML5 Development Center
   -- Windows Mobile Development Center