Algoritmul lui Prim

Aspecte teoretice:

Algoritmul lui Prim este un algoritm din teoria grafurilor care găsește arborele parțial de cost minim al unui graf conex ponderat. Înseamnă că găsește submulțimea muchiilor care formează un arbore care include toate vârfurile și al cărui cost este minimizat. Algoritmul a fost descoperit în 1930 de către matematicianul Vojtěch Jarník și apoi, independent, de informaticienii Robert C. Prim în 1957 și redescoperit de Edsger Dijkstra în 1959. De aceea mai este numit Algoritmul DJP, algoritmul Jarník sau algoritmul Prim-Jarník.

Algoritmul incrementează mărimea unui arbore, pornind de la un nod, până când sunt incluse toate nodurile.

• Intrare: Un graf conex ponderat cu nodurile V și muchiile E.
• Initializare: V_nou = {x}, unde x este un nod arbitrar (punct de plecare) din V, E_nou= {}
• repetă până când V_nou=V:
  • Alege muchia (u,v) din E de cost minim astfel încât u este în V_nou și v nu e (dacă există mai multe astfel de muchii, se alege arbitrar)
  • Se adaugă v la V_nou, (u,v) la E_nou
• Ieșire: V_nou și E_nou descriu arborele parțial de cost minim

Implementare:

Cod Sursa C++

/* Algoritmul lui Prim (determina un APM intr-un graf ponderat conex) */
#include "stdafx.h"
#include <iostream>   // <iostream.h> pentru Borland C++ 3.1
//#include <fstream>   // <fstream.h> pentru Borland C++ 3.1
using namespace std;   // a elimina/comenta, pentru Borland C++ 3.1
 
//ifstream fs("muchii.txt"); // are structura: [ nr. varfuri ] [ nr. muchii ] [ vf1, vf2, cost ]*
 
int nr_vf, nr_eg;   // identificatorii "lungi" (in loc de n, m) evita confuzii la copiere!
 
typedef struct
{
	int beg, end; // capetele muchiei
	double cost;
} muchie;
 
muchie * M;  // tabloul muchiilor grafului
 
int * APM;  // rangurile celor (n-1) muchii din M[] alese in APM
 
void init()
{
	cout << "nr varfuri: ";
	cin >> nr_vf;
	cout << "nr muchii: ";
	cin >> nr_eg;
	//fs >> nr_vf >> nr_eg;
	APM = new int[nr_vf - 1];
	M = new muchie[nr_eg]; // main() va trebui sa elibereze zonele alocate aici
	for (int i = 0; i < nr_eg; i++)
	{
		cout << "vf1: ";
		cin >> M[i].beg;
		cout << "vf2: ";
		cin >> M[i].end;
		cout << "cost: ";
		cin >> M[i].cost;
		//fs >> M[i].beg >> M[i].end >> M[i].cost;
		M[i].beg--; M[i].end--; // in fisier varfurile 1..n dar in tablou 0..(n-1)
	}
}
 
int cut_min(int *Z) 
{ // Z[i] = 1 sau 0, după cum vârful i a fost sau nu vizitat
	int rm; double q = 1.E15; // q este o valoare mai mare decât costurile existente
	for (int i = 0; i < nr_eg; i++)
	if (Z[M[i].beg] ^ Z[M[i].end]) // capetele muchiei să fie din "tabere" diferite (XOR)
	if (M[i].cost < q) {
		rm = i;
		q = M[i].cost;
	}
	return rm; // rangul celei mai "scurte" muchii care uneşte un vârf vizitat cu unul nevizitat
}
 
void apm_Prim(int start) 
{ // vârful de start (oarecare, când costurile sunt distincte: APM unic)
	int *Z = new int[nr_vf], i;
	for (i = 0; i < nr_vf; i++) // iniţializează vârfurile ca "nerecrutate" în APM
		Z[i] = 0;
	Z[start] = 1; // marchează capătul primei muchii care se va include în APM
	for (i = 0; i < nr_vf - 1; i++) { // un APM conţine nr_vf-1 muchii
		int rm = cut_min(Z);
		APM[i] = rm; // muchia de rang rm este inclusă în APM (a i-a muchie a arborelui)
		if (Z[M[rm].beg])
			Z[M[rm].end] = 1; // marchează şi celălalt capăt al muchiei incluse în APM
		else Z[M[rm].beg] = 1;
	}
	delete[] Z; // eliberează în final, zona alocată pentru Z[]
}
 
int main() 
{
	init();
	int i; double cost_apm = 0;
	cout << "vârful de plecare: "; cin >> i;
	apm_Prim(i - 1); // APM[] va conţine rangurile muchiilor selectate în A.P.M.
	for (i = 0; i < nr_vf - 1; i++) { // afişează muchiile din APM şi costurile
		int rm = APM[i];
		cout << (M[rm].beg + 1) << " - " << (M[rm].end + 1) << '\t' << M[rm].cost << '\n';
		cost_apm += M[rm].cost;
	}
	cout << "\nCostul minim = " << cost_apm << '\n';
	delete[] APM; // alocările le-a făcut INIT(), dar zonele trebuie în final, eliberate!
	delete[] M;
	system("pause");
}
 
 
 

Exemplu: