Статьи

Алгоритм недели: минимальное остовное дерево Прима

Октябрь 29, 2018

Вступление

Наряду с алгоритмом минимального связующего дерева Крускала есть еще один общий алгоритм, который решает проблему. Алгоритм Прим.

Как мы уже знаем, алгоритм Крускала работает довольно естественным и логичным образом. Поскольку мы пытаемся построить MST, который естественным образом строится по минимальным ребрам графа (G), мы сортируем их в не убывающем порядке и начинаем строить дерево.

Алгоритм Крускала

В течение всего процесса построения конечного минимального остовного дерева алгоритм Крускала сохраняет лес деревьев. Количество деревьев в этом лесу уменьшается с каждым шагом, и, наконец, мы получаем минимальный вес связующего дерева.

Ключевым моментом в подходе Крускала является способ получения «следующего» ребра от G, который должен быть добавлен к одному из деревьев леса (или соединить два дерева из леса). Единственное, о чем мы должны знать, — это выбрать ребро, соединяющее две вершины — u и v, и эти две не должны быть в одном дереве. Вот и все.

Хитрая часть Крускала

Важной особенностью алгоритма Крускала является то, что он строит MST, просто сортируя ребра по их весу и не заботясь о конкретной начальной вершине.

В то же время есть еще один алгоритм, который строит MST — алгоритм Прима, разработанный Робертом Примом в 1957 году.

обзор

Идея алгоритма Прима несколько отличается от подхода Крускала. В процессе построения MST этот алгоритм сохраняет одно дерево, которое в конечном итоге является поддеревом конечного минимального веса связующего дерева.

Прим подход

На каждом шаге мы выбирали ребро, которое добавляли к растущему дереву, которое в итоге формирует MST.

Это как-то неестественный подход! Мы начинаем с данной вершины и изначально не выбираем самое светлое ребро. Таким образом, в течение всего процесса дерево растет, но вне дерева (T) могут быть ребра, которые светлее, чем у дерева (т. Е. Ребро (5, 1) от дерева выше, чем (2, 5), но (2, 5) добавляется к растущему дереву до края (5, 1)).

По сравнению с алгоритмом Крускала на этот раз все кажется действительно неестественным. Как мы должны быть уверены, что конечное дерево (T) будет минимальным остовным деревом, так как мы не получаем самое светлое ребро на каждом шаге?

На самом деле мы уверены, что конечное дерево является MST из-за еще одной очевидной особенности минимальных остовных деревьев. Они должны «соединить» все вершины G, таким образом, как минимум одно ребро, достигающее каждой вершины, появится в MST. Таким образом, нас не должно волновать, с чего начать, единственная важная вещь — это выбрать самый легкий край, который виден до сих пор.

Этот алгоритм очень похож на кратчайший путь Дейкстры в графе , потому что мы начинаем с вершины, помещаем все ребра, начиная с этого узла, в очередь с приоритетами и выбираем самое светлое ребро. Переходя к следующему узлу, связанному с этим ребром, мы добавляем в очередь все ребра, которых нет в очереди.

Очередь Прима

Таким образом, очередь растет, и мы всегда получаем самое светлое преимущество — таким образом, формируем приоритетную очередь.

Теперь давайте подведем итог алгоритму Prim

Псевдокод

В качестве начального входа мы имеем граф (G) и начальную вершину (и).

1.  Make a queue (Q) with all the vertices of G (V);
2.  For each member of Q set the priority to INFINITY;
3.  Only for the starting vertex (s) set the priority to 0;
4.  The parent of (s) should be NULL;
5.  While Q isn’t empty
6.     Get the minimum from Q – let’s say (u); (priority queue);
7.     For each adjacent vertex to (v) to (u)
8.        If (v) is in Q and weight of (u, v) < priority of (v) then
9.           The parent of (v) is set to be (u)
10.          The priority of (v) is the weight of (u, v)

На самом деле это очень похоже на алгоритм Дейкстры.

Код

Вот PHP- реализация алгоритма Prim, которая следует непосредственно за псевдокодом.

// Prim's algorithm
 
define('INFINITY', 100000000);
 
// the graph
$G = array(
    0 => array( 0,  4,  0,  0,  0,  0,  0,  0,  8),
    1 => array( 4,  0,  8,  0,  0,  0,  0,  0,  11),
    2 => array( 0,  8,  0,  7,  0,  4,  2,  0,  0),
    3 => array( 0,  0,  7,  0,  9,  14,  0,  0,  0),
    4 => array( 0,  0,  0,  9,  0,  10,  0,  0,  0),
    5 => array( 0,  0,  4,  14,  10,  0,  0,  2,  0),
    6 => array( 0,  0,  2,  0,  0,  0,  0,  6,  7),
    7 => array( 0,  0,  0,  0,  0,  2,  6,  0,  1),
    8 => array( 8,  11,  0,  0,  0,  0,  7,  1,  0),
);
 
function prim(&$graph, $start)
{
    $q = array(); // queue
    $p = array(); // parent
 
    foreach (array_keys($graph) as $k) {
        $q[$k] = INFINITY;
    }
 
    $q[$start] = 0;
    $p[$start] = NULL;
 
    asort($q);
 
    while ($q) {
        // get the minimum value
        $keys = array_keys($q);
        $u = $keys[0];
 
        foreach ($graph[$u] as $v => $weight) {
            if ($weight > 0 && in_array($v, $keys) && $weight < $q[$v]) {
                $p[$v] = $u;
                $q[$v] = $weight;
            }
        }
 
        unset($q[$u]);
        asort($q);
    }
 
    return $p;
}
 
prim($G, 5);

история

Любопытно сказать, что алгоритм, разработанный Робертом Примом, им не разработан. Считается, что чешский математик Войтех Ярник открыл еще в 1930 году. Однако теперь мы знаем этот алгоритм как алгоритм Прима, который независимо обнаружил его в 1957 году, как я уже говорил выше, и, наконец, Эдсгер Дейкстра описал его в 1959 году. Вот почему его алгоритм на поиск кратчайших путей из одного источника в графе очень похож на этот алгоритм. Возможно, найдя этот алгоритм на минимальном остовном дереве, Дейкстра обнаружил, как мы можем найти кратчайшие пути ко всем вершинам, используя очередь с приоритетами. Действительно, пути ко всем остальным вершинам используют ребра минимального остовного дерева.

Просто потому, что Ярник нашел и описал этот алгоритм на 27 лет раньше, чем Роберт Прим, сегодня более удобно называть этот алгоритм алгоритмом Прима-Ярника.

49
Share: