Давайте попробуем существенно ускорить стандартный алгоритм Дейкстры, используя для выбора вершины с минимальным весом из не рассмотренных двоичную кучу.
Ну а напоследок, мы с вами поговорим еще про одну структуру, которая представляет из себя не очень сложно реализуемое дерево, которое используется для сортировки и быстрого извлечения элементов с максимальным приоритетом.
В программировании используют достаточно много видов деревьев:
Давайте рассмотрим еще одну структуру данных - дерево.
Давайте рассмотрим несколько задач, которые можно решить, изменяя рассмотренные нами поиск в ширину или глубину на графах.
Сегодня мы продолжим разбирать алгоритмы на графах. Еще один очень распространенный алгоритм – поиск в глубину (DFS). Если объяснять просто, то в поиске в ширину, если помните, у нас из каждой вершины как бы выбегала толпа народа, которая потом снова делилась на большие толпы, а в поиске в глубину бегает только один неутомимый товарищ, который должен успеть оббежать все вершины в поисках нужной и очень быстро.
Сегодня мы продолжим решать задачу из предыдущего занятия. Поиск в ширину отлично работает, но его можно оптимизировать. Вспомните, мы пытались двигаться из всех вершин в очереди по всем направлениям, улучшая минимальные пути и записывая одни и те же вершины в очередь по несколько раз. Алгоритм Дейкстры позволяет упростить поиск в ширину, выбирая из всех возможных направлений самое подходящее. Для алгоритма Дейкстры есть одно ограничение: вес ребер не должен быть отрицательным.
Сегодня все занятие мы посвятим решению одной задачи. Точнее, мы решим вроде бы только одну задачу, а потом поймем, что это же решение можно применить (практически без изменений) для решения сотен и даже тысяч очень актуальных и важных алгоритмических задач из реальной жизни.
Сегодня мы начинаем говорить о теории графов. Это не структура данных и не метод решения задача. Графы – это способ представления и обработки данных в виде не просто множества объектов заданного класса, но и с учетом связей между ними.
Продолжаем говорить о структурах данных.