What datastructure to use to store nodes/locations I've visited

[6tc1]

Hi all, I'm doing something similar to a graph traversal. And in this
instance this graph type structure could have cycles. I want to ensure
I don't revisit old nodes and was wondering if anyone could think of an
efficient way to store nodes/locations/names that have already been
visited.

I was thinking about using a Vector - but that would be very
inefficient as the number of nodes/locations/names got to the
thousands.

Should I just use a Hashtable and then use an empty string or something
for the value. In other words - if the following were the list of
locations/nodes I've visited:
"a"
"b"
"cd"
"dg"
"de"
"d"

then would it make sense to do the following:
Hashtable hashtable = new Hashtable();
hashtable.put("a", "");
hashtable.put("b", "");

and so on?

Then when I want to determine whether I've already visited the node
named "b", I would just say:
if (hashtable.get("b") != null){
}

Thanks,
Novice

 

[Jon Harrop]

Hi all, I'm doing something similar to a graph traversal. And in this
instance this graph type structure could have cycles. I want to ensure
I don't revisit old nodes and was wondering if anyone could think of an
efficient way to store nodes/locations/names that have already been
visited.

I was thinking about using a Vector - but that would be very
inefficient as the number of nodes/locations/names got to the
thousands.

If you can label every node with a unique integer 1..N then you can just use
an bool array where "visited" tells you if node "i" has been visited
already.

I used the slower approach of a balanced binary tree in my maze generating
program because I was asked to use a purely functional style:

http://www.ffconsultancy.com/free/maze/

If you can only give "names" to each node then a hash table would be a good
bet.

 

[Eric Sosman]

Hi all, I'm doing something similar to a graph traversal. And in this
instance this graph type structure could have cycles. I want to ensure
I don't revisit old nodes and was wondering if anyone could think of an
efficient way to store nodes/locations/names that have already been
visited.

Can you put "been here already" markers on the nodes
themselves?

 

[shakah]

Hi all, I'm doing something similar to a graph traversal. And in this
instance this graph type structure could have cycles. I want to ensure
I don't revisit old nodes and was wondering if anyone could think of an
efficient way to store nodes/locations/names that have already been
visited.

I was thinking about using a Vector - but that would be very
inefficient as the number of nodes/locations/names got to the
thousands.

Should I just use a Hashtable and then use an empty string or something
for the value. In other words - if the following were the list of
locations/nodes I've visited:
"a"
"b"
"cd"
"dg"
"de"
"d"

then would it make sense to do the following:
Hashtable hashtable = new Hashtable();
hashtable.put("a", "");
hashtable.put("b", "");

and so on?

Then when I want to determine whether I've already visited the node
named "b", I would just say:
if (hashtable.get("b") != null){
}

Thanks,
Novice

You could use a HashSet instead of a Hashtable (or HashMap), gets rid
of the nonsensical value. Regardless, your test could use contains()
instead of get(), e.g.:

if(hashtable.contains("b")) {
}