Algoritmul lui Kruskal

Aspecte teoretice:

Algoritmul lui Kruskal este un algoritm în teoria grafurilor care găsește arborele parțial de cost minim pentru un graf conex ponderat. Cu alte cuvinte, găsește submulțimea muchiilor care formează un arbore care include toate vârfurile și care este minimizat din punct de vedere al costului. Dacă graful nu este conex, atunci algoritmul găsește o pădure parțială de cost minim (un arbore parțial de cost minim pentru fiecare componentă conexă). Algoritmul lui Kruskal este un exemplu de algoritm greedy.

Algoritmul funcționează în felul următor:

• creează o pădure F (o mulțime de arbori), unde fiecare vârf din graf este un arbore separat
• creează o mulțime S care conține toate muchiile din graf
• atât timp cât S este nevidă
• elimină o muchie de cost minim din S
• dacă acea muchie conectează doi arbori distincți, atunci adaugă muchia în pădure, combinând cei doi arbori într-unul singur
• altfel, ignoră muchia

La sfârșitul algoritmului, pădurea are doar o componentă care reprezintă un arbore parțial de cost minim al grafului.

Implementare:

Cod Sursa C++

// KruskallCPP.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
#include <fstream>
 
using namespace std;
 
typedef struct minimum
{
	int lin, col;
} minimum;
 
int n, a[50][50], m[50][50], t[50][50], k, ok, v[50], st[50];
void initializare(void)
{
	for (int i = 1; i<50; i++)
		st[i] = 0;
}
 
int valid(int k)
{
	if (k>1 && t[st[k]][st[k - 1]] == 0)
		return 0;
	for (int i = 2; i<k; i++)
	if (st[i] == st[k])
		return 0;
	return 1;
}
 
void bktr(int k, int n)
{
	for (int i = 1; i <= n; i++)
	{
		st[k] = i;
		if (valid(k) == 1)
		if (st[1] == st[k] && k>3)
			ok = 1;
		else bktr(k + 1, n);
	}
}
 
void afisare(int a[50][50], int n)
{
	int i, j;
	printf("\n");
	for (i = 1; i <= n; i++)
	{
		for (j = 1; j <= n; j++)
			printf("%6d", a[i][j]);
		printf("\n");
	}
}
 
minimum minim(int a[50][50], int n)
{
	minimum min0;
	int i, j;
	int min1 = 32000;
	for (i = 1; i <= n; i++)
	for (j = 1; j <= n; j++)
	if (a[i][j]<min1 && m[i][j] != 0)
	{
		min0.lin = i;
		min0.col = j;
		min1 = a[i][j];
	}   return min0;
}
 
void main(void)
{
	int i, j, k, x, y;
	cout << "n="; cin >> n;
	for (i = 1; i <= n-1; i++)
	for (j = i+1; j <= n; j++)
	{
		cout << "a[" << i << "][" << j <<"]=";
		cin >> a[i][j];
	}
	printf("\n graful are %d noduri,matricea sa de adiacenta fiind:\n", n);
	afisare(a, n);
	for (i = 1; i <= n; i++)
		m[i][i] = 0;
	for (i = 1; i<n; i++)
	for (j = i + 1; j <= n; j++)
	if (a[i][j] == 1)
	{
		printf("\n cat este costul muchiei (%d %d)?", i, j);
		scanf_s("%d", &m[i][j]);  m[j][i] = m[i][j];
	}
	else
	{
		m[i][j] = 1000;
		m[j][i] = 1000;
	}
	printf("\n matricea costurilor este :\n");
	afisare(m, n);
	for (i = 1; i <= n; i++)
	for (j = 1; j <= n; j++)
		t[i][j] = 0;
	k = 0;
	for (i = 1; i<n + k; i++)
	{
		x = minim(m, n).lin;
		y = minim(m, n).col;
		t[x][y] = m[x][y];
		t[y][x] = t[x][y];
		if (i>2)
		{
			ok = 0;
			bktr(1, y);
			if (ok == 1)
			{
				t[x][y] = 0;
				t[y][x] = 0;
				k++;
			}
		}
		m[x][y] = 1000;
		m[y][x] = 1000;
	}
	printf("arborele de cost minim este:\n");
	afisare(t, n);
	system("pause");
}
 

Exemplu: