Алгоритм двух китайцев

НЯ! Эта статья полна любви и обожания. Возможно, стоит добавить ещё больше?

Алгоритм двух китайцев — алгоритм построения минимального остовного дерева во взвешенном ориентированном графе с корнем в заданной вершине. Был разработан математиками Чу Йонджином и Лю Цзенхонгом.

Постановка задачи

Дан взвешенный ориентированный граф [math]G(V, E)[/math] и начальная вершина [math]v[/math]. Требуется построить корневое остовное дерево в [math]G[/math] с корнем в вершине [math]v[/math], сумма весов всех ребер которого минимальна.

Алгоритм

Описание

Если хотя бы одна вершина графа [math]G[/math] недостижима из [math]v[/math], то требуемое дерево построить нельзя.

Для каждой вершины [math]u \ne v[/math] графа [math]G[/math] произведём следующую операцию: найдём ребро минимального веса, входящее в [math]u[/math], и вычтем вес этого ребра из весов всех рёбер, входящих в [math]u[/math]. [math]m(u) = \min \limits_{tu \in E}w(tu), w'(tu) = w(tu) - m(u)[/math]. Строим граф [math]K = (V,K_0)[/math], где [math]K_0[/math] — множество рёбер нулевого веса графа [math]G[/math] c весовой функцией [math]w'[/math]. Если в этом графе найдётся остовное дерево с корнем в [math]v[/math], то оно и будет искомым. Если такого дерева нет, то построим граф [math]C[/math] — конденсацию графа [math]K[/math]. Пусть [math]y[/math] и [math]z[/math] — две вершины графа [math]C[/math], отвечающие компонентам сильной связности [math]Y[/math] и [math]Z[/math] графа [math]K[/math] соответственно. Положим вес ребра между вершинами [math]y[/math] и [math]z[/math] равным минимальному среди весов рёбер графа [math]G[/math] с весовой функцией [math]w'[/math], идущих из [math]Y[/math] в [math]Z[/math]. Продолжим с пункта 2, используя граф [math]C[/math] вместо [math]G[/math]. В [math]C[/math] построено MST [math]T[/math]. Построим теперь MST [math]T'[/math] в [math]G[/math] с весовой функцией [math]w'[/math]. Добавим к [math]T'[/math] все вершины компоненты сильной связности графа [math]K[/math], которой принадлежит [math]v[/math] (по путям нулевого веса из [math]v[/math]). Пусть в [math]T[/math] есть ребро [math]yz[/math], где [math]y[/math] отвечает компоненте сильной связности [math]Y[/math], а [math]z[/math] — компоненте сильной связности [math]Z[/math] графа [math]K[/math]. Между [math]Y[/math] и [math]Z[/math] в графе [math]G[/math] с весовой функцией [math]w'[/math] есть ребро [math]y'z'[/math], вес которого равен весу ребра [math]yz[/math]. Добавим это ребро к дереву [math]T'[/math]. Добавим к [math]T'[/math] все вершины компоненты [math]Z[/math] по путям нулевого веса из [math]z'[/math]. Сделаем так для каждого ребра дерева [math]T[/math]. Полученное дерево [math]T'[/math] — MST в графе [math]G[/math].

Пример

Исходный граф.
Произведем спуск до нулевых ребер (Фаза 1, 2).
По нулевым ребрам нельзя дойти до всех вершин из [math]v[/math], поэтому строим конденсацию и добавляем наименьшие ребра между компонентами (Фаза 3). Найдем [math]MST[/math] для данного графа.
Произведем спуск до нулевых ребер (Фаза 1, 2).
По нулевым ребрам нельзя дойти до всех вершин из [math]v[/math], поэтому строим конденсацию и добавляем наименьшие ребра между компонентами (Фаза 3). Найдем [math]MST[/math] для данного графа.
Произведем спуск до нулевых ребер (Фаза 1, 2). По полученным нулевым ребрам можно дойти из корня до всех вершин. Тогда запускаем [math]dfs[/math] из корня и возвращаем ребра.
Находим корень в каждой из компонент, из каждого такого корня запускаем [math]dfs[/math] по нулевым ребрам, возвращаем результат.
Находим корень в каждой из компонент, из каждого такого корня запускаем [math]dfs[/math] по нулевым ребрам. Полученое дерево и есть [math]MST[/math] в исходном графе.

Корректность

Замечания:

• После перевзвешивания в каждую вершину кроме [math]v[/math] входит по крайней мере одно ребро нулевого веса.
  
• Пусть [math]T[/math] — искомое дерево в [math]G[/math] с весовой функцией [math]w[/math]. [math]w'(T) = w(T) - \sum \limits_{u \in V \setminus v}m(u)[/math], т.е. [math]T[/math] - MST в [math]G[/math] с весовой функцией [math]w[/math] тогда и только тогда, когда [math]T[/math] — MST в [math]G[/math] с весовой функцией [math]w'[/math].
  

Лемма:

Кратчайшее дерево путей [math]T'[/math] в графе [math]G[/math] можно получить, найдя кратчайшее дерево путей [math]T[/math] в графе [math]C[/math], а затем заменив в нем каждую компоненту сильной связности деревом, построенным из дуг нулевой длинны.

Доказательство:

[math]\triangleright[/math]

Зафиксируем любое дерево путей и покажем, что в графе [math]G[/math] найдется дерево не большей длины, имеющее такую структуру, как сказано в лемме. Для такой структуры дерева необходимо и достаточно, чтобы в каждое из подмножеств входило только по одному ребру. Меньше быть не может, иначе получится отдельная компонента связности. Если же в какое-то подмножество входит больше чем одно ребро, то все ребра кроме одного можно заменить ребрами нулевой длины, лежащими внутри подмножества, что разве лишь уменьшит длину дерева и не нарушит связности. Повторяя это преобразование нужное число раз мы добьемся искомой структуры дерева.

[math]\triangleleft[/math]

Из сделанных замечаний и леммы следует, что дерево [math]T'[/math] — MST в [math]G[/math].

Реализация

Обозначения:

• Граф хранится в виде множества ребер + индекс корня.
• Множество ребер - список смежности.
• Ребро - структура {from, to, weight}.
• root - текущий корень.

Особенность реализации: алгоритму не важна кратность ребер, поэтому при составлении нового графа кратные ребра могут появиться - это уменьшает асимптотику с [math]O(V^2)[/math] до [math]O(E)[/math]

Проверяем, можно ли дойти из [math]v[/math] до остальных вершин. Если можно - запускаем findMST.

int findMST(edges, n, root):
   int result = 0
   int minEdge[n] // создаем массив минимумов, входящих в каждую компоненту, инициализируем бесконечностью.
   for each [math]e \in E[/math]
       minEdge[e.to] = min(e.w, minEdge[e.to])
   for each [math]v \in V \backslash \{root\}[/math]
       res += minEdge[v] //веса минимальных ребер точно будут в результате
   edge zeroEdges[] //создаем массив нулевых ребер
   for each [math]e \in E[/math]
       if e.w == minEdge[e.to]
           zeroEdges.pushback([math]e_1[/math]) // [math]e_1[/math] - ребро е, уменьшенное на минимальный вес, входящий в e.to
   if dfs(root, zeroEdges) // проверяем, можно ли дойти до всех вершин по нулевым ребрам
       return res
   int newComponents[n] // будущие компоненты связности
   newComponents = Сondensation(zeroEdges) 
   edge newEdges[] //создаем массив ребер в новом графе с вершинами в полученных компонентах
   for each [math]e \in[/math] zeroEdges
       if e.to и e.from в разных компонентах
           добавляем в newEdges ребро с концами в данных компонентах и весом e.w
   res += findMST(zeroEdges, ComponentsCount, newComponents[root])
   return res

Сложность

Всего будет построено не более [math]V[/math] конденсаций. Конденсацию можно построить за [math]O(E)[/math]. Значит, алгоритм можно реализовать за [math]O(VE)[/math].

Источники

• Романовский И. В. Дискретный анализ, 3-е изд., перераб. и доп. - СПб.:Невский Диалект; БХВ-Петербург, 2003. - 320 с.: ил. - ISBN 5-7940-0114-3
• http://is.ifmo.ru