Описание алгоритма - Gentser/Graph_Bridges GitHub Wiki

Алгоритм поиска мостов. Для каждой вершины vϵV определим множество P(v). P(v) = {v} U {w : (w = предок(v)) & (∃ x∈V: ((x = v) ∪ (x=потомок(v))) & (<x, w> ∈ B))}, где B - множество обратных рёбер (хорд). Иными словами, P (v) состоит из v и всех предков вершины v, которых можно достичь из v, пройдя сначала несколько (возможно, ни одной) дуг дерева T, а затем одно обратное ребро и остановившись. Таким образом после построения дерева DFS и нахождения всех обратных ребер, будет вычислена функция P(v) для каждой вершины дерева. После вычисления P(v), для каждой вершины будет найдена Low(v) = min { numVert(x) | x ∈ P(v) }. То есть эта функция, которая определяет наименьший номер вершины, который был получен функцией P(v) для этой вершины. Далее необходимо для каждого ребра {v,w} дерева проверить соотношение Low(w)>=NumVert(w)). И если это условие выполнено, то это ребро и есть мост.