Рубрики

Алгоритм минимального остовного дерева Крускала | Жадный Алго-2

Графы, Жадный алгоритм

Что такое минимальное остовное дерево?
Для связного и ненаправленного графа остовное дерево этого графа является подграфом, который является деревом и соединяет все вершины вместе. В одном графе может быть много разных связующих деревьев. Минимальное связующее дерево (MST) или минимальное весовое остовное дерево для взвешенного, связного и ненаправленного графа — это остовное дерево с весом, меньшим или равным весу любого другого остовного дерева. Вес остовного дерева — это сумма весов, присвоенных каждому ребру остовного дерева.

Сколько ребер у минимального остовного дерева?
Минимальное остовное дерево имеет (V — 1) ребер, где V — количество вершин в данном графе.

Каковы применения минимального связующего дерева?
Смотрите это для приложений MST.

Ниже приведены шаги для нахождения MST с использованием алгоритма Крускала

1. Sort all the edges in non-decreasing order of their weight.
2. Pick the smallest edge. Check if it forms a cycle with the spanning tree formed so far. If cycle is not formed, include this edge. Else, discard it.
3. Repeat step#2 until there are (V-1) edges in the spanning tree.

Шаг № 2 использует алгоритм Union-Find для обнаружения цикла. Поэтому мы рекомендуем прочитать следующий пост в качестве предварительного условия.
Союз-Найти Алгоритм | Набор 1 (определение цикла на графике)
Союз-Найти Алгоритм | Набор 2 (объединение по рангу и сжатию пути)

Алгоритм является жадным алгоритмом. Жадный выбор — выбрать наименьшее ребро веса, которое не вызывает цикл в MST, построенном до сих пор. Давайте разберемся с этим на примере: рассмотрим входной граф ниже.

Граф содержит 9 вершин и 14 ребер. Таким образом, минимальное сформированное связующее дерево будет иметь (9 — 1) = 8 ребер.

After sorting:
Weight   Src    Dest
1         7      6
2         8      2
2         6      5
4         0      1
4         2      5
6         8      6
7         2      3
7         7      8
8         0      7
8         1      2
9         3      4
10        5      4
11        1      7
14        3      5

Теперь выберите все ребра по одному из отсортированного списка ребер
1. Выберите край 7-6: цикл не сформирован, включите его.

2. Выберите край 8-2: цикл не сформирован, включите его.

3. Выберите край 6-5: цикл не сформирован, включите его.

4. Выберите край 0-1: цикл не сформирован, включите его.

5. Выберите край 2-5: цикл не сформирован, включите его.

6. Выберите край 8-6: Поскольку включение этого края приводит к циклу, откажитесь от него.

7. Выберите край 2-3: цикл не сформирован, включите его.

8. Выберите край 7-8: поскольку включение этого края приводит к циклу, откажитесь от него.

9. Выберите край 0-7: цикл не сформирован, включите его.

10. Выберите край 1-2: Поскольку включение этого края приводит к циклу, откажитесь от него.

11. Выберите край 3-4: цикл не сформирован, включите его.

Поскольку число включенных ребер равно (V — 1), алгоритм останавливается на этом.

C ++

// C ++ программа для алгоритма Крускала для поиска минимального остовного дерева
// данного связного, ненаправленного и взвешенного графа
#include <bits/stdc++.h>

using namespace std;

  
// структура для представления взвешенного ребра в графе

class Edge 

{ 

    public:

    int src, dest, weight; 

}; 

  
// структура для представления подключенной, ненаправленной
// и взвешенный график

class Graph 

{ 

    public:

    // V-> Количество вершин, E-> Количество ребер

    int V, E; 

  

    // график представлен в виде массива ребер.

    // Так как график неориентирован, ребро

    // от src к dest также ребро от dest

    // в ср. И то и другое считается как 1 ребро.

    Edge* edge; 

}; 

  
// Создаем граф с V вершинами и E ребрами

Graph* createGraph(int V, int E) 

{ 

    Graph* graph = new Graph; 

    graph->V = V; 

    graph->E = E; 

  

    graph->edge = new Edge[E]; 

  

    return graph; 

} 

  
// Структура для представления подмножества для union-find

class subset 

{ 

    public:

    int parent; 

    int rank; 

}; 

  
// Полезная функция для поиска множества элементов i
// (использует технику сжатия пути)

int find(subset subsets[], int i) 

{ 

    // найти root и сделать root родителем i

    // (сжатие пути)

    if (subsets[i].parent != i) 

        subsets[i].parent = find(subsets, subsets[i].parent); 

  

    return subsets[i].parent; 

} 

  
// Функция, которая объединяет два набора x и y
// (использует объединение по рангу)

void Union(subset subsets[], int x, int y) 

{ 

    int xroot = find(subsets, x); 

    int yroot = find(subsets, y); 

  

    // Прикрепить дерево меньшего ранга под корень высокого

    // ранговое дерево (объединение по рангу)

    if (subsets[xroot].rank < subsets[yroot].rank) 

        subsets[xroot].parent = yroot; 

    else if (subsets[xroot].rank > subsets[yroot].rank) 

        subsets[yroot].parent = xroot; 

  

    // Если ранги одинаковы, то создайте их как root и

    // увеличиваем ранг на единицу

    else

    { 

        subsets[yroot].parent = xroot; 

        subsets[xroot].rank++; 

    } 

} 

  
// Сравнить два ребра в соответствии с их весом.
// Используется в qsort () для сортировки массива ребер

int myComp(const void* a, const void* b) 

{ 

    Edge* a1 = (Edge*)a; 

    Edge* b1 = (Edge*)b; 

    return a1->weight > b1->weight; 

} 

  
// Основная функция для построения MST с использованием алгоритма Крускала

void KruskalMST(Graph* graph) 

{ 

    int V = graph->V; 

    Edge result[V]; // Tnis будет хранить результирующий MST

    int e = 0; // Индексная переменная, используемая для результата []

    int i = 0; // Индексная переменная, используемая для отсортированных ребер

  

    // Шаг 1: Сортировка всех ребер по неубыванию

    // порядок их веса. Если нам не разрешено

    // изменить данный график, мы можем создать копию

    // массив ребер

    qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp); 

  

    // Выделить память для создания V ssubsets

    subset *subsets = new subset[( V * sizeof(subset) )]; 

  

    // Создать V подмножеств с отдельными элементами

    for (int v = 0; v < V; ++v) 

    { 

        subsets[v].parent = v; 

        subsets[v].rank = 0; 

    } 

  

    // Количество ребер, которые нужно взять, равно V-1

    while (e < V - 1 && i < graph->E) 

    { 

        // Шаг 2: Выберите наименьшее ребро. И прирост

        // индекс для следующей итерации

        Edge next_edge = graph->edge[i++]; 

  

        int x = find(subsets, next_edge.src); 

        int y = find(subsets, next_edge.dest); 

  

        // Если включение этого ребра не вызывает цикл,

        // включить его в результат и увеличить индекс

        // результата для следующего ребра

        if (x != y) 

        { 

            result[e++] = next_edge; 

            Union(subsets, x, y); 

        } 

        // Остальное сбрасываем next_edge

    } 

  

    // выводим содержимое результата [] для отображения

    // построил MST

    cout<<"Following are the edges in the constructed MST\n"; 

    for (i = 0; i < e; ++i) 

        cout<<result[i].src<<" -- "<<result[i].dest<<" == "<<result[i].weight<<endl; 

    return; 

} 

  
// Код драйвера

int main() 

{ 

    / * Давайте создадим следующий взвешенный график

            10

        0 -------- 1

        | / |

    6 | 5 / | 15

        | / |

        2 -------- 3

            4 * /

    int V = 4; // Количество вершин в графе

    int E = 5; // Количество ребер в графе

    Graph* graph = createGraph(V, E); 

  

  

    // добавляем ребро 0-1

    graph->edge[0].src = 0; 

    graph->edge[0].dest = 1; 

    graph->edge[0].weight = 10; 

  

    // добавляем ребро 0-2

    graph->edge[1].src = 0; 

    graph->edge[1].dest = 2; 

    graph->edge[1].weight = 6; 

  

    // добавляем ребро 0-3

    graph->edge[2].src = 0; 

    graph->edge[2].dest = 3; 

    graph->edge[2].weight = 5; 

  

    // добавить ребро 1-3

    graph->edge[3].src = 1; 

    graph->edge[3].dest = 3; 

    graph->edge[3].weight = 15; 

  

    // добавить ребро 2-3

    graph->edge[4].src = 2; 

    graph->edge[4].dest = 3; 

    graph->edge[4].weight = 4; 

  

    KruskalMST(graph); 

  

    return 0; 

} 

  
// Этот код предоставлен rathbhupendra

С

// C программа для алгоритма Крускала для поиска минимального остовного дерева
// данного связного, ненаправленного и взвешенного графа
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

  
// структура для представления взвешенного ребра в графе

struct Edge

{

    int src, dest, weight;

};

  
// структура для представления подключенной, ненаправленной
// и взвешенный график

struct Graph

{

    // V-> Количество вершин, E-> Количество ребер

    int V, E;

  

    // график представлен в виде массива ребер.

    // Так как график неориентирован, ребро

    // от src к dest также ребро от dest

    // в ср. И то и другое считается как 1 ребро.

    struct Edge* edge;

};

  
// Создаем граф с V вершинами и E ребрами

struct Graph* createGraph(int V, int E)

{

    struct Graph* graph = new Graph;

    graph->V = V;

    graph->E = E;

  

    graph->edge = new Edge[E];

  

    return graph;

}

  
// Структура для представления подмножества для union-find

struct subset

{

    int parent;

    int rank;

};

  
// Полезная функция для поиска множества элементов i
// (использует технику сжатия пути)

int find(struct subset subsets[], int i)

{

    // найти root и сделать root родителем i

    // (сжатие пути)

    if (subsets[i].parent != i)

        subsets[i].parent = find(subsets, subsets[i].parent);

  

    return subsets[i].parent;

}

  
// Функция, которая объединяет два набора x и y
// (использует объединение по рангу)

void Union(struct subset subsets[], int x, int y)

{

    int xroot = find(subsets, x);

    int yroot = find(subsets, y);

  

    // Прикрепить дерево меньшего ранга под корень высокого

    // ранговое дерево (объединение по рангу)

    if (subsets[xroot].rank < subsets[yroot].rank)

        subsets[xroot].parent = yroot;

    else if (subsets[xroot].rank > subsets[yroot].rank)

        subsets[yroot].parent = xroot;

  

    // Если ранги одинаковы, то создайте их как root и

    // увеличиваем ранг на единицу

    else

    {

        subsets[yroot].parent = xroot;

        subsets[xroot].rank++;

    }

}

  
// Сравнить два ребра в соответствии с их весом.
// Используется в qsort () для сортировки массива ребер

int myComp(const void* a, const void* b)

{

    struct Edge* a1 = (struct Edge*)a;

    struct Edge* b1 = (struct Edge*)b;

    return a1->weight > b1->weight;

}

  
// Основная функция для построения MST с использованием алгоритма Крускала

void KruskalMST(struct Graph* graph)

{

    int V = graph->V;

    struct Edge result[V];  // Tnis будет хранить результирующий MST

    int e = 0;  // Индексная переменная, используемая для результата []

    int i = 0;  // Индексная переменная, используемая для отсортированных ребер

  

    // Шаг 1: Сортировка всех ребер по неубыванию

    // порядок их веса. Если нам не разрешено

    // изменить данный график, мы можем создать копию

    // массив ребер

    qsort(graph->edge, graph->E, sizeof(graph->edge[0]), myComp);

  

    // Выделить память для создания V ssubsets

    struct subset *subsets =

        (struct subset*) malloc( V * sizeof(struct subset) );

  

    // Создать V подмножеств с отдельными элементами

    for (int v = 0; v < V; ++v)

    {

        subsets[v].parent = v;

        subsets[v].rank = 0;

    }

  

    // Количество ребер, которые нужно взять, равно V-1

    while (e < V - 1 && i < graph->E)

    {

        // Шаг 2: Выберите наименьшее ребро. И прирост

        // индекс для следующей итерации

        struct Edge next_edge = graph->edge[i++];

  

        int x = find(subsets, next_edge.src);

        int y = find(subsets, next_edge.dest);

  

        // Если включение этого ребра не вызывает цикл,

        // включить его в результат и увеличить индекс

        // результата для следующего ребра

        if (x != y)

        {

            result[e++] = next_edge;

            Union(subsets, x, y);

        }

        // Остальное сбрасываем next_edge

    }

  

    // выводим содержимое результата [] для отображения

    // построил MST

    printf("Following are the edges in the constructed MST\n");

    for (i = 0; i < e; ++i)

        printf("%d -- %d == %d\n", result[i].src, result[i].dest,

                                                 result[i].weight);

    return;

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    / * Давайте создадим следующий взвешенный график

             10

        0 -------- 1

        | / |

       6 | 5 / | 15

        | / |

        2 -------- 3

            4 * /

    int V = 4;  // Количество вершин в графе

    int E = 5;  // Количество ребер в графе

    struct Graph* graph = createGraph(V, E);

  

  

    // добавляем ребро 0-1

    graph->edge[0].src = 0;

    graph->edge[0].dest = 1;

    graph->edge[0].weight = 10;

  

    // добавляем ребро 0-2

    graph->edge[1].src = 0;

    graph->edge[1].dest = 2;

    graph->edge[1].weight = 6;

  

    // добавляем ребро 0-3

    graph->edge[2].src = 0;

    graph->edge[2].dest = 3;

    graph->edge[2].weight = 5;

  

    // добавить ребро 1-3

    graph->edge[3].src = 1;

    graph->edge[3].dest = 3;

    graph->edge[3].weight = 15;

  

    // добавить ребро 2-3

    graph->edge[4].src = 2;

    graph->edge[4].dest = 3;

    graph->edge[4].weight = 4;

  

    KruskalMST(graph);

  

    return 0;

}

Джава

// Java-программа для алгоритма Крускала для поиска минимума
// остовное дерево данного связанного, ненаправленного и
// взвешенный график

import java.util.*;

import java.lang.*;

import java.io.*;

  

class Graph

{

    // Класс для представления ребра графа

    class Edge implements Comparable<Edge>

    {

        int src, dest, weight;

  

        // Функция компаратора, используемая для сортировки ребер

        // в зависимости от их веса

        public int compareTo(Edge compareEdge)

        {

            return this.weight-compareEdge.weight;

        }

    };

  

    // Класс для представления подмножества для union-find

    class subset

    {

        int parent, rank;

    };

  

    int V, E;    // V-> нет. вершин и E-> количество ребер

    Edge edge[]; // коллекция всех ребер

  

    // Создаем граф с V вершинами и E ребрами

    Graph(int v, int e)

    {

        V = v;

        E = e;

        edge = new Edge[E];

        for (int i=0; i<e; ++i)

            edge[i] = new Edge();

    }

  

    // Полезная функция для поиска множества элементов i

    // (использует технику сжатия пути)

    int find(subset subsets[], int i)

    {

        // найти root и сделать root родителем i (сжатие пути)

        if (subsets[i].parent != i)

            subsets[i].parent = find(subsets, subsets[i].parent);

  

        return subsets[i].parent;

    }

  

    // Функция, которая объединяет два набора x и y

    // (использует объединение по рангу)

    void Union(subset subsets[], int x, int y)

    {

        int xroot = find(subsets, x);

        int yroot = find(subsets, y);

  

        // Прикрепить дерево меньшего ранга под корень дерева высокого ранга

        // (Объединение по рангу)

        if (subsets[xroot].rank < subsets[yroot].rank)

            subsets[xroot].parent = yroot;

        else if (subsets[xroot].rank > subsets[yroot].rank)

            subsets[yroot].parent = xroot;

  

        // Если ранги одинаковы, сделать из них корень и увеличить

        // его ранг на единицу

        else

        {

            subsets[yroot].parent = xroot;

            subsets[xroot].rank++;

        }

    }

  

    // Основная функция для построения MST с использованием алгоритма Крускала

    void KruskalMST()

    {

        Edge result[] = new Edge[V];  // Tnis будет хранить результирующий MST

        int e = 0;  // Индексная переменная, используемая для результата []

        int i = 0;  // Индексная переменная, используемая для отсортированных ребер

        for (i=0; i<V; ++i)

            result[i] = new Edge();

  

        // Шаг 1: Сортировка всех ребер в неубывающем порядке их

        // вес. Если нам не разрешено изменять данный график, мы

        // можем создать копию массива ребер

        Arrays.sort(edge);

  

        // Выделить память для создания V ssubsets

        subset subsets[] = new subset[V];

        for(i=0; i<V; ++i)

            subsets[i]=new subset();

  

        // Создать V подмножеств с отдельными элементами

        for (int v = 0; v < V; ++v)

        {

            subsets[v].parent = v;

            subsets[v].rank = 0;

        }

  

        i = 0;  // Индекс, используемый для выбора следующего ребра

  

        // Количество ребер, которые нужно взять, равно V-1

        while (e < V - 1)

        {

            // Шаг 2: Выберите наименьшее ребро. И прирост

            // индекс для следующей итерации

            Edge next_edge = new Edge();

            next_edge = edge[i++];

  

            int x = find(subsets, next_edge.src);

            int y = find(subsets, next_edge.dest);

  

            // Если включение этого ребра не вызывает цикл,

            // включить его в результат и увеличить индекс

            // результата для следующего ребра

            if (x != y)

            {

                result[e++] = next_edge;

                Union(subsets, x, y);

            }

            // Остальное сбрасываем next_edge

        }

  

        // выводим содержимое результата [] для отображения

        // построенный MST

        System.out.println("Following are the edges in " + 

                                     "the constructed MST");

        for (i = 0; i < e; ++i)

            System.out.println(result[i].src+" -- " + 

                   result[i].dest+" == " + result[i].weight);

    }

  

    // Программа для водителя

    public static void main (String[] args)

    {

  

        / * Давайте создадим следующий взвешенный график

                 10

            0 -------- 1

            | / |

           6 | 5 / | 15

            | / |

            2 -------- 3

                4 * /

        int V = 4;  // Количество вершин в графе

        int E = 5;  // Количество ребер в графе

        Graph graph = new Graph(V, E);

  

        // добавляем ребро 0-1

        graph.edge[0].src = 0;

        graph.edge[0].dest = 1;

        graph.edge[0].weight = 10;

  

        // добавляем ребро 0-2

        graph.edge[1].src = 0;

        graph.edge[1].dest = 2;

        graph.edge[1].weight = 6;

  

        // добавляем ребро 0-3

        graph.edge[2].src = 0;

        graph.edge[2].dest = 3;

        graph.edge[2].weight = 5;

  

        // добавить ребро 1-3

        graph.edge[3].src = 1;

        graph.edge[3].dest = 3;

        graph.edge[3].weight = 15;

  

        // добавить ребро 2-3

        graph.edge[4].src = 2;

        graph.edge[4].dest = 3;

        graph.edge[4].weight = 4;

  

        graph.KruskalMST();

    }

}
// Этот код предоставлен Aakash Hasija

питон

# Python программа для алгоритма Крускала найти
# Минимальное связующее дерево для данного подключенного,
# неориентированный и взвешенный график

  

from collections import defaultdict

  
# Класс для представления графика

class Graph:

  

    def __init__(self,vertices):

        self.V= vertices #No. вершин

        self.graph = [] # словарь по умолчанию

                                # хранить график

          

   

    # функция для добавления ребра на график

    def addEdge(self,u,v,w):

        self.graph.append([u,v,w])

  

    # Полезная функция для поиска множества элементов i

    # (использует метод сжатия пути)

    def find(self, parent, i):

        if parent[i] == i:

            return i

        return self.find(parent, parent[i])

  

    # Функция, которая объединяет два набора x и y

    # (использует объединение по рангу)

    def union(self, parent, rank, x, y):

        xroot = self.find(parent, x)

        yroot = self.find(parent, y)

  

        # Присоединить дерево меньшего ранга под корнем

        # дерево высокого ранга (Union by Rank)

        if rank[xroot] < rank[yroot]:

            parent[xroot] = yroot

        elif rank[xroot] > rank[yroot]:

            parent[yroot] = xroot

  

        # Если ранги одинаковы, то ставьте их как root

        # и увеличить его ранг на единицу

        else :

            parent[yroot] = xroot

            rank[xroot] += 1

  

    # Основная функция для построения MST с использованием Kruskal's

        # алгоритм

    def KruskalMST(self):

  

        result =[] # Это будет хранить результирующий MST

  

        i = 0 # Индексная переменная, используемая для отсортированных ребер

        e = 0 # Индексная переменная, используемая для результата []

  

            # Шаг 1: Сортировка всех ребер по неубыванию

                # порядок их

                # вес. Если нам не разрешено менять

                # данный график, мы можем создать копию графика

        self.graph =  sorted(self.graph,key=lambda item: item[2])

  

        parent = [] ; rank = []

  

        # Создание V подмножеств с отдельными элементами

        for node in range(self.V):

            parent.append(node)

            rank.append(0)

      

        # Количество ребер, которые нужно взять, равно V-1

        while e < self.V -1 :

  

            # Шаг 2: Выберите наименьшее ребро и приращение

                    # индекс для следующей итерации

            u,v,w =  self.graph[i]

            i = i + 1

            x = self.find(parent, u)

            y = self.find(parent ,v)

  

            # Если включение этого ребра не вызывает цикл,

                        # включить его в результат и увеличить индекс

                        № результата для следующего ребра

            if x != y:

                e = e + 1     

                result.append([u,v,w])

                self.union(parent, rank, x, y)            

            # Остальное отбросить край

  

        # распечатать содержимое результата [] для отображения построенного MST

        print "Following are the edges in the constructed MST"

        for u,v,weight  in result:

            #print str (u) + "-" + str (v) + "==" + str (вес)

            print ("%d -- %d == %d" % (u,v,weight))

  
# Код драйвера

g = Graph(4)

g.addEdge(0, 1, 10)

g.addEdge(0, 2, 6)

g.addEdge(0, 3, 5)

g.addEdge(1, 3, 15)

g.addEdge(2, 3, 4)

  
g.KruskalMST()

  
# Этот код предоставлен Ниламом Ядавом

C #

// C # код для вышеуказанного подхода

using System;

  

class Graph

{

      
// Класс для представления ребра графа

class Edge : IComparable<Edge>

{

    public int src, dest, weight;

  

    // Функция компаратора, используемая для сортировки ребер

    // в зависимости от их веса

    public int CompareTo(Edge compareEdge)

    {

        return this.weight - compareEdge.weight;

    }

}

  
// Класс для представления подмножества для union-find

public class subset

{

    public int parent, rank;

};

  

int V, E; // V-> нет. вершин и E-> количество ребер

Edge[] edge; // коллекция всех ребер

  
// Создаем граф с V вершинами и E ребрами

Graph(int v, int e)

{

    V = v;

    E = e;

    edge = new Edge[E];

    for (int i = 0; i < e; ++i)

        edge[i] = new Edge();

}

  
// Полезная функция для поиска множества элементов i
// (использует технику сжатия пути)

int find(subset[] subsets, int i)

{

    // найти root и сделать root как

    // родитель i (сжатие пути)

    if (subsets[i].parent != i)

        subsets[i].parent = find(subsets, 

                                 subsets[i].parent);

  

    return subsets[i].parent;

}

  
// Функция, которая объединяет
// два набора x и y (использует объединение по рангу)

void Union(subset[] subsets, int x, int y)

{

    int xroot = find(subsets, x);

    int yroot = find(subsets, y);

  

    // Прикрепить дерево меньшего ранга под корнем

    // дерево высокого ранга (Union by Rank)

    if (subsets[xroot].rank < subsets[yroot].rank)

        subsets[xroot].parent = yroot;

    else if (subsets[xroot].rank > subsets[yroot].rank)

        subsets[yroot].parent = xroot;

  

    // Если ранги одинаковы, то ставим их как root

    // и увеличиваем его ранг на единицу

    else

    {

        subsets[yroot].parent = xroot;

        subsets[xroot].rank++;

    }

}

  
// Основная функция для построения MST
// используя алгоритм Крускала

void KruskalMST()

{

    Edge[] result = new Edge[V]; // Это будет хранить результирующий MST

    int e = 0; // Индексная переменная, используемая для результата []

    int i = 0; // Индексная переменная, используемая для отсортированных ребер

    for (i = 0; i < V; ++i)

        result[i] = new Edge();

  

    // Шаг 1: Сортировка всех ребер по неубыванию

    // порядок их веса. Если нам не разрешено

    // чтобы изменить данный график, мы можем создать

    // копия массива ребер

    Array.Sort(edge);

  

    // Выделить память для создания V ssubsets

    subset[] subsets = new subset[V];

    for (i = 0; i < V; ++i)

        subsets[i] = new subset();

  

    // Создать V подмножеств с отдельными элементами

    for (int v = 0; v < V; ++v)

    {

        subsets[v].parent = v;

        subsets[v].rank = 0;

    }

  

    i = 0; // Индекс, используемый для выбора следующего ребра

  

    // Количество ребер, которые нужно взять, равно V-1

    while (e < V - 1)

    {

        // Шаг 2: Выберите наименьшее ребро. И прирост

        // индекс для следующей итерации

        Edge next_edge = new Edge();

        next_edge = edge[i++];

  

        int x = find(subsets, next_edge.src);

        int y = find(subsets, next_edge.dest);

  

        // Если включение этого ребра не вызывает цикл,

        // включить его в результат и увеличить индекс

        // результата для следующего ребра

        if (x != y)

        {

            result[e++] = next_edge;

            Union(subsets, x, y);

        }

        // Остальное сбрасываем next_edge

    }

  

    // выводим содержимое результата [] для отображения

    // построенный MST

    Console.WriteLine("Following are the edges in " +

                              "the constructed MST");

    for (i = 0; i < e; ++i)

            Console.WriteLine(result[i].src + " -- " +

            result[i].dest + " == " + result[i].weight);

        Console.ReadLine();

}

  
// Код драйвера

public static void Main(String[] args)

{

  

    / * Давайте создадим следующий взвешенный график

            10

        0 -------- 1

        | / |

    6 | 5 / | 15

        | / |

        2 -------- 3

            4 * /

    int V = 4; // Количество вершин в графе

    int E = 5; // Количество ребер в графе

    Graph graph = new Graph(V, E);

  

    // добавляем ребро 0-1

    graph.edge[0].src = 0;

    graph.edge[0].dest = 1;

    graph.edge[0].weight = 10;

  

    // добавляем ребро 0-2

    graph.edge[1].src = 0;

    graph.edge[1].dest = 2;

    graph.edge[1].weight = 6;

  

    // добавляем ребро 0-3

    graph.edge[2].src = 0;

    graph.edge[2].dest = 3;

    graph.edge[2].weight = 5;

  

    // добавить ребро 1-3

    graph.edge[3].src = 1;

    graph.edge[3].dest = 3;

    graph.edge[3].weight = 15;

  

    // добавить ребро 2-3

    graph.edge[4].src = 2;

    graph.edge[4].dest = 3;

    graph.edge[4].weight = 4;

  

    graph.KruskalMST();

} 
} 

  
// Этот код предоставлен Aakash Hasija

Following are the edges in the constructed MST
2 -- 3 == 4
0 -- 3 == 5
0 -- 1 == 10

Сложность времени: O (ElogE) или O (ElogV). Сортировка ребер занимает O (ELogE) время. После сортировки мы перебираем все ребра и применяем алгоритм find-union. Операции поиска и объединения могут занимать не более O (LogV) времени. Таким образом, общая сложность составляет O (ELogE + ELogV) время. Значение E может быть не более O (V 2 ), поэтому O (LogV) равны O (LogE). Следовательно, общая сложность времени составляет O (ElogE) или O (ElogV)

Ссылки:
http://www.ics.uci.edu/~eppstein/161/960206.html
http://en.wikipedia.org/wiki/Minimum_spanning_tree

Эта статья составлена Aashish Barnwal и рецензирована командой GeeksforGeeks. Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Алгоритм минимального остовного дерева Крускала | Жадный Алго-2

0.00 (0%) 0 votes