[4.2] Find route(Path) between two nodes

1. Example

Depth First Search


2. Implementation

LinkedList stack = new LinkedList();

for (Node u: g.getNodes())

    u.state = State.Unvisited;

start.state = State.Visiting;
stack.add(start); 

while (  !stack.isEmpty()  ) {
      Node curr = stack.removeFirst();// pop()

     if ( curr!= null ) { 

              for ( Node v: curr.getAdjacent() ) {
                               if (v.state == State.Unvisited) { 

                                      // NOTE :find sth 

                                      if ( v == end) 

                                             return true; 

                                     else { 

                                             v.state = State.Visiting; 

                                             stack.add(v); 

                                    }

                              }

            }

            curr.state = State.Visited;
     }

}

return false;

public enum State{
    Unvisited, Visited, Visiting;
}


public static boolean FindRoute(Graph g, Node start, Node end)
{



    // Validate the input
    if ( g == null || start == null || end == null )
         return false;



    LinkedList stack = new LinkedList();
    for (Node u: g.getNodes())
        u.state = State.Unvisited;




    start.state = Visting;
    stack.add(start);
    while ( !stack.isEmpty() )
    {




         Node curr = stack.removeFirst();// pop()
         if ( curr!= null )
         {
 




              for ( Node v: curr.getAdjacent() )
              {
                   if (v.state == State.Unvisited)
                   {
                         // NOTE :find sth
                         if ( v == end)
                                return true;
                         else
                         {
                                v.state = State.Visiting;
                                stack.add(v);
                         }
                        
                   }
              }





              curr.state = State.Visited;
         }
    }



    return false;



}

3. Similar One