алгоритмы на графах: примечание 1 к основам графов
algorithms-on-graphs
Эта статья представляет собой заметку об изучении алгоритмов на графах.
Представление диаграммы
матрица смежности
список смежности
реберно-связанный список
Различные представления определяют временную сложность различных операций.
Обход графа
Вопрос: Как найти все вершины, которых может достичь A?
Описание алгоритма:
Приведенный выше алгоритм также должен решить две проблемы:
- Как отслеживать, какие ребра/вершины были посещены?
- В каком порядке посещаются вновь добавленные вершины?
Мы можем использовать карту, чтобы записать, были ли посещены вершины, а для новых добавленных вершин мы пробуем схему поиска в глубину и продолжаем посещать.
DFS
Если мы хотим посетить все точки на графике, метод следующий:
Previsit and Postvisit Functions
Когда мы находимся в узле исследования, добавляем функции Previsit и Postvisit:
В соответствии с этой функцией мы можем реализовать часы:
возможность подключения
проблема
Мы можем сделать это, изменив DFS
Направленные ациклические графы
определение:
A source is a vertex with no incoming edges.
A sink is a vertex with no outgoing edges.
Теперь наша цель найти Linear Ordering, что такое Linear Ordering, посмотрите на рисунок ниже:
Как его найти? Согласно концепции раковины, мы сначала идем к раковине
Весь процесс выглядит следующим образом:
- Find sink.
- Put at end of order.
- Remove from graph.
- Repeat.
Весь алгоритм следующий:
В частности, сначала нужно получить доступ к графику в соответствии с DFS, а затем отсортировать его в соответствии с часами Postvisit от большего к меньшему, что является значением, которое нам нужно задать.
Потому что DFS всегда проходит весь путь до самой глубокой точки, то есть сначала находит узел, чей сток равен 0.
Strongly Connected Components
В неориентированных графах есть связность, но в ориентированных графах она будет сложнее.
определение
В ориентированном графе связность означает, что точки в наборе могут достигать друг друга, и при их объединении это выглядит так:
Он называется метаграфом и также является DAG.
Ниже мы опишем, как рассчитать SCC (сильно связанные компоненты).
Расчет SCC
простой алгоритм
Другая идея состоит в том, чтобы найти агрегированный приемник так же, как найти узел приемника.
, а как его найти?
В неориентированном графе мы сортируем postOrder, а маленький postOrder является стоком.В ориентированном графе у нас есть следующая теория:
Таким образом, источник с большим postOrder является источником, но нам нужен приемник, поэтому мы можем сделать следующее:
Теперь мы начинаем давать конкретный алгоритм.
Базовый алгоритм
Приведенный выше подход заключается в непрерывном обходе DFS, а затем поиске наибольшей вершины postOrder, поиске всех точек, до которых можно добраться из него, удалении ее и повторении.
Ниже приведен улучшенный алгоритм без dfs каждый раз:
Суммировать
Эта статья представляет собой запись 1-2-недельного курса «Алгоритмы на графиках», примечания предназначены скорее для быстрого ознакомления при просмотре.
Ваша поддержка является движущей силой для меня, чтобы продолжать писать, и я с нетерпением жду нашего общего прогресса.