Árbol de expansión mínimo (MST) de Prim | Codicioso Algo-5 – Part 1

 

Hemos discutido  el algoritmo de Kruskal para el árbol de expansión mínimo . Al igual que el algoritmo de Kruskal, el algoritmo de Prim también es un  algoritmo Greedy . Comienza con un árbol de expansión vacío. La idea es mantener dos conjuntos de vértices. El primer conjunto contiene los vértices ya incluidos en el MST, el otro conjunto contiene los vértices aún no incluidos. En cada paso, considera todos los bordes que conectan los dos conjuntos y selecciona el borde de peso mínimo de estos bordes. Después de seleccionar el borde, mueve el otro extremo del borde al conjunto que contiene MST. 
Un grupo de aristas que conecta dos conjuntos de vértices en un gráfico se llama  corte en la teoría de grafosEntonces, en cada paso del algoritmo de Prim, encontramos un corte (de dos conjuntos, uno contiene los vértices ya incluidos en MST y el otro contiene el resto de los vértices), seleccionamos el borde de peso mínimo del corte e incluimos este vértice a MST Set (el conjunto que contiene vértices ya incluidos).

¿Cómo funciona el algoritmo de Prim? La idea detrás del algoritmo de Prim es simple, un árbol de expansión significa que todos los vértices deben estar conectados. Entonces, los dos subconjuntos disjuntos (discutidos anteriormente) de vértices deben estar conectados para hacer un árbol de expansión  . Y deben estar conectados con el borde de peso mínimo para convertirlo en un árbol de expansión mínimo  .

Algoritmo 
1) Cree un conjunto mstSet que realice un seguimiento de los vértices ya incluidos en MST. 
2) Asigne un valor clave a todos los vértices en el gráfico de entrada. Inicialice todos los valores clave como INFINITOS. Asigne el valor clave como 0 para el primer vértice para que se elija primero. 
3) Si bien mstSet no incluye todos los vértices 
a) Elija un vértice u que no esté en mstSet y tenga un valor clave mínimo. 
…. b) Incluya u en mstSet. 
…. c) Actualizar valor clave de todos los vértices adyacentes de u. Para actualizar los valores clave, itere a través de todos los vértices adyacentes. Para cada vértice adyacente v , si el peso del borde uv es menor que el valor clave anterior de v , actualice el valor clave como el peso de uv
. La idea de usar valores clave es elegir el borde de peso mínimo del corte . Los valores clave se usan solo para vértices que aún no están incluidos en MST, el valor clave para estos vértices indica los bordes de peso mínimo que los conectan al conjunto de vértices incluidos en MST. 
 

C++

// A C++ program for Prim's Minimum 
// Spanning Tree (MST) algorithm. The program is 
// for adjacency matrix representation of the graph 
#include <bits/stdc++.h>
using namespace std;
  
// Number of vertices in the graph 
#define V 5 
  
// A utility function to find the vertex with 
// minimum key value, from the set of vertices 
// not yet included in MST 
int minKey(int key[], bool mstSet[]) 
{ 
    // Initialize min value 
    int min = INT_MAX, min_index; 
  
    for (int v = 0; v < V; v++) 
        if (mstSet[v] == false && key[v] < min) 
            min = key[v], min_index = v; 
  
    return min_index; 
} 
  
// A utility function to print the 
// constructed MST stored in parent[] 
void printMST(int parent[], int graph[V][V]) 
{ 
    cout<<"Edge \tWeight\n"; 
    for (int i = 1; i < V; i++) 
        cout<<parent[i]<<" - "<<i<<" \t"<<graph[i][parent[i]]<<" \n"; 
} 
  
// Function to construct and print MST for 
// a graph represented using adjacency 
// matrix representation 
void primMST(int graph[V][V]) 
{ 
    // Array to store constructed MST 
    int parent[V]; 
      
    // Key values used to pick minimum weight edge in cut 
    int key[V]; 
      
    // To represent set of vertices included in MST 
    bool mstSet[V]; 
  
    // Initialize all keys as INFINITE 
    for (int i = 0; i < V; i++) 
        key[i] = INT_MAX, mstSet[i] = false; 
  
    // Always include first 1st vertex in MST. 
    // Make key 0 so that this vertex is picked as first vertex. 
    key[0] = 0; 
    parent[0] = -1; // First node is always root of MST 
  
    // The MST will have V vertices 
    for (int count = 0; count < V - 1; count++)
    { 
        // Pick the minimum key vertex from the 
        // set of vertices not yet included in MST 
        int u = minKey(key, mstSet); 
  
        // Add the picked vertex to the MST Set 
        mstSet[u] = true; 
  
        // Update key value and parent index of 
        // the adjacent vertices of the picked vertex. 
        // Consider only those vertices which are not 
        // yet included in MST 
        for (int v = 0; v < V; v++) 
  
            // graph[u][v] is non zero only for adjacent vertices of m 
            // mstSet[v] is false for vertices not yet included in MST 
            // Update the key only if graph[u][v] is smaller than key[v] 
            if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]) 
                parent[v] = u, key[v] = graph[u][v]; 
    } 
  
    // print the constructed MST 
    printMST(parent, graph); 
} 
  
// Driver code
int main() 
{ 
    /* Let us create the following graph 
        2 3 
    (0)--(1)--(2) 
    | / \ | 
    6| 8/ \5 |7 
    | / \ | 
    (3)-------(4) 
            9     */
    int graph[V][V] = { { 0, 2, 0, 6, 0 }, 
                        { 2, 0, 3, 8, 5 }, 
                        { 0, 3, 0, 0, 7 }, 
                        { 6, 8, 0, 0, 9 }, 
                        { 0, 5, 7, 9, 0 } }; 
  
    // Print the solution 
    primMST(graph); 
  
    return 0; 
} 
  
// This code is contributed by rathbhupendra

C

// A C program for Prim's Minimum
// Spanning Tree (MST) algorithm. The program is
// for adjacency matrix representation of the graph
#include <limits.h>
#include <stdbool.h>
#include <stdio.h>
// Number of vertices in the graph
#define V 5
  
// A utility function to find the vertex with
// minimum key value, from the set of vertices
// not yet included in MST
int minKey(int key[], bool mstSet[])
{
    // Initialize min value
    int min = INT_MAX, min_index;
  
    for (int v = 0; v < V; v++)
        if (mstSet[v] == false && key[v] < min)
            min = key[v], min_index = v;
  
    return min_index;
}
  
// A utility function to print the
// constructed MST stored in parent[]
int printMST(int parent[], int graph[V][V])
{
    printf("Edge \tWeight\n");
    for (int i = 1; i < V; i++)
        printf("%d - %d \t%d \n", parent[i], i, graph[i][parent[i]]);
}
  
// Function to construct and print MST for
// a graph represented using adjacency
// matrix representation
void primMST(int graph[V][V])
{
    // Array to store constructed MST
    int parent[V];
    // Key values used to pick minimum weight edge in cut
    int key[V];
    // To represent set of vertices included in MST
    bool mstSet[V];
  
    // Initialize all keys as INFINITE
    for (int i = 0; i < V; i++)
        key[i] = INT_MAX, mstSet[i] = false;
  
    // Always include first 1st vertex in MST.
    // Make key 0 so that this vertex is picked as first vertex.
    key[0] = 0;
    parent[0] = -1; // First node is always root of MST
  
    // The MST will have V vertices
    for (int count = 0; count < V - 1; count++) {
        // Pick the minimum key vertex from the
        // set of vertices not yet included in MST
        int u = minKey(key, mstSet);
  
        // Add the picked vertex to the MST Set
        mstSet[u] = true;
  
        // Update key value and parent index of
        // the adjacent vertices of the picked vertex.
        // Consider only those vertices which are not
        // yet included in MST
        for (int v = 0; v < V; v++)
  
            // graph[u][v] is non zero only for adjacent vertices of m
            // mstSet[v] is false for vertices not yet included in MST
            // Update the key only if graph[u][v] is smaller than key[v]
            if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v])
                parent[v] = u, key[v] = graph[u][v];
    }
  
    // print the constructed MST
    printMST(parent, graph);
}
  
// driver program to test above function
int main()
{
    /* Let us create the following graph
        2 3
    (0)--(1)--(2)
    | / \ |
    6| 8/ \5 |7
    | /     \ |
    (3)-------(4)
            9         */
    int graph[V][V] = { { 0, 2, 0, 6, 0 },
                        { 2, 0, 3, 8, 5 },
                        { 0, 3, 0, 0, 7 },
                        { 6, 8, 0, 0, 9 },
                        { 0, 5, 7, 9, 0 } };
  
    // Print the solution
    primMST(graph);
  
    return 0;
}

Java

// A Java program for Prim's Minimum Spanning Tree (MST) algorithm.
// The program is for adjacency matrix representation of the graph
  
import java.util.*;
import java.lang.*;
import java.io.*;
  
class MST {
    // Number of vertices in the graph
    private static final int V = 5;
  
    // A utility function to find the vertex with minimum key
    // value, from the set of vertices not yet included in MST
    int minKey(int key[], Boolean mstSet[])
    {
        // Initialize min value
        int min = Integer.MAX_VALUE, min_index = -1;
  
        for (int v = 0; v < V; v++)
            if (mstSet[v] == false && key[v] < min) {
                min = key[v];
                min_index = v;
            }
  
        return min_index;
    }
  
    // A utility function to print the constructed MST stored in
    // parent[]
    void printMST(int parent[], int graph[][])
    {
        System.out.println("Edge \tWeight");
        for (int i = 1; i < V; i++)
            System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);
    }
  
    // Function to construct and print MST for a graph represented
    // using adjacency matrix representation
    void primMST(int graph[][])
    {
        // Array to store constructed MST
        int parent[] = new int[V];
  
        // Key values used to pick minimum weight edge in cut
        int key[] = new int[V];
  
        // To represent set of vertices included in MST
        Boolean mstSet[] = new Boolean[V];
  
        // Initialize all keys as INFINITE
        for (int i = 0; i < V; i++) {
            key[i] = Integer.MAX_VALUE;
            mstSet[i] = false;
        }
  
        // Always include first 1st vertex in MST.
        key[0] = 0; // Make key 0 so that this vertex is
        // picked as first vertex
        parent[0] = -1; // First node is always root of MST
  
        // The MST will have V vertices
        for (int count = 0; count < V - 1; count++) {
            // Pick thd minimum key vertex from the set of vertices
            // not yet included in MST
            int u = minKey(key, mstSet);
  
            // Add the picked vertex to the MST Set
            mstSet[u] = true;
  
            // Update key value and parent index of the adjacent
            // vertices of the picked vertex. Consider only those
            // vertices which are not yet included in MST
            for (int v = 0; v < V; v++)
  
                // graph[u][v] is non zero only for adjacent vertices of m
                // mstSet[v] is false for vertices not yet included in MST
                // Update the key only if graph[u][v] is smaller than key[v]
                if (graph[u][v] != 0 && mstSet[v] == false && graph[u][v] < key[v]) {
                    parent[v] = u;
                    key[v] = graph[u][v];
                }
        }
  
        // print the constructed MST
        printMST(parent, graph);
    }
  
    public static void main(String[] args)
    {
        /* Let us create the following graph
        2 3
        (0)--(1)--(2)
        | / \ |
        6| 8/ \5 |7
        | /     \ |
        (3)-------(4)
            9         */
        MST t = new MST();
        int graph[][] = new int[][] { { 0, 2, 0, 6, 0 },
                                      { 2, 0, 3, 8, 5 },
                                      { 0, 3, 0, 0, 7 },
                                      { 6, 8, 0, 0, 9 },
                                      { 0, 5, 7, 9, 0 } };
  
        // Print the solution
        t.primMST(graph);
    }
}
// This code is contributed by Aakash Hasija

Python3

# A Python program for Prim's Minimum Spanning Tree (MST) algorithm.
# The program is for adjacency matrix representation of the graph
  
import sys # Library for INT_MAX
  
class Graph():
  
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for column in range(vertices)] 
                    for row in range(vertices)]
  
    # A utility function to print the constructed MST stored in parent[]
    def printMST(self, parent):
        print ("Edge \tWeight")
        for i in range(1, self.V):
            print (parent[i], "-", i, "\t", self.graph[i][parent[i]])
  
    # A utility function to find the vertex with 
    # minimum distance value, from the set of vertices 
    # not yet included in shortest path tree
    def minKey(self, key, mstSet):
  
        # Initialize min value
        min = sys.maxsize
  
        for v in range(self.V):
            if key[v] < min and mstSet[v] == False:
                min = key[v]
                min_index = v
  
        return min_index
  
    # Function to construct and print MST for a graph 
    # represented using adjacency matrix representation
    def primMST(self):
  
        # Key values used to pick minimum weight edge in cut
        key = [sys.maxsize] * self.V
        parent = [None] * self.V # Array to store constructed MST
        # Make key 0 so that this vertex is picked as first vertex
        key[0] = 0 
        mstSet = [False] * self.V
  
        parent[0] = -1 # First node is always the root of
  
        for cout in range(self.V):
  
            # Pick the minimum distance vertex from 
            # the set of vertices not yet processed. 
            # u is always equal to src in first iteration
            u = self.minKey(key, mstSet)
  
            # Put the minimum distance vertex in 
            # the shortest path tree
            mstSet[u] = True
  
            # Update dist value of the adjacent vertices 
            # of the picked vertex only if the current 
            # distance is greater than new distance and
            # the vertex in not in the shortest path tree
            for v in range(self.V):
  
                # graph[u][v] is non zero only for adjacent vertices of m
                # mstSet[v] is false for vertices not yet included in MST
                # Update the key only if graph[u][v] is smaller than key[v]
                if self.graph[u][v] > 0 and mstSet[v] == False and key[v] > self.graph[u][v]:
                        key[v] = self.graph[u][v]
                        parent[v] = u
  
        self.printMST(parent)
  
g = Graph(5)
g.graph = [ [0, 2, 0, 6, 0],
            [2, 0, 3, 8, 5],
            [0, 3, 0, 0, 7],
            [6, 8, 0, 0, 9],
            [0, 5, 7, 9, 0]]
  
g.primMST();
  
# Contributed by Divyanshu Mehta

C#

// A C# program for Prim's Minimum
// Spanning Tree (MST) algorithm.
// The program is for adjacency
// matrix representation of the graph
using System;
class MST {
  
    // Number of vertices in the graph
    static int V = 5;
  
    // A utility function to find
    // the vertex with minimum key
    // value, from the set of vertices
    // not yet included in MST
    static int minKey(int[] key, bool[] mstSet)
    {
  
        // Initialize min value
        int min = int.MaxValue, min_index = -1;
  
        for (int v = 0; v < V; v++)
            if (mstSet[v] == false && key[v] < min) {
                min = key[v];
                min_index = v;
            }
  
        return min_index;
    }
  
    // A utility function to print
    // the constructed MST stored in
    // parent[]
    static void printMST(int[] parent, int[, ] graph)
    {
        Console.WriteLine("Edge \tWeight");
        for (int i = 1; i < V; i++)
            Console.WriteLine(parent[i] + " - " + i + "\t" + graph[i, parent[i]]);
    }
  
    // Function to construct and
    // print MST for a graph represented
    // using adjacency matrix representation
    static void primMST(int[, ] graph)
    {
  
        // Array to store constructed MST
        int[] parent = new int[V];
  
        // Key values used to pick
        // minimum weight edge in cut
        int[] key = new int[V];
  
        // To represent set of vertices
        // included in MST
        bool[] mstSet = new bool[V];
  
        // Initialize all keys
        // as INFINITE
        for (int i = 0; i < V; i++) {
            key[i] = int.MaxValue;
            mstSet[i] = false;
        }
  
        // Always include first 1st vertex in MST.
        // Make key 0 so that this vertex is
        // picked as first vertex
        // First node is always root of MST
        key[0] = 0;
        parent[0] = -1;
  
        // The MST will have V vertices
        for (int count = 0; count < V - 1; count++) {
  
            // Pick thd minimum key vertex
            // from the set of vertices
            // not yet included in MST
            int u = minKey(key, mstSet);
  
            // Add the picked vertex
            // to the MST Set
            mstSet[u] = true;
  
            // Update key value and parent
            // index of the adjacent vertices
            // of the picked vertex. Consider
            // only those vertices which are
            // not yet included in MST
            for (int v = 0; v < V; v++)
  
                // graph[u][v] is non zero only
                // for adjacent vertices of m
                // mstSet[v] is false for vertices
                // not yet included in MST Update
                // the key only if graph[u][v] is
                // smaller than key[v]
                if (graph[u, v] != 0 && mstSet[v] == false
                    && graph[u, v] < key[v]) {
                    parent[v] = u;
                    key[v] = graph[u, v];
                }
        }
  
        // print the constructed MST
        printMST(parent, graph);
    }
  
    // Driver Code
    public static void Main()
    {
  
        /* Let us create the following graph
        2 3
        (0)--(1)--(2)
        | / \ |
        6| 8/ \5 |7
        | / \ |
        (3)-------(4)
            9 */
  
        int[, ] graph = new int[, ] { { 0, 2, 0, 6, 0 },
                                      { 2, 0, 3, 8, 5 },
                                      { 0, 3, 0, 0, 7 },
                                      { 6, 8, 0, 0, 9 },
                                      { 0, 5, 7, 9, 0 } };
  
        // Print the solution
        primMST(graph);
    }
}
  
// This code is contributed by anuj_67.

Javascript

<script>
  
// Number of vertices in the graph 
let V = 5;
  
// A utility function to find the vertex with 
// minimum key value, from the set of vertices 
// not yet included in MST 
function minKey(key, mstSet) 
{ 
    // Initialize min value 
    let min = Number.MAX_VALUE, min_index; 
  
    for (let v = 0; v < V; v++) 
        if (mstSet[v] == false && key[v] < min) 
            min = key[v], min_index = v; 
  
    return min_index; 
} 
  
// A utility function to print the 
// constructed MST stored in parent[] 
function printMST(parent, graph) 
{ 
    document.write("Edge      Weight" + "<br>"); 
    for (let i = 1; i < V; i++) 
        document.write(parent[i] + "   -  " + i + "     " + graph[i][parent[i]] + "<br>"); 
} 
  
// Function to construct and print MST for 
// a graph represented using adjacency 
// matrix representation 
function primMST(graph) 
{ 
    // Array to store constructed MST 
    let parent = []; 
      
    // Key values used to pick minimum weight edge in cut 
    let key = []; 
      
    // To represent set of vertices included in MST 
    let mstSet = []; 
  
    // Initialize all keys as INFINITE 
    for (let i = 0; i < V; i++) 
        key[i] = Number.MAX_VALUE, mstSet[i] = false; 
  
    // Always include first 1st vertex in MST. 
    // Make key 0 so that this vertex is picked as first vertex. 
    key[0] = 0; 
    parent[0] = -1; // First node is always root of MST 
  
    // The MST will have V vertices 
    for (let count = 0; count < V - 1; count++)
    { 
        // Pick the minimum key vertex from the 
        // set of vertices not yet included in MST 
        let u = minKey(key, mstSet); 
  
        // Add the picked vertex to the MST Set 
        mstSet[u] = true; 
  
        // Update key value and parent index of 
        // the adjacent vertices of the picked vertex. 
        // Consider only those vertices which are not 
        // yet included in MST 
        for (let v = 0; v < V; v++) 
  
            // graph[u][v] is non zero only for adjacent vertices of m 
            // mstSet[v] is false for vertices not yet included in MST 
            // Update the key only if graph[u][v] is smaller than key[v] 
            if (graph[u][v] && mstSet[v] == false && graph[u][v] < key[v]) 
                parent[v] = u, key[v] = graph[u][v]; 
    } 
  
    // print the constructed MST 
    printMST(parent, graph); 
} 
  
// Driver code
  
/* Let us create the following graph 
    2 3 
    (0)--(1)--(2) 
    | / \ | 
    6| 8/ \5 |7 
    | / \ | 
    (3)-------(4) 
    9     */
      
let graph = [ [ 0, 2, 0, 6, 0 ], 
[ 2, 0, 3, 8, 5 ], 
[ 0, 3, 0, 0, 7 ], 
[ 6, 8, 0, 0, 9 ], 
[ 0, 5, 7, 9, 0 ] ]; 
  
// Print the solution 
primMST(graph); 
  
  
// This code is contributed by Dharanendra L V.
</script>

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *