Графы
ArslanВсем привет, Никита совсем разленился и поэтому эту статью написал я. В этой статье описана моя любимая тема: графы, задачи по которой есть почти на каждой олимпиаде по уровню выше муниципальной. В отличие от сортировки или кучи в c++ нет встроенной реализации графов (или есть, но очень кривое и неудобное), поэтому придется писать все вручную.
Давайте узнаем что такое граф
Граф - абстрактный математический объект, представляющий собой множество вершин графа и набор рёбер, то есть соединений между парами вершин. (с) wikipedia.org
Проще что такое граф можно понять, если посмотреть на картинку:
Кружочки с цифрами - вершины(узлы), линии между ними - ребра.
С помощью графов можно представить, например, сеть воздушных перелетов, где вершины - аэропорты, а ребра - маршруты самолетов.
Добавим немного важной теории
• Ребра в графе бывают ориентированными и неориентированными.
Ориентированные ребра как односторонние дороги, т.е. по ним можно двигаться только в одну сторону, в то время как по неориентированным в обе.
• Графы бывают циклическими и ациклическими.
Граф называется циклическим если в нем есть вершина, "выйдя" из которой можно по ненулевому множеству вершин "прийти" обратно не "проходя" по одному и тому же ребру более одного раза, иначе он называется ациклическим.
• Полным графом называется граф, в котором из каждой вершины есть ребро в любую другую вершину этого графа
• Граф может быть взвешенным и не взвешенным.
Граф называется взвешенным, если у его ребер известен вес.
Вес у ребра может означать абсолютно разные вещи: стоимость билета, если граф - карта метро, или длительность поездки, если это карта дорог.
Самые популярные способы хранения графов
Для начала стоит заметить, что чаще мы хотим узнать у графа 2 вещи: "есть ли ребро из a в b?" и "узнать всех соседей вершины a?"
Традиционно количество вершин и ребер обозначают n(v) и m(e) соответственно
Матрица смежности - метод, при котором граф представляется квадратной таблицей n*n где в поле graph[a][b] стоит "1", если есть ребро из вершины a в вершину b, и "0", если ребра нет.
O(1) - есть ли ребро между a и b
O(n) - все соседи вершины a
память - O(n^2)
Список ребер - метод, при котором граф хранится в виде вектора, в i-той ячейке которого хранится два числа: откуда и куда ведет i-тое ребро.
O(m) - есть ли ребро между a и b
O(m) - все соседи вершины a
память - O(m)
Этот способ не особо эффективен, т.к. зачастую m >= n и все работает ужасно долго. Но этот способ используется в нескольких нужных алгоритмах, про которые я, возможно, расскажу позже(нет).
Список смежности - метод, при котором для каждой вершины хранятся все ее соседи.
(количество соседей) - есть ли ребро между a и b
(количество соседей) - все соседи вершины a
память - O(m)
Надеюсь со способами хранения все понятно, если нет, то мне вас жаль.
Базовые алгоритмы(1)
DFS - Depth-First Search - Поиск в глубину
Наверное, самый известный и используемый алгоритм во всей теории графов.
Цель алгоритма - пройтись по всем вершинам графа, доступных из начальной(стартовой) вершины.
Как он работает:
- Если мы находимся в вершине, идем в любого ее соседа, в котором мы еще не были.
- Если мы были во всех соседях вершины, или соседей нет, то возвращаемся в вершину, из которой пришли в данную вершину.
- Если мы были во всех соседях начальной вершины, то завершаем программу.
Реализуется это все очень легко и просто рекурсией.
P.S. Может быть потом я напишу больше алгоритмов, но нет, не сейчас.