Clever Geek Handbook

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

I have a linked list of NODE_

. These nodes do not actually point to other nodes, but rather to a linked list NODELINK_

that stores related nodes.

This allows you to generate irregular schedules such as:

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

You get the idea. Very dynamic data. A typical node might look like this:

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

A problem arises when it comes to going through such a schedule. Getting my way around the graph is easy enough, but how can I make sure I'm not stuck looping inside the graph (NOTE: It's not safe to assume the head will be part of this loop, so your typical "round robin" algorithm won't be shortened here ), and how can I make sure that before node processing?

The only thing I can think of is setting a flag inside each node, indicating that it has already been processed. It looks like a hark, but I can't think of any other way to do this, which I think is reasonable. Am I wrong? Is there a better way?

+3


source to share


2 answers


You are traversing the schedule . Setting a flag visited

with each node is definitely a common approach, eg. like breadth -first search and depth-first search algorithm> on Wikipedia mark

visited nodes.



+3


source


The only way I can do this is to store a data structure such as Dictionary

to list the nodes you have already visited and check the membership before visiting the node you have already visited. This will avoid the need to create additional fields in your nodes.



+3


source






More articles:


All Articles