0
$\begingroup$

I need an algorithm to explore every node in a graph (starting at any given node). Each node can have multiple parent nodes and multiple child nodes.

The following algorithm (in psuedocode) appears to gather every node but results in duplicate nodes (I think because the recursive 'paths' crossover at some points):

rFindAll(Node ID, Array currentpath) //current path passed by value
{
  Array connectedNodes = getConnectedNodes(ID);

  for_each_node (Node n : connectedNodes)
  {
     if(find(currentpath, n) == NOT_FOUND) // check to ensure id not in current recursive path
     {
        // every n is a node which is within the same graph as the original node
        currentpath.add(n); 
        rFindAll(n, currentpath);
     }
  }

}

I was just wondering whether anyone has a better suggestion to do this. I've looked on google/wikipedia and there was nothing which would obviously help.

Thanks

Improve this question
$\endgroup$
3
  • $\begingroup$ How are your graphs represented? Adjacency lists? Adjacency matrices? Edge lists? $\endgroup$ Commented Jan 1, 2019 at 21:43
  • $\begingroup$ Have you looked at graph traversal algorithms? $\endgroup$ Commented Jan 1, 2019 at 22:00
  • $\begingroup$ You can simply use a Set to avoid duplicates $\endgroup$ Commented Jan 2, 2019 at 1:14

2 Answers 2

Reset to default
2
$\begingroup$

The standard way to solve this is called whatever-first search. (Because depth-first and breadth-first and best-first and others are all special cases of it.)

The algorithm goes like this:

Pick a starting node
Add the starting node to a "bag" (arbitrary data structure)
While the bag isn't empty:
    Take a node out of the bag
    Mark this node as "explored"
    [Do whatever you like with this node]
    Add all this node's unexplored neighbors to the bag

The choice of "bag" is up to you. A stack makes depth-first search, a queue makes breadth-first search, a priqueue makes best-first search, and so on, but you can use anything you like, as long as you can put things into it and take things out of it.

Improve this answer
$\endgroup$
-1
$\begingroup$

Not sure whether "rFindAll" is first called in your program. If you just pass the initial node with empty "currentpath", obviously, the initial node is not added into the path and will be visited again and introduce duplication. You can update your function by moving the line currentpath.add(n); to the first position of the function: rFindAll(...) { currentpath.add(n); ... }

Another potential issue might be related to your programming language. If you are using c/c++, your code does have problem on function argument: rFindAll(Node ID, Array currentpath) Here "Array currentpath" is defined by val, so the update on this variable will not be propagated to the upper level. This may also lead to duplication.

In addition, please you'd set to store visited node instead of array, for better performance.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.