Проблема

Учитывая ориентированный граф, разработайте алгоритм, чтобы узнать, существует ли маршрут между двумя узлами.

Решение

Эта проблема может быть решена простым обходом графа, таким как поиск в глубину или поиск в ширину. Мы начинаем с одного из двух узлов и во время обхода проверяем, найден ли другой узел. Мы должны пометить любой узел, обнаруженный в ходе алгоритма, как «уже посещенный», чтобы избежать циклов и повторения узлов.

public enum State {
   Unvisited, Visited, Visiting;
}
public static boolean search(Graph g, Node start, Node end) {
   // operates as Queue
   LinkedList<Node> q = new LinkedList<Node>();
   for (Node u : g.getNodes()) {
      u.state = State.Unvisited;
   }
   start.state = State.Visiting;
   q.add(start);
   Node u;
   while (!q.isEmpty()) {
       u = q.removeFlrst(); // i.e., dequeue)()
       if (u != null) {
           for (Node v : u.getAdjacent()) {
              if (v.state == State.Unvisited) {
                 if (v == end) {
                    return true;
                 } else {
                    v.state = State.Visiting;
                    q.add(v);
                 }
              }
           }
           u.state = State.Visited;
        }
   }
   return false;
}