Пользователь
0,0
рейтинг
25 июля 2009 в 17:18

Разработка → Алгоритмы на графах — Часть 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 — записки программиста"

______________________
Текст подготовлен в Хабра Редакторе
xpic99 @xpic99
карма
77,9
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

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

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

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

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