title: How to trace path during algorithm BFS
body: <p>I'm looking for a way to trace a path for my bfs-algorithm, but I don't know how. Maybe I'm wrong, but I think I do need a duble ArrayList, to save every possible way. That means in the following example:</p>
  
  <p><a href="https://i.stack.imgur.com/7wsPU.gif" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/7wsPU.gif" alt="enter image description here"></a></p>
  
  <ol>
  <li>arraylist: 6-3-1</li>
  <li>arraylist: 6-3-5</li>
  <li>arraylist: 5-9-7</li>
  <li>arraylist: 6-9-10</li>
  </ol>
  
  <p>And this would even look worse, if there would be a connection from 3 to 9.</p>
  
  <pre><code>    public List&lt;E&gt; BFS(N source, N target)
      {
          ArrayList&lt;ArrayList&lt;N&gt;&gt; nodes_paths = new ArrayList&lt;ArrayList&lt;N&gt;&gt;();
          ArrayList&lt;N&gt; nodes_list = new ArrayList&lt;N&gt;(graph.getNodes());
          N current_node;
  
          Queue &lt;N&gt; list = new LinkedList&lt;N&gt;();
          HashMap&lt;N, Boolean&gt; already_visited = new HashMap&lt;N, Boolean&gt;();
  //      mark all nodes in HashMap as not visited
          for(int i=0; i&lt;nodes_list.size(); i++)
          {
              already_visited.put(nodes_list.get(i), false);
          }
  
          ArrayList&lt;N&gt; successors = new ArrayList&lt;N&gt;();
          list.add(source);
  
          while(!list.isEmpty())
          {
              current_node = list.poll();
              already_visited.put(current_node, true);
            //need to add the node to any path, but don't know to which?
              if(current_node.equals(target))
              {
  
              }
              else
              {
                  successors = new ArrayList&lt;N&gt;(graph.getSuccessors(current_node));
                  for(int j=0; j&lt;successors.size(); j++)
                  {
                      if(!already_visited.get(successors.get(j)))
                      {
                          already_visited.put(successors.get(j), true);
                          list.add(successors.get(j));
                      }
                  }
              }
          }
  
  
  //      need the path array here!
          ArrayList&lt;E&gt; edges_list = new ArrayList&lt;E&gt;(graph.getEdges());
          ArrayList&lt;E&gt; path_edges = new ArrayList&lt;E&gt;();
          for(int k=0; k&lt;path.size()-1; k++)  //If there are path.size nodes, so therer are only path.size-1 edges
          {
              for(int l=0; l&lt;edges_list.size(); l++)
              {
                  if(path.get(k).equals(edges_list.get(l).getSource()) &amp;&amp; path.get(k+1).equals(edges_list.get(l).getTarget()))
                  {
                      path_edges.add(edges_list.get(l));
                  }
              }
          }
  
          return path_edges;
  
  
      }
  </code></pre>