КАК РАБОТАЮТ ГРАФЫ | СТРУКТУРЫ ДАННЫХ

Скидка 50% по промокоду ALEKOS до 15.05.2023 г.

Подписывайся в соц. сетях:

❤️ Поддержка канала:

✔️ Полезные ссылки:

00:00 Введение
01:34 Характеристики графа
02:44 Интеграция
04:11 Граф как двумерный массив
07:09 Граф как набор узлов
08:05 Создание графа
09:04 Обход в глубину
12:16 Поиск пути
12:51 Поиск всех путей
13:18 Интеграция
14:36 Обход в ширину
16:07 Поиск кратчайшего пути
17:20 Алгоритм Дейкстры

Pb3XmBtztBuvyFvz2c9VpgyrNKgVozDjgpdAZzY

[AlekOS]

Код и структуры данных из видео - это просто шаблон.
В реальных языках порядок поиска и обхода может отличаться.

[nimbabul]

как врач могу сказать, что использовать слово "ребра" и в картинку вставлять бедреные кости - несколько сбивает с толку. С другой стороны, натуральные ребра не отражали бы идею прямой "грани", они же изогнутые. А те, которые не сильно изогнутые (например, ребра некоторых животных), не будут узнаваемыми "ребрами". Хотя и бедра - не очень узнаваемые "ребра")

[Rainmakeroffire]

Графы не работают - это делают крепостные. Единственным широко известным исключением в истории, и то с большими оговорками, является Л.Н. Толстой.

[igorglushatov]

Все круто, но алгоритм Дейкстры для поиска именно пути обычно так не рассказывают в вузах. Принято все таки при обновлении значения хранить и вершину из которой ведет минимальный маршрут. По памяти будет также линейно, но и по времени сделается линейным (от количества вершин в минимальном пути). В вашем же случае, если граф является полносвязным (что часто так и бывает), то вам придется при обратном проходе постоянно перебирать все вершины, чтобы все же найти откуда мы пришли.

[nestanetta]

Так ждала этот видос. Большое спасибо. Очень люблю вашу лаконичную подачу материала.

[Kwaiiii]

спасибо огромное за твои видео! я не видел больше таких понятных, интересных, и приятных обьяснений таких тем, спасибо!

[ghjklfghk]

Ооооооо. Ништяк. Заморочки на ноч грядущую подъехали. Спасибо

[Secvad]

19:10 а можно просто попутно для каждой вершины сохранять номер предшествующей ей вершины. И тогда путь автоматически будет готов под конец (правда в обратном порядке, но реверснуть его не сложно)

[uprynaDcraft]

сказал ребро, а на картинке бедренная кость! и как теперь доверять?😄

[zlspyhn]

Это супер полезное видео. Информация и визуализация и звук, тут все прекрасно

[kjgsreact]

ОоО как раз начал изучать алгоритмы и структуры данных спасибо

[kharlo_]

Впервые не пропускаю рекламу, в дань уважения к автору за такие максимально понятные и разжëваные видеоролики👍

[niconico]

Кто-то: "Аристократов на фонарь!"
Тем временем графы:

[nibunimu]

Когда мы ищем путь или кратчайший путь от точки A до точки B нам не нужны несвязанные графы - они не могут привести нас из точки A в точку B.

[vetl-foto]

Спасибо за видео, теперь хоть стало понятно как работает навигатор под капотом )

[vadimmatskevich]

Как же у меня сгорело от двух частей видео (во мне проснулся мастер по спортивному программированию и я начал ломать код в видео)
1 Нерекурсивный обход в глубину - вы не сохраняете состояние обхода дочерних узлов - получается что для каждой вершины обход совершается в квадратическое время от количества потомков вместо линейного - это недопустимое упрощение (представте граф-звезда тогда будет квадрат от количества вершин время обхода). Нерекурсивная реализация рекурсии - это очень сложная задача когда я в первый раз ее писал вышло в 2 раза медленее обычной рекурсии по быстродействию В олимпиадной жизни да в крайних случаях приходится писать такое если время на задачу осталось и больше решать нечего а в реальной жизни можно в опции компилятора увеличить размер стека.
2 Двунаправленный поиск в ширину - что??? meet-in-the-middle да есть такой вид перебора очень редкий вид задач в реальной жизни слышал про взломы защит таким способом Вместо 2^n получаем 2^(n/2) * что-нибудь типа n^2 (проверки совместимости половинок) тут реально есть смысл. А в графе что? В лучшем случае в 2 раза выйгрыш неимоверными усилиями не факт что так будет. Граф цепочка - и тогда путь между концами диаметра графа будет всегда n вершин - выйгрыша не будет зато помучаетесь немного с реализацией и будет расходоваться доп память для быстрой проверки принадлежности дереву поиска второй половинки. Неудачный просто пример вышел.

[rephexu]

Вовремя зашел! Топ контент, благодарю!

[malejeeck]

Видео не смотрел. Графы не работают. На графов работают.

[onxxx]

С каждым подобным видео, понимаю, как же уныло и максимально сложно объясняли это мне в ВУЗе...
Спасибо, что даешь нам возможность получать такую иныормацию с такой крутой подачей, еще и бесплатно!

[thenikehiro]

Напишу просто чтобы ютубчик продвигал в реки, а так видосик как обычно топовый, а когда видос по третьей части ассемблера?