Поиск мостов
Определение. Мостом называется ребро, при удалении которого связный неориентированный граф становится несвязным.
Пример задачи, где их интересно искать: дана топология сети (компьютеры и физические соединения между ними) и требуется установить все единые точки отказа — узлы и связи, без которых будут существовать два узла, между которыми не будет пути.
Наивный алгоритм поочередного удаления каждого ребра \((u, v)\) и проверки наличия пути \(u \leadsto v\) потребует \(O(m^2)\) операций. Чтобы научиться находить мосты быстрее, сначала сформулируем несколько утверждений, связанных с обходом в глубину.
Запустим DFS из произвольной вершины. Введем новые виды рёбер:
- Прямые рёбра — те, по которым были переходы в dfs.
- Обратные рёбра — то, по которым не было переходов в dfs.
Заметим, что никакое обратное ребро \((u, v)\) не может являться мостом: если его удалить, то всё равно будет существовать какой-то путь от \(u\) до \(v\), потому что подграф из прямых рёбер является связным деревом.
Значит, остается только проверить все прямые рёбра. Это уже немного лучше — такой алгоритм будет работать за \(O(n m)\).
Сооптимизировать его до линейного времени (до одного прохода dfs) поможет замечание о том, что обратные рёбра могут вести только «вверх» — к какому-то предку в дереве обхода графа, но не в другие «ветки» — иначе бы dfs увидел это ребро раньше, и оно было бы прямым, а не обратным.
Тогда, чтобы определить, является ли прямое ребро \(v \to u\) мостом, мы можем воспользоваться следующим критерием: глубина \(h_v\) вершины \(v\) меньше, чем минимальная глубина всех вершин, соединенных обратным ребром с какой-либо вершиной из поддерева \(u\).
Для ясности, обозначим эту величину как \(d_u\), которую можно считать во время обхода по следующей формуле\[ d_v = \min \begin h_v, &\\ d_u, &\text (v \to u) \text < прямое>\\ h_u, &\text (v \to u) \text < обратное>\end \]
const int maxn = 1e5; bool used[maxn]; int h[maxn], d[maxn]; void dfs(int v, int p = -1) used[u] = true; d[v] = h[v] = (p == -1 ? 0 : h[p] + 1); for (int u : g[v]) if (u != p) if (used[u]) // если ребро обратное d[v] = min(d[v], h[u]); else // если ребро прямое dfs(u, v); d[v] = min(d[v], d[u]); if (h[v] d[u]) // ребро (v, u) -- мост > > > > >
Примечание. Более известен алгоритм, вместо глубин вершин использующий их \(tin\), но автор считает его чуть более сложным для понимания.
Как найти мост в графе
Дан неориентированный граф. Найдите все мосты в нем.
Вход. Первая строка содержит два натуральных числа n и m – количество вершин и ребер графа соответственно ( n ≤ 2 * 10 4 , m ≤ 2 * 10 5 ). Следующие m строк содержат описание ребер по одному на строке. Ребро номер i задается двумя натуральными числами bi, ei (1 ≤ bi, ei ≤ n) – номерами вершин, которые оно соединяет.
Выход. Первая строка должна содержать количество мостов b в заданном графе. На следующей строке через пробел выведите b целых чисел – номера ребер, которые являются мостами, в возрастающем порядке. Ребра нумеруются с единицы в том порядке, в котором они поступают на вход.
Пример входа
Пример выхода
РЕШЕНИЕ
графы – мосты
Запустим поиск в глубину с расстановкой меток d[v] и up[v]. Из вершины v или её потомка есть обратное ребро в её предка тогда и только тогда, когда найдётся такой сын to, что up[to] < d[ v]. Если для некоторого ребра дерева ( v, to) выполняется равенство up[to] = d[ v], то в поддереве поиска с вершиной v найдется обратное ребро, приходящее точно в v. Если же up[ to] > d[v], то ребро (v, to) является мостом. Никакое обратное ребро мостом быть не может.
Граф, приведенный в примере, имеет следующий вид:
Поскольку количество вершин в графе велико, будем хранить граф в виде списка смежности graph . Массив used используется для отмечания уже пройденных вершин. Для решения задачи будем также использовать два дополнительных массива d и up. Во множестве Bridges будем собирать номера ребер, являющихся мостами. Для каждого входного ребра ( a, b) будем запоминать его номер в отображении mp.
vector < int >used, d, up;
Функция Edge возвращает ребро – пару вершин (a, b), где a < b.
pair < int , int >Edge( int a, int b)
Функция dfs реализует поиск в глубину. Расставляем метки d[v] и up[v]. Вершина p является предком v в дереве поиска.
void dfs ( int v, int p = -1)
int to = graph[v][i];
if (to == p) continue ;
up[v] = min (up[v], d[to]);
up[v] = min (up[v], up[to]);
if (up[to] > d[v]) Bridges.insert(mp[Edge(v,to)]);
Поиск мостов совершаем вызовом функции FindBridges.
void FindBridges( void )
for ( int i = 1; i
Основная часть программы. Читаем входной граф. Для каждого ребра (a, b) запоминаем его номер в отображении mp. Это нам нужно чтобы потом выводить мосты не как пары вершин, которые они соединяют, а как номера входных ребер.
Запускаем поиск мостов. Номера ребер – мостов заносим во множество Bridges.
Выводим количество мостов. В следующей строке выводим номера ребер – мостов в возрастающем порядке.
printf( «%d\n» ,Bridges.size());
for (iter = Bridges.begin(); iter != Bridges.end(); iter++)
Алгоритм Тарьяна поиска «мостов» в графе
Алгоритм Тарьяна [1] находит мосты в неориентированном графе за время [math]O(m)[/math] .
Пусть [math]T[/math] – дерево в одной из компонент связности графа [math]G.[/math]
Выберем корневую вершину и введём обозначения:
• [math]v-\gt w[/math] , если в дереве имеется [math]e=(v,w)[/math] , и вершина находится дальше от корня [math]r[/math] , чем вершина [math]v[/math] . Далее будем считать дерево [math]T[/math] направленным графом, содержащим рёбра указанного вида.
• [math]v=\gt w[/math] , если в ориентированном дереве [math]T[/math] имеется направленный путь от [math]v[/math] к [math]w[/math] .
• [math]v***w[/math] , если в графе [math]G[/math] существует ребро [math]e=(v,w)[/math] , не принадлежащее дереву [math]T[/math] .
• [math]N(v)[/math] – нумерация вершин в обратном порядке обхода вершин (post-order).
• [math]D(v)[/math] – количество потомков вершины [math]v[/math] в ориентированном дереве [math]T[/math] , то есть.
• [math]L(v) = \min S(v)[/math] , [math]H(v) = \max S(v)[/math] .
Алгоритм Тарьяна основан на следующем свойстве: ребро является мостом тогда и только тогда, когда [math]v-\gt w, H(w) \lt = N(w), L(w) \gt N(w) — D(w)[/math]
1.2 Математическое описание алгоритма
1. Для каждой компоненты связности графа найти какое-либо остовное дерево [math]T[/math] . 2. Перенумеровать вершины [math]T[/math] в порядке обратного обхода.
3. В порядке возрастания номера вершины выполнить следующие действия:
d. Пометить ребро [math]v \rightarrow w[/math] мостом, если [math]H(w)\lt =N(w)[/math] и [math]L(w)\gt N(w)-D(w)[/math] .
1.3 Вычислительное ядро алгоритма
1.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
1.6 Последовательная сложность алгоритма
Последовательная сложность алгоритма составляет [math]O(|E|)[/math] .
1.7 Информационный граф
1.8 Ресурс параллелизма алгоритма
Алгоритм Тарьяна может работать с любым остовным деревом, поэтому можно применить эффективно параллелизуемый поиск в ширину. Последующие вычисления также могут быть параллелизованы.
Параллельный алгоритм Тарьяна-Вишкина [2] основан на аналогичных вычислениях и может быть адаптирован для поиска мостов.
1.9 Входные и выходные данные алгоритма
1.10 Свойства алгоритма
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Возможные способы и особенности параллельной реализации алгоритма
2.3 Результаты прогонов
2.4 Выводы для классов архитектур
3 Литература
- ↑ Tarjan, R Endre. “A Note on Finding the Bridges of a Graph.” Information Processing Letters 2, no. 6 (April 1974): 160–61. doi:10.1016/0020-0190(74)90003-9.
- ↑ Tarjan, Robert Endre, and Uzi Vishkin. “An Efficient Parallel Biconnectivity Algorithm.” SIAM Journal on Computing 14, no. 4 (1985): 862–74.
- Уровень алгоритма
- Начатые статьи
Мосты и точки сочленения
Пусть дан неориентированный граф. Мостом называется такое ребро, удаление которого делает граф несвязным (или, точнее, увеличивает число компонент связности). Требуется найти все мосты в заданном графе.
Неформально, эта задача ставится следующим образом: требуется найти на карте такие дороги, при удалении которых пропадает путь между какими-либо двумя точками.
Суть алгоритма
Идея
Мы можем заметить тот факт, что ребро между точками v и u является мостом тогда и только тогда, когда из вершины u и её потомков нельзя вернуться в вершину v или подняться выше нее. Осталось лишь понять, как нам это выяснить.
Алгоритм
Разобьём ребра на ориентированные и будем хранить их в отдельной структуре. Пусть мы будем запоминать номер вершины, в которую направлено ребро, номер данного ребра (номер ребра равен номеру обратного ребра) и ссылку на его обратное ребро.
Заведём граф ссылок на рёбра и заполним его.
Запустим обход графа в глубину (DFS).
Будем для каждой вершины v хранить два значения:
- dp[v] — минимально возможная вершина в которую мы можем опуститься из этой вершины в процессе обхода в глубину (по умолчанию текущая глубина)
- d[v] — глубина текущей вершины
В процессе обхода:
- Если встречаем вершину u, в которой еще не были, то спускаемся в неё и тогда dp[v] = min(dp[v], dp[u]). Тем самым проверяем опустились ли мы из вершины u и её потомков выше v.
- Если встречаем вершину v, в которой уже были, то dp[v] = min(dp[v], d[u]). Тем самым проверяем не встретили ли мы вершину выше по обходу графа, чем вершина v.
По завершении обхода вершины v и её потомков:
Если из вершины v нельзя опуститься выше нее самой и мы знаем проверяемое ребро (dp[v] == d[v] && p != nullptr(текущее ребро)), то ребро из этой вершины — есть мост.
p->is_bridge = true — вершина v
p->bck->is_bridge = true — вершина другого конца ребра
Реализация
#include using namespace std; typedef long long ll; #define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL) struct Edge < ll v,num; bool is_bridge; Edge* bck; Edge()<>Edge(ll v, ll num):v(v),num(num)<> >; vector> gr; vector dp,d,bridges; vector used; void dfs(ll v, ll depth = 0, Edge* p = nullptr)< used[v] = true; dp[v] = d[v] = depth; for(auto u : gr[v])< if(!used[u->v])< dfs(u->v,depth+1,u); dp[v] = min(dp[v],dp[u->v]); > else if (p && p->num != u->num)< dp[v] = min(dp[v],d[u->v]); > > if(p != nullptr && dp[v] == d[v])< p->is_bridge = true; p->bck->is_bridge = true; bridges.push_back(p->num+1); > > int main()< fast_cin(); ll n,m; cin >> n >> m; gr.resize(n); dp.resize(n); d.resize(n); used.resize(n); ll v,u; for(ll i = 0;i < m;i++)< cin >> v >> u; v--; u--; Edge* a = new Edge(u,i); Edge* b = new Edge(v,i); a->bck = b; b->bck = a; gr[v].push_back(a); gr[u].push_back(b); > for(ll i = 0;i < n;i++) if(!used[i]) dfs(i); sort(bridges.begin(),bridges.end()); cout >Задачи по теме
Точки сочленения
Определение
Точкой сочленения называется вершина, удаление которой делает граф несвязным.
Суть алгоритма
Идея
Мы можем заметить два факта:
- Рассмотрим ребро между вершинами v и u. Тогда если из вершины u и ее потомков нельзя попасть в какого-либо предка вершины v и притом вершина v не является корнем дерева, то данная вершина и есть точка сочленения
- Если вершина v — корень дерева, то она является точкой сочленения тогда и только тогда, когда эта точка имеет более одного сына в обходе графа в глубину
Алгоритм
Заведем общий счетчик времени входа timer и два массива:
- tin[v] — время входа в вершину v
- fup[v] — минимально достижимая вершина из вершины v
Запустим обход графа в глубину (DFS).
В процессе обхода:
- Если встречаем уже посещенную вершину u, то fup[v] = min(fup[v], tin[u]). Проверяем не спустились ли мы выше v.
- Если встречаем не посещенную вершину v, то спускаемся в неё. Затем fup[v] = min(fup[v], fup[u]). Тем самым проверим не спустились ли мы выше v из вершины u и ее потомков. И наконец если из вершины u нельзя спуститься ниже вершины v и вершины v — не корень дерева обхода графа (v fup[u] >= tin[v] && p != -1), то вершина v и есть искомая точка сочленения. Добавляем 1 к количеству сыновей вершины v (children++)
По завершении обхода:
Если вершина v является корнем обхода графа в глубину и имеет более одного сына, то она также является точкой сочленения (p == -1 && children > 1)
Реализация
#include using namespace std; typedef long long ll; #define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL) ll timer = 0; vector> gr; vector tin,fup; set points_of_connectebility; vector used; void dfs(ll v,ll p = -1) < used[v] = true; tin[v] = fup[v] = timer++; ll children = 0; for(auto u : gr[v])< if(u == p)< continue; >if(used[u]) < fup[v] = min(fup[v],tin[u]); >else< dfs(u,v); fup[v] = min(fup[v],fup[u]); if(fup[u] >= tin[v] && p != -1) < points_of_connectebility.insert(v+1); >children++; > > if(p == -1 && children > 1) < points_of_connectebility.insert(v+1); >> int main() < fast_cin(); ll n, m; cin >> n >> m; gr.resize(n); tin.resize(n); fup.resize(n); used.resize(n); ll v, u; for (ll i = 0; i < m; i++) < cin >> v >> u; v--; u--; gr[v].push_back(u); gr[u].push_back(v); > for (ll i = 0; i < n; i++) if (!used[i]) dfs(i); cout >