|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Sergey Radkevitch 2:5020/400 21 May 2001 20:16:55
To : All
Subject : Минимальное остовное дерево
--------------------------------------------------------------------------------
на каждом этапе выбираем дугу с минимальным весом весом, из тех дуг, которые
не создают циклов.
=========================================================
Алгоритм Краскала:
Hа деле этот алгорит работает так:
Функция получает в качестве параметра массив всех дуг в графе. Считается,
что если вес дуги == 0, то ее просто не существует ;) Это значение можно
заменить, например, на -1 или другое число - на алгоритм это не влияет.
1. Сортируем дуги графа по возрастанию весов от меньшего к большему.
2. Для каждой вершины определяем к какому из "connection components" от
относится. Hа первом этапе каждая вершина - своя компонента.
3. Для каждой дуги по порядку:
Если ее концы i и j находятся в разных компонентах связности (так это
переводится?), то эти компоненты объединяются в одну, а рассматриваемая дуга
добавляется в минимальное покрывающее дерево.
Если ее концы i и j находятся в одной компоненте связности - пропускаем
дугу, она не попадет в покрывающее дерево.
4. Алгоритм завершает при по завершении прохода по всем дугам или по
достижении момента, когда все компоненты связности уже объеденены в одну.
struct edge {
int i, j, weight;
};
// for qsort
int compare_function(const void *p1, const void *p2) {
return ((const edge *)(p1))->weight - ((const edge
*)(p2))->weight;
}
int find_minimum_spawning_tree(edge *edges, int n_vertices, int n_edges)
{
int weight = 0;
// sorting the edges
qsort(edges, n_edges, sizeof(edge), compare_function);
// connection components, initializing
// for each vertex says his connection component
int *vertices = new int [n_vertices];
for(int i=0;i<n_vertices;i++) vertices[i] = i;
for(int i=0;i<n_edges;i++) {
// two connection componets ...
int comp1 = vertices[edges[i].i], comp2 = vertices[edges[i].j];
if (comp1 != comp2) {
// union two connection components
for(int k=0;k<n_vertices;k++)
if(vertices[k] == comp2) vertices[k] = comp1;
weight += edges[i].weight;
}
else edges[i].weight = 0; // skipping edge
}
delete [] vertices;
return weight;
}
void main()
{
// do something
// starting ...
int total = find_minimum_spawning_tree(graf_edges, n_vertices, n_edges);
// do something
}
Именно сортировка ребер и дает O(|E|log|E|), а сам алгоритмКраскала проходит
один раз по всему множеству ребер,т.е. дает O(|E|).
=========================================================
Алгоритм Прайма
он немного сложнее для реализации
1. Hа начальном этапе мы делим все множество вершин на две части S1 и S2,
так что все вершины V = S1 + S2. Способ разделения на начальном этапе
простейший - выбираем случайным образом одну вершину v1 и получаем
S1={v1}, S2={все остальные вершины}.
2. Hа каждом шаге алгоритма находим дугу e=(Vx, Vy) с минимальным весом,
выходящую из S1 в S2 (Vx в S1, Vy в S2), и заносим ее в минимальное
покрывающее дерево:
MinTree += e;
А также обновляем значения S1 и S2:
S1 += Vy;
S2 -= Vy;
Этот алгоритм будет работать быстрее Kruskal только при одном условии -
массив дуг E должен быть реализован в виде heap.
3. Алгоритм завершается, когда все вершины переходят в S1.
Трудность заключается в поиске дуги с min весом, именно выходящей из S1
в S2 и именно для облегчения этой задачи нужен heap.
=========================================================
И у Краскала и у Прима сложность была O(|E|log|E|), где |E| -
число дуг в графе.
--- ifmail v.2.15dev5
* Origin: MTU-Intel ISP (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
Минимальное остовное дерево 