Arbol de expansión mínima - Kruskal

Algoritmo de kruskal:

Este algoritmo se usa para hallar el árbol minimal de un grafo ponderado(con peso). El árbol minimal es la forma mas eficiente de conectar todos los vértices del grafo, mediante las aristas con menor peso posible…

Metodología:

1°: Hallar y marcar la arista de menor peso del grafo, si hay mas de una se marca cualquiera de ellas.

2°: Hallar y marcar la arista de menor peso sin contar la anterior, controlando que no generemos ciclos en el grafo, y controlando también que vértices nos falta recorrer. Esto quiere decir que en el árbol resultante tendremos n-1 aristas, siendo n el numero de vértices del grafo.

3°: Repetir el paso 2.

Cuando ya recorrimos todos los vértices, el árbol resultante es el árbol minimal.

Conclusión:

Como podemos ver, el algoritmo es un proceso recursivo. Ya que, excepto en el primer paso que solamente se halla y marca la arista de menor peso, se debe realizar la misma acción de hallar y marcar, pero con el adicional de controlar que no formen siclos, y que queden vértices que recorrer, que seria el caso base de la recursividad.

Aquí un link con un video explicando gráficamente el funcionamiento del algoritmo de kruskal:

https://www.youtube.com/watch?v=SilS8f8icWY

 

Aquí tenemos el Ejercicio 11 de la Guia Nº:8, el cual nos dio la consigna de hacerlo hoy en clases de Práctica la profesora Mariela Vanesa Burghardt para realizarlo en grupos.

 Archivo .pas codificado en Geany (Free Pascal).

//CONSGINA EJERCICIO 11, GUIA Nº:8
//En un plano con varias nodos de coordenadas (x, y). Tu trabajo es como conectar todos los nodos de forma que utilice la menor cantidad de tinta posible (Alg. Kruskal).

program grafoKruskal;

// Grafo conexo (esta todo conectado), denso (faltan pocas aristas para ser completo), no dirigido (bidireccional) y ponderado (con peso)

uses crt;
const n = 5;

type
{
 tVector = array [1..n] of string;
 tVertice = 1..n;
 tArco = record
  origen: tVertice;
  destino: tVertice;
 end;
}
 conjuntoVertices = array [1..n] of integer;
 conjuntoArcos = array [1..n, 1..n] of integer;
 tGrafo = record
  vertices: conjuntoVertices;
  arcos: conjuntoArcos;
 end;

var
 vGrafo: tGrafo;
{
 vector: tVector;
}


procedure crearGrafo(var pGrafo: tGrafo);
var
 i, j: integer;
begin
 for i := 1 to n do
 begin
  pGrafo.vertices[i]:= i;
  for j := 1 to n do
  begin
   pGrafo.arcos[i,j] := 0;
  end;
 end;
end;


function peso(i: integer; j: integer): integer;
begin
 writeln('Que peso tiene el vertice ', i, ' con el ', j, ': ');
 readln(peso);
end;


procedure cargarGrafo(var pGrafo: tGrafo);
var
 i, j: integer;
begin
 for i := 1 to n do
 begin
  for j := 1 to n do
  begin
   pGrafo.arcos[i,j] := peso(i, j);
  end;
 end;
end;


procedure mostrarGrafo(pGrafo: tGrafo);
var
 i, j: integer;
begin
 for i := 1 to n do
 begin
  for j := 1 to n do
  begin
   write(pGrafo.arcos[i,j], ',')
  end;
  writeln();
 end;
end;


begin
 crearGrafo(vGrafo);
 cargarGrafo(vGrafo);
 mostrarGrafo(vGrafo);
end.
//El ejercicio continua en construccion, lo iremos modificando.

 

INICIO