0

I am trying to find all the possible paths from one node in my graph that will visit all other nodes in the graph. I want the function to produce all possibilities of paths in my n*m graph. Each node in my graph has a vector of all neighbors nodes and a Boolean that check if the node is visited or not.

example:

a  b

c  d

will produce:

abcd
abdc
acbd
...

I tried the solution in this answer, but only return one path. How can I produce all possible paths?

Community
  • 1
  • 1
Max Pain
  • 1,217
  • 7
  • 19
  • 33
  • You can use depth-first search (DFS). Pseudocode can be found here: https://en.wikipedia.org/wiki/Depth-first_search#Pseudocode – Special Sauce Nov 27 '15 at 02:03

1 Answers1

0

It seems like in some situations by your description you could have infinite paths and a path of infinite length because you didn't specify that nodes couldn't be revisited.

You should implement depth first search and pass a reference to an array of marked (visited) nodes in your recursive DFS method assuming that you have a count of the number of nodes in your graph. After you visit each node, before you leave that node make sure you set it to false again so that it can be reaccessed via another node.

The implementation of this algorithm is really going to depend on how you implemented your graph structure and without the details all I can do is speculate that you have a linked structure with an adjacency list representing the different nodes. I also have no idea how the different nodes map to characters so that is another detail I have to speculate, but say that the nodes are represented by integers.

You need to pass into a DFS method the following: array of marked nodes, a linked list which contains the path information, starting node, (i.e, current node) and final node 

 void printAllPaths(LinkedList<Integer> currentPath, boolean[] marked, int current, int last){ 

    for( all nodes adjacent to current, node ){
      if(node == last){ 
         currentPath.addLast(last); 
         System.out.println(currentPath);
         currentPath.removeLast();
      }else if(!marked[node]){
         currentPath.addLast(node);
         marked[node] = true;
         printAllPaths(currentPath, marked, node, final);
         marked[node] = false;
         currentPath.removeLast();
      }
    }
 }

This will be the basic idea of the code. I apologize if it doesn't compile in advance, but this should print out all of the paths.

libby
  • 585
  • 4
  • 15