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

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

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