Проблема
Учитывая ориентированный граф, разработайте алгоритм, чтобы узнать, существует ли маршрут между двумя узлами.
Решение
Эта проблема может быть решена простым обходом графа, таким как поиск в глубину или поиск в ширину. Мы начинаем с одного из двух узлов и во время обхода проверяем, найден ли другой узел. Мы должны пометить любой узел, обнаруженный в ходе алгоритма, как «уже посещенный», чтобы избежать циклов и повторения узлов.
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; }