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

[@AlekOS]

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

[@nimbabul8384]

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

[@Rainmakeroffire]

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

[@ВладиславСубботин-з1э]

Черт, ты меня опередил! Я хотел это сказать!!!

[@Rainmakeroffire]

@@ВладиславСубботин-з1э ничего, бывает) Комментарий, конечно, напрашивался.

[@MrTruth2]

Кому как не крепостным фашистким федерастам этого не знать

[@romansmirnov5813]

То чувство, когда гуманитарий решил зайти на видос по программированию

[@МихаилВасичев-з5я]

@@romansmirnov5813 Точно))

[@igorglushatov1948]

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

[@ghjklfghk]

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

[@nestanetta4817]

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

[@НиколайРюмин-й6и]

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

[@kjgsreact]

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

[@Secvad]

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

[@EvilYou]

Тоже вариант

[@_mrix_534]

Мне кажется, что путь, которому мы добрались до назначения не обязательно самый короткий: например, если бы путь от C до D был бы равен 1, то обратно машина поехала бы по нему.

[@Secvad]

​@@_mrix_534так... В смысле?

[@_mrix_534]

Фактически, когда мы вычисляем кратчайшие расстояния до точек, двигаемся мы по всему графу, так как метод calculateTimeToEachNode крутит цикл до тех пор, пока unprocessedNodes не пуст, а unprocessedNodes заполняется всеми точками графа. Когда метод заканчивается, остановиться мы могли на любой точке графа(в видео это обговаривается, когда автор из точки B двигается не в D, а в E; а в точке E мог быть тупик) , но уже зная все кратчайшие пути от точки start до остальных, поэтому обратный путь приходится вычислять таким способом. В своих примерах я постоянно говорю, что то-то могло быть равно тому-то, потому что в видео выбран довольно неудачный пример графа, из-за чего не видна вся суть алгоритма Дейкстры. @@Secvad

[@_mrix_534]

Да и в коде в конце метода calcutaleTimeToEachNode не видно, чтобы мы как-то сохраняли даже последнюю точку, поэтому мы в метод getPath передаём и стартовую, и последнюю точки.@@Secvad

[@Kwaiiii]

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

[@АлександрЦыбулин-д1м]

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

[@Karina-M-0]

Очень крутой видос, спасибо)

[@4upryna3Dcraft]

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

[@vetl-foto]

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

[@alexkazimir3835]

Класс🎉уважение за качество материала и за такой труд

[@andrewkruchini8614]

Наверное, первый ролик на канале, который разочаровал. При этом я подписан и считаю автора топовым по качеству изложения материала. И не понимаю восторгов в комментариях именно к этому видео, т. к. похоже, большинство дальше заголовка не идет, или смотрит на перемотке и строчит коменты по привычке, "за былые заслуги" (а остальные ролики, действительно, выше всяких похвал). Если я не прав, и дело во мне, буду благодарем, если мне объяснят хотя бы следующую идею из видео. Я понимаю, что можно взять учебник и вспомнить/разобраться во все самостоятельно, но я пытался честно вникнуть во все, что хотел донести автор, и КМК, один из немногих, . Первый раз "завис" на 4:30 идее "оставить в виде двумерного массива". Что значит "оставить", если смысл хранимых данных полностью меняется? Что означает "каждая ячейка будет являться отдельным узлом"? Какие данные будут храниться в "каждой ячейке"? Судя по картинке, номер узла? Зачем тут вообще ДВУМЕРНЫЙ массив? И что означает "отсутствие узла"? В итоге на 4:55 список "минусов" (каждый пункт, не буду повторять) и картинка выглядят, мягко говоря, станными. Лучше бы проиллюстрировали, какую топологию описывает данная "структура"... Еще больше вопросов в комментарии ув. @QwDragon. Буду признателен, если кто-то из разобравшихся ответит на них. Вообще, зная качество остальных роликов, эти неясности кажутся результатом неаккуратного монтажа. Если так - с нетерпением буду ждать "расширенную" версию.

[@_mrix_534]

Да, жаль конечно, что автор не разъясняет до конца, что происходит в видео. Сам на красно-чёрных деревьях завис, потому что некоторые методы надо было поменять или тонкости реализации не упомянуты. Однако я считаю, что это можно простить автору, потому что, по-моему, главная цель видео - описать логику реализации различных структур данных в коде, работу с ними, их плюсы и минусы. А то, что мы не понимаем некоторых моментов, - это уже наша проблема. Более того, если достаточно долго поработать со структурой данных, то начинаешь понимать смысл её реализаций и сам можешь разбираться в этом.

[@andrewkruchini8614]

@@_mrix_534да я вообще готов автору простить все за талант просто объяснять сложные вещи :) Тут скорее не претензия, а фидбек от "аудитории". "Ничего не понял, но очень интересно". Хотелось бы каких-нибудь пояснений, хотя, конечно, все можно "допилить" самостоятельно (гугл, лекции, учебники...)

[@niconico9568]

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

[@QwDragon]

Спасибо за классный контент! Но есть несколько вопросов: 04:33 Вообще не понял, что за структура. 05:04 Зачем тут нужен -1? 06:47 Значения узлов? Это вершины? Почему это минус? А веса могут быть любыми - они значения массива, а не индексы. 07:09 Ну с деревьями такая структура ещё используется (dom, xml), но вот с обычными графами - никогда не встречал. И её жирный минус - большое потребление памяти. 11:25 А как мы можем достать из стека посещённый узел, если проверяем посещённость перед тем, как его туда положить? 12:16 Обёртку теперь можно объединить с обходом. 13:17 Стоило отметить, что из passed теперь ещё и удаляются вершины. Ну и это будет жутко медленно. 20:48 Цикл по хэштаблице асимптотику портит же? Очередь приоритетов была бы лучше.

[@jonniuss]

классно тебе ответили чувак 😂

[@thenikehiro5278]

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

[@EvgShes]

Спасибо большое за труд, очень классные видео!

[@nibunimu]

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

[@nanai-mama]

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

[@stransey]

Я по прежнему пропускаю

[@user-oq1jk5fy4p]

ФУУУ, ТЕРПИЛА

[@kaiken9101]

У меня авто пропуск реклыммых интерграций)

[@nikmir8259]

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

[@TheShtroborez]

Ютуб не отдаёт анализ просмотра ролика пользователями из России. Так что, не имеет никакого значения пропускают или смотрят рекламу. Рекламодатель ориентируется на общее число просмотров видео у каждого автора. Кроме того, реклама остаётся навечно - она вшита в ролик и её будут смотреть спустя годы и века....

[@olegderevenets8943]

Полезное видео, лайк! Для интересующихся графами рекомендую свободно распространяемую электронную книгу «Графомания» (автор Деревенец О.В.). Даны решения задач с исходными текстами и контрольными примерами. Рассмотрены следующие темы: Задачи на множествах: • разбиение множества на подмножества; • задача о наименьшем разбиении (ЗНР); • задача о наименьшем покрытии (ЗНП). Группа задач на достижимость: • взаимная достижимость вершин; • кратчайшие пути между вершинами; • выделение сильно связанных компонент. Группа задач на размещение: • независимые вершины и клики; • доминирующие множества; • раскраски; • центры; • p-центры; • p-медианы. Остовные деревья Группа задач о потоках: • максимальный поток в сети; • поток, ограниченный сверху и снизу; • минимальная стоимость потока. Паросочетания на взвешенных графах: • паросочетание в двудольном графе; • паросочетание в произвольном графе. Цикл Эйлера и задача почтальона на взвешенных графах: • на неориентированном графе; • на орграфе. Задачи Гамильтона и коммивояжёра на взвешенных графах: • разомкнутая задача Гамильтона; • замкнутая задача Гамильтона (контур); • комбинирование методов для задач Гамильтона; • замкнутая и разомкнутая задачи коммивояжёра.

[@leomysky]

Круто Очень круто Большое спасибо за видео

[@MikhailGoncharov-tl4cr]

Золотой, золотой ты человек

[@Aristotle314]

Забросил программирование и математику уже как пол года, но всё же интересно

[@Piixel2517]

Почему?

[@Aristotle314]

@@Piixel2517 понял, что не моё. Родители были программистами, все остальные в семье - тоже. Я думал, что стать программистом - моя судьба, продолжал что-то изучать, делать... Никогда у меня это занятие не вызывало подлинного интереса. Это начинало понемножку "убивать" меня. Я выгорел, мне было очень плохо, я не понимал, что со мной происходит. Решил всё-таки сменить курс, как только понял, что не замечал истинную страсть. 8 лет своей жизни я просто просрал, ведь думал, что раз все избрали именно этот путь, то и мне будет там хорошо...

[@Piixel2517]

@@Aristotle314 а если не секрет, то в какой степь двигаешься?

[@Aristotle314]

@@Piixel2517 биологию я для себя открыл

[@Piixel2517]

@@Aristotle314 звучит круто, успехов тебе)

[@menako778]

Делал задачу на графы - буквально нашёл решение в твоём новом ролике! Спасибо!

[@ИгорьСтепанов-и1п5х]

Когда думал что оптимизируешь а на самом деле оказалось...

[@dotokha8468]

смотрю этот канал, ничего не понимая, чисто офигеваю со сложности программирования

[@thinhenson2182]

Вот наконец-то нашёл человека, который реально шарит

[@pinkierar_real]

Я уже давно смотрю канал Артём граф, но никогда не знал ничего про графы. Спасибо

[@dimabobrov582]

А канал то хороший, Артем крайне воспитанный и начитанный молодой человек, не то что эти ваши блогеры современные

[@evgenysamarin]

Однозначно вижу популяризацию знаний ставлю лайк ❤

[@Vic7bd]

Отлично как всегда! Немного быстро, но это не проблема ведь можно пересматривать и замедлять :-) Когда же мы изучим как обходить и перепрыгивать рекламу на автомате )))) это самый востребованный сейчас бот в мире, чтоб распознавал и перескакивал или если перескочить нельзя (на ТВ), то глушил сразу звук и замещал отсчётом времени или своей картинкой "Отдохните n-минут, посмотрите на своего котика" )))

[@TrueCyberian]

Красава. Как всегда доступно только сжато.

[@rechw769]

чувство, будто бы кто-то написал приятные конспекты и дает почитать

[@MMC_Repair]

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

[@evilvirraZzz]

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

[@zmeyotkusitel]

Не influence случайно?)

[@evilvirraZzz]

@@zmeyotkusitel Нет, но я ей вдохновлялся. Хорошая игра в своем жанре:)

[@Sergey.Ts_]

Крутейкий ролик! Буду думать где такое применить... Может "Навител" переписать 😁 А то тащит вечно в непонятные графы

[@Radik_Hatmullin]

Если графы работают, значит произошла революция

[@parvinaliyevv]

Братан, просто респект 🫡

[@vadimmatskevich8439]

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

[@learningmeansdoing]

Вопрос по алгоритму Дейкстры. Для восстановления пути мы можем запоминать родителя той или иной вершины, ну и менять родителя при необходимости. Так разве не проще, чем восстанавливать путь по значениям расстояний?

[@shu3s]

проще, я так и делаю

[@memnyi_gecksorall]

Пятый раз уже пересматриваю чтобы сделать свою реализацию

[@wersa45]

Ждем разбор алгоритмов поиска А-стар и Суурбалле! )

[@flexford1able]

На мой взгляд тоненькая книжка под названием "Грокаем Алгоритмы" лучше объясняет алгоритмы чем такой видос

[@НурсейитАхунбаев]

круто !!! просто нет слов !!! В универе .....

[@sh0ny]

У автора талант преподавания !

[@alexeyy8133]

Не бывает самой минимальной или самой максимальной величины. Бывает минимальная или самая малая и максимальная или самая большая. А самая мин. или самая макс - это как масло масляное.

[@alexfantast6566]

Как всегда афигенное подробное видео, где всё разложено по полочкам 👍👍👍

[@djadjaandrey]

Thanks a million!

[@BellaLugoshi]

читал это и слушал много раз за последние 30 лет, но так и не понял чем это отличается от двумерных массивов или структур в Си/Паскале, без всякого ООП. Я всегда пользовался каким-то движком БД и SQL. Там то же хеширование для двумерных массивов. Скорость огромная. Память? Ну оно всегда так - либо быстро либо мало памяти. Задачи на память конечно бывают, в тех же МК, где порой оперативки 1-16 Кб, но там и SQL нет.

[@tapkafapka7551]

Круто рассказываешь! но этот звук карандаша... просто жесть..

[@shoqun6360]

Продлевать слово это как заполнять паузу пока думаешь что сказать, можно просто сказать в обычном темпе и сделать паузу чтобы зритель мог обдумать сказанное

[@duoduoo6732]

лучшее видео про графы

[@victor_zimin]

Видос класс. Единственное в алгоритме Дейкстры при обратном обходе не совсем понятно, что происходит если несколько ребер соответствуют условию равенства!

[@MusorniyAkkaunt-mw5ll]

Тиканье фоном крайне раздражает, сделайте тише в будущем.

[@UCFaqdXdFIRYF5rmFih4GNkQ]

В ОГЭ по информатике есть задача по алгоритму Дейкстры, получается.

[@МихаилВасичев-з5я]

4:41 ааа, скрип карандаша о бумагу(вернее, наверное об доску)

[@МихаилВасичев-з5я]

7:17 ааа, опять

[@kirakorunov5407]

Спасибо бро

[@justnikocat]

имба тема, топовые видео, ахуенный чел, все до тапок хорошо

[@vladpromzelev4111]

Спасибо за видео! Вот только узлы это не классы, а объекты (классов). 7:18

[@francheskodown]

Подробнее с алгоритмами поиска кратчайшего пути в направленных графах поверхностно можно ознакомится в книге Т.Х. Кармена Алгоритмы:Вводный курс.

[@TheShtroborez]

Тема родителя номер 1 и родителя номер 2 не раскрыта в графах...

[@vincentlaw6751]

неплохое видео, но алгоритм дейкстры плоховато рассказан, есть куда проще и понятнее реализации

[@darkfrei2]

Можешь показать как это делается в Lua?

[@ЕвгенийСахаров-т7ы]

Насколько я знаю, cg pods так и не показали своё производство. А это значит, что с большой вероятностью, они таскают наушники из Китая и переклеивают шильдики. Об этом есть масса инфы в интернете, на пикабу в частности...

[@XitriyLis-km9kj]

вот те на, удивил. пожалуй, большая часть производства находится в Китае.

[@ЕвгенийСахаров-т7ы]

@XitriyLis-km9kj они-то позиционируют, что у них производство там, где они сидят...

[@XitriyLis-km9kj]

@@ЕвгенийСахаров-т7ы бизнес. любой товар найдет своего покупателя. дураков хватает. если человек мамонт, пусть его стригут, зачем препятствовать? люди, которым действительно нужен хороший звук, не будут покупать хлам.

[@XitriyLis-km9kj]

@@ЕвгенийСахаров-т7ы ля, чего только стоят всякие леомаксы с отдельными каналами для вещания своего говна 24 на 7 по тв)))

[@koresh10]

Если убрать всю рекламу и воду, останется 5 минут полезной информации. Но автор ценит только своё время

[@vicos2503]

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

[@duoduoo6732]

графы это алгоритм поиска или структура данных?

[@airatrahm1179]

Картинки красивые и стильные. Но речь очень сложно воспринимать. Например такая фраза: "Минус один здесь снова обозначает отсутсвие узла и получается, что если у одного узла есть три ребра, которые ведут на три его дочерних элемента, то в масиве под каждые из этих ребер будет создано три записи". Как одно из другого следует? Почему эти две фразы слиты в одну посредством "и получается"? 🥱

[@thenc4568]

Хотелось бы ещё узнать про алгоритм А*

[@Graviton1917]

10 из 10 👍

[@Arkham_nine]

Даёшь разбор алгоритма Тарьяна и Кхана

[@eazy_profit]

А можно как-то просто объяснить где дешевле использовать рекурсию, а где цикл? В общем случае

[@MahMoodTechnologies]

Лучше всего использовать циклы, рекурсии могут вызвать переполнение стека

[@zmeyotkusitel]

Семестр теории графов в университете или видео на 22 минуты? Сложный выбор.

[@АнтонМирный-с5х]

Спасибо

[@OPKECTPAHT]

Как работают графы? Странный вопрос. Графы дворяне, они не работают! )))

[@call_nick]

Учёный под названием Дейкстра)

[@elbaron5762]

Как раз в унике проходим графы. На парах это очень уныло, в ролике достаточно показательно и информативно. Спасибо.

[@ВиталийГеннадьевичЛободин]

Автор бедренную кость (это та, которая ходить мало-мало) называет ребрами. Вопрос - как он называет другую кость, голову?

[@СергейЮров-б6е]

Уважаемый, у вас там не рёбра, а бёдра))

[@MrVellial]

4:25 Ужснх! Вы б ещё пенопластом по стеклу посребли >.

[@Alexey0795]

кости не ребряные а бедряные)

[@СергейУсачев-м8г]

А если граф неориентированный, кто будет его родителями?(parents)

[@Pivikua]

В методе getPath после цикла забыл return false;

[@MACTEPCKA9I_HA_MUHUMAJIKAX]

Так, сразу стоп, я не понял... Зачем представлять переходы в виде данных?? Переходы надо делать, а не представлять. Тогда зачем данные, когда всё-ровно всё сведётся к переходам в коде. Jmp, jne, call, ret, int... Сразу пишем код, ну и флаги состояний.

[@АккаунтВременный-ш2ы]

За ролик огромное спасибо! А вот реклама наушников меня насмешила))) Реально штоль кто-то покупает наушники за 5000? Или тем более за 12000+?))) У меня весь телефон стока стоит, а наушники мы отхватили за 150 рублей на китайской распродаже, и шикарные оказались))) Два года проработали, пока аккумуляторы не сдохли!

[@guitarkiller86]

Okey❤

[@tinersy]

Лайк не глядя, комментарий для статистики любимого канала

[@majestick]

Ничего не понял с двумерных массивов(

[@gyynhildiv3813]

Даров

[@malejeeck]

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

[@ОлегЛегейда]

говорит про ребра, а показывает бедренную кость.

[@ВасилийШумилов-о8ь]

Графы я так и не осилил. Теория просто проваливается без понимания, а практических задач решать так и не приходилось.

[@justdaxik]

АлекОС - провидец. Только мы начали тему графов в учебке - и тут как тут с видосом)))

[@egorio9534]

Открывай школу )) 😅

[@diceline1677]

Продвигаем твой контент комментарием.

[@МаскимБардин]

Дискретная математика 2 курс)

[@billlanc9461]

Сложно, но познавательно.

[@qwerty-fz5kv]

А можно видос про ИИ и про то что программистов ИИ заменит? Очень хотелось бы узнать мнение автора на эту тему

[@AlekOS]

Не заменит

[@qwerty-fz5kv]

@@AlekOS Спасибо за ответ! Сам недавно начал изучать Джаву, а тут возник хайп по поводу ИИ, пошла такая демотивация, очень сложно было справится с этим чувством и преодолевать его. Все ждал компетентного ответа с этого канала, которому можно доверять)

[@smalyu]

@@AlekOS Можете привести какие-то аргументы, почему не заменит? А за видео спасибо большое, очень круто!

[@rutexgreat3619]

@@smalyu аргумент один: математика. Текущие общепринятые модели МО работают через линейные регрессии (и кучу других подвидов вроде трансформеров и им подобным), что априори совершенно не располагает к анализу и созданию нового. Единственное что они могут заменить - какого нибудь джуна у которого график в неделю на уровне пары часов, где найти некоторый сниппет или готовое решение к фундаментальной проблеме быстрее чем платить джуну. Если появится модель, которая сможет заменить любого средне или высококвалифицированного спеца - то там и до терминатора совсем недалеко будет уже и проблемы совсем иного ряда пойдут... Поэтому это все смех на палочке и можешь смело смеяться всем в лицо когда тебе такое говорят.

[@smalyu]

@@rutexgreat3619 Понял, спасибо за ответ!