CODEWITHSUNDEEP
graphtreegraph-algorithmtree-traversal
user32262
user32262

Reputation: 8850

Graph traversal for node search

In the given below graph, the child parts are traversed recursively. Each child must report its immediate parent. The problem is child[3] must report both of its immediate parent (i.e. child[2] and child[4]) at the same time in the same row.

traverse(Node node)
{
    if(node == null)
        return;

    for(Node child : node.getChilds()) {
        traverse(child);
    }
}

Parent 
|---child[1]
|       child[2]
|           child[3]
|---child[4]
        child[3]

Right now I am traversing the graph one node at a time and the output produced is -

Node      Immediate Parent
--------------------------
child[2]  child[1]
child[3]  child[2]
child[3]  child[4]

The expected output is -

Node      Immediate Parent
--------------------------
child[2]  child[1]
child[3]  child[2], child[4]

What would be the best way to search the nodes and produce the expected output for the graph? Any help would be appreciated.

Upvotes: 3

Views: 488

Answers (1)

Attila
Attila

Reputation: 28762

If you have (or can add) a link back to the parents, you can list all the parents the first time you encounter a node, then skip it on recurring visits. You have multiple options to keep track of whether a node has been visited:

  1. maintain a set of visited nodes and check if the current one is in the set. If not, process it and add it to the set; otherwise skip.

    Advantage: general approach

    Disadvantage: might take a significant amount of memory to maintain the set if the graph is large

  2. add an isVisited member value to the node (set to false by default) and check it when encountering a node: if the value is false, process the node and set isVisited to true; otherwise skip.

    Advantage: less additional memory

    Disadvantage: intrusive, task-specific, the extra variable is there even when not needed, does not scale well for tasks that require multiple such "has-it-been-processed-yet" decisions simultaneously

If the parent-link option is not available, you can maintain the child-to-parent relationship in an extra map: you map from the child to the set of parents as you process the nodes. Once done with the initial processing (of building the map), you iterate the map and list each node and its parents.

The advantage over the direct parent links is that there is no extra maintenance when building/modifying the graph (unless you want to keep the mapping up-to-date as well)

The disadvantage is that you will have to re-build the map every time you want to process the graph after a series of modifications to the structure of the graph (unless -- see the note for adventage)

Note: traversing a general graph by traversing all the children can lead to infinite loops if there is a directed (parent-to-child) circle in the graph. I imagine this is not the case for your problem, but just to cover all bases: you can maintain a set of "visited" nodes as you process the graph. The discussion of the available options is identical to the one in the first ("link back to the parents") part

Upvotes: 8

Related Questions