Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 2 of 2

Thread: Graph Search Theory with extend of BFS, UFS and A* Search in grid

  1. #1
    Junior Member
    Join Date
    Feb 2012
    Posts
    8
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Default Graph Search Theory with extend of BFS, UFS and A* Search in grid

    Dear All,

    I am currently working on my school assignment and have some confusing with the theory.

    The description of the assignment is

    Lets say we have a 5 x 5 grid as below:

    1 1 1 5 8
    1 2 3 x 5
    1 2 3 x 6
    1 1 1 x 1
    x 1 1 1 1

    x = obstacle that should avoid
    number = higher number mean we need to climb up, same number mean same level
    Must expand in the following order up, down, left and right.
    Start (1,1) Goal (5,5)

    The mission is to use BFS, UFS and A* heuristic search to find the shortest path.

    The output for BFS should be something like this:-

    * 1 1 5 8
    * 2 3 x 5
    * 2 3 x 6
    * * 1 x 1
    x * * * *

    The question that in my mind is:-
    1. Is the Graph Search algorithm need to convert the above grid into a adjcency matrix? that keep record on which node is connect to which.
    2. I not sure on how the data structure will be for this. Suppose we need to create a node object with 4 value which is label, visited flag, x-coordinate and y-coordinate.

    I am totally lost and have no idea on how can i start this. Anyone can please enlighten me on this? Thank you for your help.


  2. #2
    Administrator copeg's Avatar
    Join Date
    Oct 2009
    Location
    US
    Posts
    5,320
    Thanks
    181
    Thanked 833 Times in 772 Posts
    Blog Entries
    5

    Default Re: Graph Search Theory with extend of BFS, UFS and A* Search in grid

    Have you ever created a Graph before? Create a Node and Edge class - write out the connectivity and then translate to code. Google 'java graph node tutorial', or something along those lines and you will see how to accomplish this. Traversal requires iterating through the nodes and edges, both of which have references to other nodes/edges, and allow you to traverse through the graph.

Similar Threads

  1. Java search - help
    By cnilsson in forum What's Wrong With My Code?
    Replies: 1
    Last Post: August 25th, 2011, 02:26 AM
  2. java job search
    By medasi in forum Java Theory & Questions
    Replies: 0
    Last Post: January 18th, 2011, 03:09 AM
  3. search file by id
    By d..:) in forum File I/O & Other I/O Streams
    Replies: 1
    Last Post: January 13th, 2011, 09:34 AM
  4. search problem
    By farvi_buet in forum What's Wrong With My Code?
    Replies: 0
    Last Post: May 8th, 2010, 01:26 PM
  5. google search
    By nasi in forum Java Theory & Questions
    Replies: 7
    Last Post: April 2nd, 2010, 03:13 AM