Алгоритмы на графах — Часть 0: Базовые понятия

    Вступление


    Как оказалось тема алгоритмов интересна Хабра-сообществу. Поэтому я как и обещал, начну серию обзоров «классических» алгоритмов на графах.
    Так как публика на Хабре разная, а тема интересна многим, я должен начать с нулевой части. В этой части я расскажу что такое граф, как он представлен в компьютере и зачем он используется. Заранее прошу прощения у тех кто это все уже прекрасно знает, но для того чтобы объяснять алгоритмы на графах, нужно сначала объяснить что такое граф. Без этого никак.


    Основы


    В математике, Граф — это абстрактное представление множества объектов и связей между ними. Графом называют пару (V, E) где V это множество вершин, а E множество пар, каждая из которых представляет собой связь (эти пары называют рёбрами).
    Граф может быть ориентированным или неориентированным. В ориентированном графе, связи являются направленными (то есть пары в E являются упорядоченными, например пары (a, b) и (b, a) это две разные связи). В свою очередь в неориентированном графе, связи ненаправленные, и поэтому если существует связь (a, b) то значит что существует связь (b, a).

    Рис. 1

    Пример:
    Неориентированный граф: Соседство (в жизни). Если (1) сосед (3), то (3) сосед (1). См рис. 1.а

    Ориентированный граф: Ссылки. Сайт (1) может ссылаться на сайт (3), но совсем не обязательно (хотя возможно) что сайт (3) ссылается сайт (1). См рис. 1.б


    Степень вершины может быть входящая и исходящая (для неориентированных графов входящая степень равна исходящей).
    Входящая степень вершины v это количество ребер вида (i, v), то есть количество ребер которые «входят» в v.
    Исходящая степень вершины v это количество ребер вида (v , i), то есть количество ребер которые «выходят» из v.
    Это не совсем формальное определение (более формально определение через инцидентность), но оно вполне отражает суть

    Путь в графе это конечная последовательность вершин, в которой каждые две вершины идущие подряд соединены ребром. Путь может быть ориентированным или неориентированным в зависимости от графа. На рис 1.а, путем является например последовательность [(1), (4), (5)] на рис 1.б, [(1), (3), (4), (5)].

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

    Представление графов


    Существует два способа представления графа, в виде списков смежности и в виде матрицы смежности. Оба способа подходят для представления ориентированных и неориентированных графов.

    Матрица смежности
    Этот способ является удобным для представления плотных графов, в которых количество рёбер (|E|) примерно равно количеству вершин в квадрате (|V|2).
    В данном представлении мы заполняем матрицу размером |V| x |V| следущим образом:
    A[i][j] = 1 (Если существует ребро из i в j)
    A[i][j] = 0 (Иначе)
    Данный способ подходит для ориентированных и неориентированных графов. Для неориентированных графов матрица A является симметричной (то есть A[i][j] == A[j][i], т.к. если существует ребро между i и j, то оно является и ребром из i в j, и ребром из j в i). Благодаря этому свойству можно сократить почти в два раза использование памяти, храня элементы только в верхней части матрицы, над главной диагональю)
    Понятно что с помощью данного способа представления, можно быстро проверить есть ли ребро между вершинами v и u, просто посмотрев в ячейку A[v][u].
    С другой стороны этот способ очень громоздкий, так как требует O (|V|2) памяти для хранения матрицы.

    Рис. 2
    На рис. 2 приведены представления графов из рис. 1 с помощью матриц смежности.

    Списки смежности
    Данный способ представления больше подходит для разреженных графов, то есть графов у которых количество рёбер гораздо меньше чем количество вершин в квадрате (|E| << |V|2).
    В данном представлении используется массив Adj содержащий |V| списков. В каждом списке Adj[v] содержатся все вершины u, так что между v и u есть ребро. Память требуемая для представления равна O (|E| + |V|) что является лучшим показателем чем матрица смежности для разреженных графов.
    Главный недостаток этого способа представления в том, что нет быстрого способа проверить существует ли ребро (u, v).


    Рис. 3
    На рис. 3 приведены представления графов из рис. 1 с помощью списков смежности.

    Применение

    Те кто дочитал до этого места, наверное задали себе вопрос, а где же собственно я смогу применить графы. Как я и обещал я буду стараться приводить примеры. Самый первый пример который приходит в голову это социальная сеть. Вершинами графа являются люди, а ребрами отношения (дружба). Граф может быть неориентированным, то есть я могу дружить только с теми кто дружит со мной. Либо ориентированным (как например в ЖЖ), где можно добавить человека в друзья, без того чтобы он добавлял вас. Если же он да добавит вас вы будете «взаимными друзьями». То есть будет существовать два ребра: (Он, Вы) и (Вы, Он)
    Ещё одно из применений графа, которое я уже упоминал это ссылки с сайта на сайт. Представим Вы хотите сделать поисковую систему и хотите учесть на какие сайты есть больше ссылок (например сайт A), при этом учитывать сколько сайтов ссылается на сайт B, который ссылается на сайт A. У вас будет матрица смежности этих ссылок. Вы захотите ввести какую то систему подсчёта рейтинга, которая делает какие то подсчёты на этой матрице, ну, а дальше… это Google (точнее PageRank) =)

    Заключение

    Это небольшая часть теории которая понадобится нам чтобы для следующих частей. Надеюсь вам было понятно, а главное понравилось и заинтересовало читать дальнейшие части! Оставляйте свои отзывы и пожелания в комментариях.

    В следующей части

    BFS — Алгоритм поиска в ширину

    Библиография

    Кормен, Лайзерсон, Риверст, Штайн — Алгоритмы. Построение и анализ. Издательство Вильямс, 2007.
    Словарь терминов теории графов
    Граф — статья в английской Википедии

    Статья это кросс-пост из моего блога — "Programing as is — записки программиста"

    ______________________
    Текст подготовлен в Хабра Редакторе
    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

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

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

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

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

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

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

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

                          Но согласитесь, что в статье для широкой аудитории определение из статьи будет наиболее понятно и достаточно математически корректно)
                          • НЛО прилетело и опубликовало эту надпись здесь
                            • 0
                              Вот самое правильное определение. :)
                              И все-таки оно не достаточно корректно, так как из него не очень понятно (читай совсем непонятно) как соотносятся элементы из V с элементами из E
                              хотя в жизни все конечно пишут просто (V,E) а не (V,E,phi), ибо лень просто. phi держим в уме :)
                              А по жизни скорее бинарные отношения любят представлять в виде графа, а не наоборот.
                              • 0
                                оно = определение из статьи. зарапортовался, простите.
                              • +1
                                Первое определение может и не очень четкое, но как-то больше располагает неподготовленного читателя.
                                • НЛО прилетело и опубликовало эту надпись здесь
                                  • 0
                                    Из такого определения напрочь выпадает специфика графа.
                                  • +7
                                    Не упомянуты основы:

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

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

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

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

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

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

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

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

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

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

                                                                      Я вобще к тому, что с каждым годом все интереснее учится — когда не заставляет никто и не подгоняет, но на это все меньше свободного времени.
                                                                      Да и просто материала тонны в интернете стало, видео, лекции, статьи — на высоком уровне.
                                                                    • 0
                                                                      только хотел написать об это
                                                                      те кому нужно еще в универе это усвоили и использовали, а остальным и сейчас не нужно:)
                                                                    • 0
                                                                      я пока только рабираюсь с основами алгоритмов, поэтому оч простой вопрос: а матрица смежности заполняется тоже по какому-то алгоритму или вручную, т е вижу связь — заношу «1» не вижу -«0»?
                                                                      за материал, спасибо-)

                                                                      Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.