Data structure 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

 

[Patricia Shanahan]

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.

....

java.util.HashSet

Patricia

 

[Remon van Vliet]

...

java.util.HashSet

Patricia

Well, at the risk of pointing out the obvious, why not ue a 'visited' flag
in the actual nodes and check for these during traversal.

Remon

 

[Thomas Weidenfeller]

Well, at the risk of pointing out the obvious, why not ue a 'visited' flag
in the actual nodes and check for these during traversal.

It only works in limited circumstances. E.g. it doesn't work in any
setup where you have concurrent (overlapping ) traversals of the graph
going on.

It also requires an extra step to clear all flags prior to traversal if
you do more than one traversal. Which means you better have all your
nodes arranged in some other data structure, like a list, too. Otherwise
you end up in the situation where you would have to do a traversal to
clear the flags to prepare for a traversal. However, the
preparation-traversal can't work if you need the flags for loop
detection during traversal.

/Thomas