Pull to refresh

Comments 70

Любопытно, как меняются стереотипы. А ведь еще совсем недавно «самый первый пример который приходит в голову», был о решении транспортной задачи. :)
Согласен =)
Сейчас первое что пришло в голову это люди и дружба между ними (читай: социальная сеть)
Я думаю есть куча менее очевидных, но более интересных применений. Интересно было бы привести именно такие примеры.
Вот отличный пример: в игре «11й час» была головоломка. Обрезок шахматной доски, на котором чёрных и белых коней нужно было поменять местами (скриншот). Мы долго бились, перебирали варианты.

В универе мы только начинали изучать дискретную математику, в частности — теорию графов.

И неожиданно мне в голову пришла мысль: а что, если ситуацию в виде графа, где узлы — клетки доски, которые соединяются возможными ходами коней. Сказано — сделано. В итоге получилась настолько простая картинка, что головоломка становилась детской (а-ля головоломка с поездом и сменой порядка вагонов при том, что есть тупиковый запасной путь). Однако на шахматной доске эти пути были как бы завязаны в узел, потому головоломка казалась сложной :)
BFS с описанием алгоритма, кодом, примерами применения и многим другим, в следующей части =)
Фундаментальная книжка. По мне, так каждый должен прочитать )
Согласен. Но людей надо заинтересовать, я надеюсь что такими статьями можно заинтересовать людей которые совсем не знакомы с темой. И о Кормене откуда-то нужно узнать.
Сам читал Кормена несколько раз и считаю что каждый Программист (именно с большой буквы) должен прочитать. Идея в том, что нужно где то один раз наткнуться на тему а дальше каждый сам решает если ему достаточно такого описания или он пойдет читать Кормена.
Так или иначе, написано довольно адекватно. Я бы заинтересовался %)
Заинтересовался, спасибо.
Лет 10-20 назад всем советовали читать Кнута.
Ф. Харари — Теория графов. Замечательная книжка. Но для программирования обычно хватает университетского учебника по дискретной математике + описания необходимого алгоритма.
BFS уже был в этом же блоге, помогло при подготовке к экзамену по дискре =)
Граф — это абстрактное представление множества объектов и связей между ними. Графом называют пару (V, E) где V это множество вершин, а E множество пар, каждая из которых представляет собой связь (эти пары называют рёбрами).

У меня в университете преподаватель по дискретке, который этими самыми графами и алгоритмами на них уже не один десяток лет занимается, такую формулировку пресекал на корню.
«Граф есть множество и бинарное отношение на нем» — это как четкое математическое определение.

+++
Ничего лишнего и всё правильно!!! В википедию закиньте, плз!
Вы про эквивалентность определений слышали? В той же дискретке даётся как минимум 5 определений дерева ;)
К слову, в дискретке нет понятий «вершина», «ребро», а есть понятия «множество», «n-арное отношение». Я не посягаю на эквивалентность определений.
Выше чётко сказано, что вершинами называют элементы множества, а рёбрами — пары элементов относительно бинарной операции(отношения). Не думаю что эти термины где-то определены по-другому.

А насчёт базовых определений — никто (надеюсь, никто) не спорит. Без них никуда.
И кто вам такое сказал. Я учусь на специальности прикладная математика и подобные определения вроде вершина, ребро, ориентированность и подобные очень часто используются. Тем более, что определение графа использует эти понятия.
Определение графа дано выше. В нем только 2 основных понятия из дискретной математики. Все остальное — то, что входит в раздел «теория графов». Именно там:
— будем называть элементы множества вершинами;
— элементы бинарного отношения — ребрами etc.
Вот из-за того, что большинство учёных — анектдотические армянские пионеры (которые, как известно, выбирают сложный путь), наука непопулярна.
UFO landed and left these words here
Мне тоже такое определение больше по душе, но всеж статья как бы ликбез, поэтому определение «на пальцах» тут гораздо уместнее, иначе пришлось бы писать все сопутствующие определения (бинарные отношения etc)
такое определение не расширяется на мультиграфы, то есть на графы с кратными ребрами (несколько ребер между одной и той же парой вершин)

Наиболее четкое математическое определение графа выглядит так:
тройка (V, E, phi) множества вершин V, множества ребер E и отображения из множества ребер в множество пар вершин phi.

Но согласитесь, что в статье для широкой аудитории определение из статьи будет наиболее понятно и достаточно математически корректно)
UFO landed and left these words here
Вот самое правильное определение. :)
И все-таки оно не достаточно корректно, так как из него не очень понятно (читай совсем непонятно) как соотносятся элементы из V с элементами из E
хотя в жизни все конечно пишут просто (V,E) а не (V,E,phi), ибо лень просто. phi держим в уме :)
А по жизни скорее бинарные отношения любят представлять в виде графа, а не наоборот.
оно = определение из статьи. зарапортовался, простите.
Первое определение может и не очень четкое, но как-то больше располагает неподготовленного читателя.
UFO landed and left these words here
Из такого определения напрочь выпадает специфика графа.
Не упомянуты основы:

1. Cмешанный граф — когда есть ребра с ориентацией и без;
2. Формально ребер между двумя вершинами может быть несколько (мультиграф);
3. Ребро может быть петлей (соединяет вершину саму с собой): A[i=j] > 0;

Яркие примеры: разводка печатных плат и транспортные задачи.
Мне кажется, что это не совсем основы.
Ну мультиграфы — вполне основы и многие алгоритмы с ними и работают. Псевдографы — да, реже применяются.
Это _тоже_ основы.
Изложенные в статье без этого недостаточно полно.
Мультиграф это просто обобщение теории…
О котором неплохо бы упомянуть…
Замечательно написано, жду следующих статей с великим нетерпением!
Спасибо конечно за ссылку, но таким образом я просто хотел сказать автору спасибо за труды праведные.
Возьмите книгу Седжвика, пятую часть Фундаментальных алгоритмов, всяко книга лучше статей, хотя и их читать тоже полезно.
чтобы не томить себяожиданием можно открыть учебник, все то же самое только без комментов
Эх, а когда преподавали это в универе, казалось «Что это? Зачем это мне надо? Кто поставил эту ересь в предметную сетку?»
А сейчас так очень даже интересно ))
Сейчас ответ очевиден — чтобы не придумывать велосипед с квадратными колесами =).
Интересно — за что тебя минусуют?
Ну да. Вообще, очень многое из того, что на учебе кажется ненужным, оказывается крайне полезным спустя каких-то несколько лет.
А минусуют — да боги с ними. Один одаренный и до кармы добрался ))
1. Не сказано о массиве смежностей, как одного из способов представления графа, который является экономным по требуемой памяти, но эффективен, когда нет необходимости корректировать граф.
2. Раз уж речь пойдет об алгоритмах, то следует в базовые понятия включить определение «алгоритма» и «сложности алгоритма»

В общем, получилось достаточно легковесно и доступно, с удовольствием буду следить за продолжением… Спасибо.
3. Не было сказано о взвешенных графах… Это тоже одна из основных вещей.
1) Описание не привязано к языку программирования. Массивы есть не в каждом языке.

2) Конечно, про сложность каждого алгоритма нужно будет своевременно сказать. Но не было их ещё. А забивать статью сторонними (алгоритм, сложность..) определениями всё же не стоит. Они довольно интуитивны, и найти формальное определение нетрудно.
оригинал xpic99:
BFS с описанием алгоритма, кодом, примерами применения и многим другим, в следующей части

Код будет, либо на псевдоязыке, который необходимо было описать вводной части, либо на конкретном.
Также матрица смежностей и списки смежностей представлены в виде массива, если их можно представить в «без массивных» языках, то и массив смежностей тоже можно представить.

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

А как насчёт абстракции от способа хранения? Например, делаем функцию, которая по идентификаторам вершин возвращает значение ячейки матрицы смежности.

2) Если исключить код и примеры, то по BFS можно сказать от силы с десяток предложений. Неинтересно же. К тому же эта статья и так довольно объёмная.
1) Все применимо к массиву смежностей :). От того, что в названии метода, присутствует слово «массив», не следует, что необходим для хранения именно массив как тип данных

2) Поиск в ширину лучше рассматривать с поиском в глубину… Рассказать, чем отличаются и чем обуславливается выбор конкретного алгоритма.
Матрица изначально все же математическая абстракция. Не стоит из-за некоторых языков не включать такую серьезную вещь.
Кстати, ищу книжку с «классическими» задачами дискретной математики, например, задача о коммивояжере. Уважаемое хабрасообщество не порекомендует какую-нибудь?
Асанов М.О., Баранский В.А., Расин В.В. — Дискретная математика: графы, матроиды, алгоритмы
Я бы порекомендовал Окулова
Прочитал всего. Там начинается с «длиной арифметики», а потом графы, коммивояжер, и максимальный поток, венгерский алгоритм (в качестве задачки)… Много интересных задач. И книжка всего на 300 страниц. =)
Просмотрел содержание — хорошая, годная книжка. Спасибо.
Графы также используются в телекоммуникациях, а именно в теории сетей, например. Ими очень удобно описывать структуру сети и решать сопутствующие задачи.
хм…
а как ЕЩЁ можно описать структуру сети, без графов?
Мне очень понравилось давно хотел с граффами окончательно разобраться! Спасибо
Здорово, что кто-то решился написать об этом :)

Правда, мне кажется, в «вводной» статье Вы упустили достаточно важный момент — возможность существования весов у ребер. Без этого, например, задача о поиске кратчайшего пути кажется не такой интересной :)
Не так давно была чудеснейшая статья об алгоритме Дейкстры… Было бы хорошо дать линк на нее, ибо это было бы неплохим примером с замечательными иллюстрациями :)
Я прошу простить, ответил не туда, куда хотел :)
спасибо
как раз искал способ построения коротких путей на карте по опр.точкам
А про матрицу инцидентности что же не написали? В некоторых алгоритмах она тоже используется.
Ну и не забывайте, что в ориентированных графах не ребра, а дуги (arcs). ;)
Вот почему, в универе это все так напрягало и казалось сложным. А сейчас просто на досуге интересно читать?
препод хреновый?
или учёба только в ночь перед сессией…
И то, и другое.
Усваивал уже когда понадобилось для работы, термины многие не помню — но представляю, как работает и для чего нужно.

Я вобще к тому, что с каждым годом все интереснее учится — когда не заставляет никто и не подгоняет, но на это все меньше свободного времени.
Да и просто материала тонны в интернете стало, видео, лекции, статьи — на высоком уровне.
только хотел написать об это
те кому нужно еще в универе это усвоили и использовали, а остальным и сейчас не нужно:)
я пока только рабираюсь с основами алгоритмов, поэтому оч простой вопрос: а матрица смежности заполняется тоже по какому-то алгоритму или вручную, т е вижу связь — заношу «1» не вижу -«0»?
за материал, спасибо-)
Only those users with full accounts are able to leave comments. Log in, please.