Пользователь пока ничего не рассказал о себе

Наибольший вклад в теги

Все теги (4)

Лучшие ответы пользователя

Все ответы (3)
  • Как найти путь в ориентированном графе?

    @TwoBlueCats
    0) у вас в коде есть цикл, который ничего не делает, его можно удалить.
    1) в строчке, где получается список соседей используется неправильная переменная. Текущая вершина хранится в nodeIndex.
    2) запоминать можно. Для этого либо используют дополнительный массив, в который запоминают "предка" вершины v, то есть такую вершину u, после рассмотрения которой, добавили в стек v. В результате для получения пути надо будет размотать цепочку предков от финальной вершины до стартовой
    2.5) если требуется кратчайший путь в невзвешенном графе (все ребра одинаковые), то стоит использовать алгоритм BFS (использовать очередь вместо стека). Если граф взвешенный, то использоваться алгоритм Дейсктры
    Ответ написан