Ответы пользователя по тегу Алгоритмы
  • Как найти путь в ориентированном графе?

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

    @TwoBlueCats
    При вычислении минимума вы рассматриваете только один из двух стеков, а минимум может быть в любом из двух. Рассмотрим такой тест c 7 запросами:
    7
    5
    6
    7
    0
    1
    2
    0

    После первой операции запроса минимума у вас в s2 будет лежать два элемента. Потом вы добавляете 2 меньших по значению элемента в s1. Во время второго запроса минимума не будет выполняться перенос элементов из s1 в s2 и вернется минимум только среди элементов s2.
    Ответ написан
    Комментировать