How can I traverse a linked list that can not only include loops, but also multiple links from a single node? (VB6)

I've got a linked list made out of NODE_'s. These nodes do not actually point to other nodes, but rather to a linked list of NODELINK_'s, which store connected nodes.

This allows for the formation of irregular graphs, such as:

N------N---------N-------N
      / \        |        \
     /   \       N---N-----N
    /     \      |    \    |  
   N-------N-----N     N---N

You get the idea. Very dynamic data. A typical node may look like so:

NOODE_1 -> NODELINK_1 -> NODELINK_2 -> NODELINK_3 -> NULL
               |             |             |
               V             V             V
             NODE2_        NODE3_        NODE4_

A problem arises when it comes to traversing such a graph. Making my way around the graph is easy enough, but how can I make sure I don't find myself stuck traversing a loop within the graph (NOTE: It is unsafe to assume that the head will be a part of this loop, so your typical "circular linked list traversal" algorithm won't cut it here), and how can I make sure to know when a node has been processed before?

The only thing I can come up with is setting a flag within each node, indicating that it has already been processed. This seems sort of like a hackjob, but I can't think of any other way to do this that I would consider reasonable. Am I wrong? Is there a better way?

Solution

You're doing a Graph traversal. Setting a visited flag with each node is definitely a common approach e.g. both the Breadth-first search and Depth-first search algorithms at Wikipedia mark the visited nodes.