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

$\endgroup$
  • $\begingroup$ How are your graphs represented? Adjacency lists? Adjacency matrices? Edge lists? $\endgroup$ – dkaeae Jan 1 at 21:43
  • $\begingroup$ Have you looked at graph traversal algorithms? $\endgroup$ – Apass.Jack Jan 1 at 22:00
  • $\begingroup$ You can simply use a Set to avoid duplicates $\endgroup$ – Navjot Waraich Jan 2 at 1:14
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.

$\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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.