Комментарии 42
Всем привет! Меня зовут Нурислам (aka tonitaga), и сегодня я бы вам хотел рассказать об Основных алгоритмах на графах.
да, но зачем?
спасибо, лучше не надо :)
Хорошая статья, пригодится для моего обучения
Я как бы напомню, кому нужна профессиональная реализация алгоритмов, то есть Boost Graph Library (BGL) и Parallel BGL.
Матрица смежности это один из вариантов представления графа в памяти компьютера. Есть и другие способы, но простой обёртки, которая знает количество рёбер, вершин и тип графа, достаточно для большинства задач, можешь ознакомиться с этой обёрткой у меня на github'e "GraphAlgorithms"
Но вы же действительно перепутали "граф" и "техническую реализацию" графа.
Ничего не было перепутано, просто заголовки читать надо, заголовок, перед упоминанием обертки матрицы смежности, такой "Представление графа в коде"
Что ж если продолжаете упорствовать в совём заблуждении:
представление графа в коде
Графом будет называться простая обертка над ххх
Это ошибка. Не "графом будет называться обёртка над ххх", а "граф будет реализован как обёртка над ххх" - ну за исключением случаев когда вы граф зачем-то определяете не так, как общепринято.
просто заголовки читать надо
Наличие какого угодно заголовка не даёт индульгенции от фактических ошибок.
Итог (пока предварительный):
Статья не рекомендуется к прочтению потому, что:
1. статья содержит ошибки (что снижает её качество).
2. После указания на фактические ошибки автор вместо исправления их и улучшения статьи пытается выкрутиться чтобы их не исправлять.
Графом будет называться простая обертка над матрицей смежности
Автор, дайте нормальное определение графу и не вводите людей в заблуждение.
Граф 
— это пара множеств 
где 
— непустое конечное множество элементов, называемых вершинами графа, а 
— множество пар элементов из 
(необязательно различных), называемых ребрами графа.
То что вы написали является всего лишь одним из видов записи или представления графа в компьютерных науках. Другими способами записать граф являются:
лист смежности (adjacency list)
лист вершин (Edge list)
матрица инцидентности (Incidence Matrix)
Compressed Sparse Column или Compressed Sparse Row (обычно для больших разреженных графов)
Каждый из указанных методов имеет свои достоинства и недостатки.
Делать такое однозначное утвеждение, что "Графом будет называться простая обертка над матрицей смежности" - простите, но это либо верх неуважения к аудитории либо банальное невежество.
Уж простите, не смог пройти мимо и не поправить.
Просто хочу немного подискутировать: Как мне кажется, граф это неопределяемое понятие, понимаемое на уровне интуиции. Ну т.е. определение то есть, но если подумать, оно определяет само через себя.
Точно так же как и функция. На примере функции проще объяснить. Что такое функция? По определению это правило, которое ставит элементу множества X элемент из множества Y, обладающее свойствами... А что такое правило? Ну это же синоним слову функция. Просто игра слов. Ок. Есть другое определение слову функция - это подмножество из множества декартового произведения XxY, обладающее свойствами... (Очень похоже на ваше определение графа. Ну и это понятно, ведь с помощью графа можно определить функцию). Но подождите, мы же ничего по сути не поменяли. Было - функция это правило сопоставления элементов... Стало - функция это правило по которому из множества декартовых произведений выбирается подмножество... Опять все упирается в правило, которое является синонимом самому слову функция.
Что касается вашего определения графа, это правило, по которому выбирается подмножество из декартового произведения VxV. А правило это по сути некоторая функция, а функция может быть определена с помощью графа. Круг замкнулся.
Даже не знаю что и сказать, почитайте основы мат. логики и теории множеств, там все описано. Функция это подмножество декартового произведения, как вы его выберете? Ну можно предикат определить, или просто перечислить все элементы если множество конечное.
И в случаи графа дуги это именно конечное множество упорядоченных(или нет, если граф не направленный) пар вершин, это множество конечное, и его можно просто перечислить. Все просто.
И автор комментария правильно написал, что представления графов множества, и чаще всего матрица смежности далеко не самое эффективное.
Хм это я не знаю что сказать. Вы предлагаете использовать предикат, чтобы определить подмножество, которое определяет функцию. Но предикат это и есть функция.
И вы мне ещё будете советовать читать основы мат. логики и теории множеств... Вам не показалось, что я их достаточно хорошо знаю, если вижу потенциальную проблему в определении графа?
Извините, но у вас и правда рассуждения немного "не в кассу". ИМХО, определение графа через множества вершин и ребер одновременно и строгое, и интуитивно понятное. Вы говорите, что множество ребер графа может быть задано как логическая функция от VxV. ОК, пожалуйста. В этом нет никакого противоречия.
А что такое правило? Ну это же синоним слову функция.
Что такое функция? По определению это правило, <...> обладающее свойствами...
Вообще-то это оффтопик, тут не про функции разговор, а про графы, но ладно. Почему вдруг синоним? Не любое правило есть функция, так что это уж точно не синонимы. "А есть такое Б, которое обладает свойством С" - типичное логическое определение. Это вовсе не тавтология. А определяется не "само через себя", а через Б и С.
ведь с помощью графа можно определить функцию
Ну это ваше собственное заявление, никто тут такого не говорил. Далеко не любую функцию можно определить через граф.
Если рассуждения "не в кассу", прошу извинить. Я сразу написал, что предлагаю подискутировать на тему сложности определения термина граф, раз уж автору тыкнули, что он определяет граф как то не так, как принято. Чтобы те, кто не хочет дискутировать, не обращали внимание. Ну а моё мнение, что такого рода сущности не могут быть никак определены, так же как невозможно определить что такое точка, прямая и плоскость. Ну и что такое функция тоже невозможно определить, поэтому я много написал про функцию, т.к. граф и функция взаимно эквивалентны и могут быть выведены один из другого. Ну т.е. определения то у них есть. Но это такие определения-заглушки, нужные для педагогического процесса, чтобы студенты не смущались от того, что опереируют неопределяемыми терминами, для них придумали определение термина через себя самого, но сделали это завуалированно, чтобы было незаметно.
Функция и правило не синонимы. Ну пусть не синонимы. Но тогда неплохо бы определить что такое правило, а не подменять один термин другим, у которого нет определения. Можно говорить, что функция это правило, отображение, мэппинг, способ сопоставления и т.п. но по сути это игра слов и подмена одного загадочного термина на другой.
И почему это не любую функцию можно определить через граф? Можете привести пример такой функции? Как я вижу, если есть f: X -> Y, то её можно определить как граф, где каждое ребро соединяет x и f(x).
Ну подискутировать я и сам рад, только чтобы была связь с исходной темой, а то будем смешно выглядеть тут.
По-моему, то, что не любую функцию можно задать графом, совершенно очевидно даже школьнику. Вам нужен пример? Пожалуйста: f(x) = x^2. Да и вообще любая функция, определенная на множестве действительных чисел. (Про комплексные даже и не заикаюсь.)
Теперь по поводу определений и аксиоматических понятий. Вы правы в том, что не все определения логически строги. Но эта нестрогость, как ни странно, добавляет им смысла. А рекурсивное "разложение на атомы" какого-либо понятия вплоть до самых аксиом как раз смысл и отнимает. Потому что смысл понятий заключен не столько в их определениях, сколько в их связях и соотношениях с другими понятиями.
Раз мы тут про графы говорим, то ваш поход предполагает, что связи между понятиями образуют направленный ациклический граф, который можно отсортировать топологической сортировкой от высоких уровней абстракции к низким. Но эти взаимосвязи, вероятно, все-таки образуют более сложную структуру.
Не понимаю в чем проблема построить граф соответствующий функции f(x) = x^2 ? Просто каждую точку х соединить ребром с точкой x^2.
Более строго: G=(V,E) где V = R, E = подмножество из RxR, такое что второй элемент пары равен квадрату первого элемента.
Не понимаю в чем проблема построить граф
Ну вот мне прямо интересно даже стало. Раз нет проблем, то постройте, пожалуйста. Мне очень интересно, как вы каждую точку бесконечного множества будете ребрами соединять с чем-то еще. Я хотел бы это увидеть на чертеже. Или в виде матрицы смежности. Или любой другой вышеупомянутой структуры данных.
Ну как бы далеко не каждый граф можно изобразить на чертеже. Очевидно, что если множество ребер графа более чем конечно, то отобразить его на рисунке или запихать целиком в память ЭВМ несколько затруднительно. Просто в таких случаях граф задается аналитически.
Более строго: G=(V,E) где V = R, E = подмножество из RxR, такое что второй элемент пары равен квадрату первого элемента.
Вы вот это называете "аналитическим заданием графа"? О, я так могу очень многое "аналитически позадавать". Вот например, сейчас "задам" четырехугольник с числом углов n=5. Разве кто-то может запретить четырехугольнику приобрести еще один угол?
Да, кстати, а почему "далеко не каждый граф можно изобразить на чертеже"? Бумаги не хватает?
множество R несчётно, а в графе количество вершин должно быть счётно. и никакие ЭВМ не помогут.
Вы предлагаете использовать предикат, чтобы определить подмножество, которое определяет функцию. Но предикат это и есть функция.
https://en.wikipedia.org/wiki/Predicate_(mathematical_logic)
И вы мне ещё будете советовать читать основы мат. логики и теории
множеств... Вам не показалось, что я их достаточно хорошо знаю, если
вижу потенциальную проблему в определении графа?
Там нет проблем, есть ваше не понимание основ предмета, которому уже сотня лет стукнет. Типичный пример Даннинга - Крюгера: мало что понимаю в вопросе, но свое мнение выскажу.
Т.е. по вашему предикат это не функция!?
Поскольку наш собеседник сразу заявил, что общепринятое определение графа ему не указ, и что "граф это неопределяемое понятие, понимаемое на уровне интуиции", то он теперь может назвать "графом" что угодно, хоть синусоиду. И никаких противоречий в его рассуждениях не возникнет. Очень удобно! :)
Мне кажется я достаточно убедительные доводы предоставил к своим аргументам. Вы их никак не можете опровергнуть зато отмахиваетесь, обвиняя меня в том, что я типичный пример Даннинга - Крюгера. В научном диспуте так поступать не этично. Ещё раз - если вы не хотите или не можете дискутировать, не дискутируйте. А просто прибежал, обвинил человека в том, что он мало чего понимает и убежал никак не удосужившись подтвердить свои слова, это как то недостойно.
В научных спорах не принято бравировать авторитетом и регалиями, а принято приводить логические доводы и агрументы, но мои аргументы вы проигнорировали, сославшись на то, что предмету уже сотни лет, видимо намекали на то, что такой почтенный возраст уже сам по себе авторитет. Ну а арифметике уже 10 тысяч лет, но до сих пор ведутся ожесточенные споры по ее аксиоматике.
Ну если вам логических доводов недостаточно, и необходим авторитет, то у меня есть 2 опубликованные статьи по математике. Не в области теории графов, а в области теории случайных процессов, но тем не менее, я вас уверяю, что основы теории множеств и логики я кое-как, худо-бедно знаю. Не знаю, право, достаточный ли это аргумент, чтобы вы перестали считать меня типичным примером Даннинга - Крюгера, если честно, я думал что и моих логических доводов должно быть достаточно, но как показала практика люди здесь логику не очень то уважают.
Так там же есть заголовок перед этим, "Представление графа в коде", потому что без этого было бы непонятно такое выражение graph(v1, v2), а до этого есть заголовок, про сам граф, где я отставил ссылки для ознакомления с самим понятием графа.
По каким критериям вы отобрали эти 5 алгоритмов как "основные"? Ну ладно, обход в ширину и глубину - наверное, и правда. А остальные? Почему, к примеру, не алгоритмы раскраски графа? Или поиска паросочетаний? Или поиска полносвязного подграфа? Или решения "задачи коммивояжера"?
Впрочем, ответ на эти вопросы предположить нетрудно: вы описали те алгоритмы, которые знаете сами. Но не вводите, пожалуйста, людей в заблуждение, заявляя, что "все основные алгоритмы будут находится в одном посте". Алгоритмов на графах хватит на несколько книг. Даже если ограничиться наиболее известными и важными, все равно это потребует книги, а не поста. И такие книги уже написаны. (Думаю, именно это и имеют в виду те, кто пишет "спасибо, не надо".)
Ну и наконец, алгоритмы интересны тем, какие задачи они решают, а не тем, в честь кого они названы. Оглавление статьи очень неудачное.
Например, задача коммивояжера, эта та задача и алгоритм ее решения точно тема отдельной статьи. А BFS DFS это база, да и кратчайшие пути межд вершинами и всеми парами вершин, как по мне база. Согласен, что и целой книги не хватит для описания алгоритмов на графах.
Про статью "решения задачи коммивояжера" вы явно пошутили, там просто про один из наиболее эффективных подходов к точному решению - монография страниц на 500. И без мат подготовки, вы просто не поймете, что там написано.
Про "аппроксимирующие" алгоритмы и методы локальной оптимизации, применительно к этой задаче, еще можно одну книгу написать.
Алгоритм там не сложный, сложнее его понять и реализовать, как раз для этого придется прочитать не мало тех.материала, согласен, но в одну статью это уместить можно, убрав воду. Причем в таких книгах больше половины (как по мне) просто дискуссия и обсуждения, доказательства, теоремы и т.п.
С моей точки зрения, доказательство того, почему работает алгоритм — это одна из самых интересных вещей, достойных упоминания в статье (зависит от темы статьи, конечно). Например, почему алгоритм Дейкстры получает корректный результат и чем ему «мешают» рёбра с отрицательным весом.
По содержанию статьи: по-моему, Вы перепутали, какой из алгоритмов найдёт кратчайший путь в лабиринте. Это должен быть BFS. DFS найдёт путь, но не обязательно кратчайший.
"Алгоритм там не сложный" это вообще о чем? Это NP задача(задача коммивояжера), там единственный не сложный алгоритм - это полный перебор, все остальное там сложное или очень сложное. (может быть за исключением совсем наивных "жадных" алгоритмов)
Нет описания алгоритмов простыми словами
Реализация по пунктам это хорошо, но что из себя представляет тот же самый dfs? Зачем он и какова его суть?
Без базового понимания что это такое человек даже не сможет придумать куда его впихнуть
Лучше добавить описание под каждый алгоритм
статья отличная!
Было бы здорово свести в какую-то главу достоинства и недостатки разных алгоритмов. Например: требования к памяти, какие виды графов подходят лучше, итп
Простите, но статья содержит много ошибок.
1. Ничего не рассказано о представляниях графов. На мой вкус, это ошибка с образовательной точки зрения.
2. Представленные реализация DFS и BFS имеют сложность O(V*V), а не указанную в статье.
3. Представленная реализация алгоритма Дейсктры имеет сложность O(V*V), а не указанную в статье.
4. Кроме того, есть смысл обсудить когда реализации O(E*logV) лучше, а когда хуже O(V*V).
Это всё базовые вещи, которые статья не описывает, дальше Дейкстры читать не стал. Мои рекомендации автору и желающим понять эти алгоритмы:
Дасгупта Санджой, Пападимитриу Христос, Вазирани Умеш. - "Алгоритмы".
Она выложена в интернете на русском языке (например, тут). Школьникам может быть что-то сложновато, но для начинающих разработчиков/студентов самое то.WIKI-конспекты ИТМО.
Очень хорошие тщательные конпекты, написанные профессионалами. Но это именно конспекты, а не учебник, а потому написано суховато.Лекции Куликова А. на лекториуме по книге Алгоритмы Дасгупты.
Кому-то может понравиться больше, чем сама книга. Кстати, сам Куликов переводчик ее на русский язык, а редактором был Шень.
У меня есть более полный список на github, там есть разные источники на разные вкусы. Не сочтите за саморекламу.
Основное отличие BFS от DFS только в том, что BFS используется очередь а DFS используется stack, в остальном алгоритм обхода практически не отличается
Грубейше не верно! Кто-то постоянно распространяет эту чушь среди студентов...
Классический алгоритм DFS, в частности по тому же Дийкстре, должен быть рекурсивным, то есть в нем должны быть четко выделенные этапы прямого и обратного хота, или, другими словами, этапы "раскраски" вершин: первой визит в вершину графа на прямом ходе алгоритма (белая вершина становится серой) и последний визит в вершину на обратном ходе алгоритма (серая вершина становится черной). Множество вторичных алгоритмов построено на основе дийкстровского DFS и используют именно эту структуру алгоритма с "перекраской" вершин.
Простой заменой очереди на стек вы не получите DFS из BFS. Вы получите некий псевдо-DFS, который правильно воспроизводит последовательность первых визитов в вершины, но не воспроизводит обратный ход алгоритма. Это не DFS, по крайней мере в каноническом понимании.
Базовые алгоритмы на графах