Recursion, possible search tree

[aerowenn]

I have a program assignment, just needing a little help in the right direction implementing part of it. I'll give a general brief description of what it does. It reads in from a text file, these objects called sectors (different areas), they may be in 3x3 fashion or any size 4x7, 5x2 and etc. Dimensions of the sector grid isn't important really. Here is how they are formatted:

name 4 34 name 2 1
name 6 23 name 3 9

The name being the name of that sector of course, second digit being a binary direction value 1 North, 2 East, 4 South, 8 West. So for instance, if we read in a C (binary 12) for directions, we have an open path West and South. Here is where I need help. We link these sectors to each other via pointers, if a sector is open to the South, it will only be open if there is another sector there, then it's South pointer holds the address of the Sector to the South. I know this is a little confusing and I'm sorry if I'm rushing it. Like this:

brown 4 45
red 5 92

Since brown has a direction value of 4 for brown, it's SOUTH pointer, points to red's address. Linking them dynamically so to speak. The third value, another integer, is that sectors SIZE.

What we are supposed to do is start at a sector of size 0, and go until we reach a sector of size 100, there is no particular order, but there could be multiple paths to the right sector, for instance one sector may be open to the north and south, you can go either direction and get there, but one may be longer. I need to know how to implement this. How do I start at sector size 0 and go to sector size 100, show each sector we visited to get there and etc. I would really appreciate a push in the right direction! Thanks!

[KrishnaV]

First you need to create the graph (with nodes linked to other nodes).
Each node in the graph represents sector.
Once you do that, starting from the node with size 0, you can do a depth first or a breadth first search. Any algorithm book that deals with graphs should have these basic searches described.

DFS will give you the first path it finds that reaches 100 and BFS will give you the shortest path.


EDIT: actually may be you can improvise by keeping track of the path when creating the graph itself.

[aerowenn]

Yes actually another part is to keep track of the path taken, and give a "value" of the path, or distance, either way it's totals the sizes. That is actually more of an extra credit type. QUESTION: On your description of a graph, you're talking about like a dynamically allocated array or just a vector of vectors? My question here is that some Sectors aren't linked to ones near them, some may not be linked at all in any particular path, but each Sector has a maximum link to only 4 possible other Sectors, and they don't change. So this method will still work assuming we cannot take any path we choose?

[KrishnaV]

Dynamically allocated nodes..linked together...its like a linked list but each node in the list can point to upto 4 possible other nodes...unlike in a regular linked list each points to only one other node.