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

• February 7th, 2012, 12:14 AM
keat84
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.
• February 7th, 2012, 08:46 AM
copeg
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.