Рубрики
Структура Данных "Коллекция"

Структура Данных «Стек»

ВАЖНО

  • элементы всегда добавляются в конец структуры
  • элементы всегда извлекаются из конца структуры

ПРИМЕР

стопка бумаги

  • добавляем сверху
  • забираем сверху
Рубрики
Алгоритмы Графы "поиск el"

Графы Алгоритм «поиск в ширину»

не важно

длительный этот путь или нет, а самое

главное

количество пройденных участков или существует ли путь

ЗАДАЧА

Найти путь из точки A в точку B за минимальное количество шагов

Процесс решения

задаём для каждой вершины название
создаём объект, который содержит вершины (содержит путь к точке B)

используется Cтруктура Данных «очередь»

  • состоит из каких то элементов
  • элементы всегда добавляются в конец структуры, а извлекаются из её начала
  • тот кто пришел на кассу первым — уходит первым
  • тот кто пришел на кассу последним — уходит последним
  • FIFO FIRST IN FIRST OUT
Рубрики
Алгоритмы Графы "поиск el"

Графы Алгоритм «Дейгстры»

алгоритм поиска кратчайшего пути в графе

Важно

учитывается длинна пройденного ребра — вес

Задача

стартовая точка A
конечная точка G

A—B—F—G
|       / |
|      /  |
|     /   |
|    D  |
|   /     |
|  /      |
|/        |
C——E

составляется таблица, на котором на первом этапе записываются значения тех вершин, в которые мы можем попасть из стартовой точки. Все остальные вершины являются не достижимыми и мы их помечаем знаком бесконечности.

На втором этапе мы помечаем эти (B и C) вершины как рассмотренные,

На третьем этапе мы рассматриваем вершины, на которые мы можем попасть из точек B и C и в таблице записываем значения из точки A до точек, которые мы достигаем из вершин B и С. Опять же помечаем эти точки, как уже рассмотренные.

На следующем этапе мы достигаем конечной точки G, но у нас происходит перерасчет (мы находим путь до F, до которого оказывается короче и перезаписываем значение в таблице).

И на следующем этапе мы проделываем тоже самое и находим самый оптимальный путь и узнаем, что из точки A в точку G мы можем добраться за пять условных единиц.

Рубрики
Графы

Графы «Матрица Смежности»

  • двумерный массив
  • граф представляют в виде матрицы смежности
  • вершины столбцы и строчки
  • есть путь — на перекрестие ставится 1
  • нет пути — на перекрестии ставится 0
Рубрики
Графы

Графы «понятие»

  • абстрактная структура данных
  • представляет множество вершин
  • набор рёбер — соединений между пару вершин

Пример

карта — города(вершины), которые соединены маршрутами (ребрами)

Какие бывают РЕБРА

  • однонапраленные
    идут слева на направа, а обратно мы возвращаться не можем
  • двунаправленные
    из A в B и B в A можем попасть