I am implementing Depth-first search in java using \"RECURSION\" the problem is,

Question

I am implementing Depth-first search in java using "RECURSION"

the problem is, the recursiveDFS method is "void" so it does not return anything

but the driver is supposed to return a "list." How can I return a list by using void recursive method?

Is the implementation correct?

/**
   * Depth-first search driver method.
   * Performs a depth-first search of a graph to determine a path from a starting vertex to an ending vertex.
   *
   * @param graph - graph object reference to be used for searching
   * @param startName - Name of the starting vertex in the path
   * @param goalName - Name of the ending vertex in the path
   * @throws UnsupportedOperationException - if the start vertex does not exist in the graph
   * @throws UnsupportedOperationException - if the goal vertex does not exist in the graph
   * @return a list of the vertices that make up a path from the starting the ending vertices (inclusive)
   */
   public static List depthFirstSearch(GraphStructure graph, String startName, String goalName)
   {
       // TODO

       if(!graph.getVertices().containsKey(startName) || !graph.getVertices().containsKey(goalName))
       {
           throw new UnsupportedOperationException();
       }
      
       List list = new LinkedList();

       GraphVertex start = graph.getVertices().get(startName);
       GraphVertex goal = graph.getVertices().get(goalName);
      
      
       depthFirstSearchRecursive(graph, start, goal);
      
      
       return list;

      
   }

   /**
   * Depth-first search recursive method
   *
   * @param graph - graph object reference to be used for searching
   * @param start -- Name of the starting vertex in the path
   * @param goal -- Name of the ending vertex in the path
   */

   private static void depthFirstSearchRecursive(GraphStructure graph, GraphVertex start, GraphVertex goal)
   {
       // TODO   

       //created empty list
       LinkedList list = new LinkedList();

       //set start's "visited" flag and add it to the queue
       start.setVisited(true);
      
       //if the start is the goal, return - base case
       if(start.equals(goal))
       {
           return;
       }
      
       if(start.equals(goal)) //if the path was found
       {
           while(!start.equals(start))
           {
               list.addFirst(start.getName());
               start = start.getCameFrom();      
           }
       }
      
       LinkedList edges = start.getEdges();
       for(GraphEdge edge : edges)
       {
           if(edge.getOtherVertex().getVisited() == false)
           {
               edge.getOtherVertex().setVisited(true);
               edge.getOtherVertex().setCameFrom(start);
               depthFirstSearchRecursive(graph, start, goal);
           }
       }
      

   }

Explanation / Answer

public static LinkedList<String> depthFirstSearch(GraphStructure graph, String startName, String goalName)
{
   GraphVertex start = new GraphVertex(startName);
   GraphVertex goal = new GraphVertex(goalName);
   LinkedList<String> list = new LinkedList<String>();
  
   if(!graph.getVertices().containsKey(startName) || !graph.getVertices().containsKey(goalName))
   {
       throw new UnsupportedOperationException();
   }
  
   if(startName.equals(goalName))
    {
       list.add(startName);
        return list;
    }
  
   return depthFirstSearchRecursive(start, goal);
}

private static LinkedList<String> depthFirstSearchRecursive(GraphVertex start, GraphVertex goal)
{
   LinkedList<String> list = new LinkedList<String>();
  
   if(!start.getName().equals(start.getName()))
       start.setVisited(true);
  
   LinkedList<GraphEdge> edges = start.getEdges();
  
   for(GraphEdge edge : edges)
   {
       if(edge.getOtherVertex().getVisited() == false)
       {
           edge.getOtherVertex().setCameFrom(start);
          
           list.addAll((Collection<? extends String>) start.getCameFrom());
          
          
           return depthFirstSearchRecursive(edge.getOtherVertex(), goal);
       }
   }
  
   return list;
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.