prima

1//algorytm Prima

2#include <iostream>

3#include <cstdlib>

5#define MX 10000 

7using namespace std;

9int main()

10	{
11	int graf[100][100];
12	int odwiedzone[MX];
13	int waga[MX];
14
15	int n , m;

16int a, b, c; 

17int wiersz,wierzcholki,koszt;

18

19cout<<"Podaj liczbe wierzcholkow i krawedzi"<<endl;

20cin>>n>>m; 

22for(int i=1; i <= n; i++ ) 

23{

24odwiedzone[i]=0; //nie ma poprzednikow i nastepnikow

25waga[i]=MX; // waga jest rowna max

26for(int j=1; j <= n; j++ )

27{

28	graf[i][j]=0; // wypelnianie tablicy zerami

29}

30}

31

32for (int i=1; i <= m; i++ ) //pobieranie drog w grafie

33{

34cout<<"Podaj wierzcholki krawedzi i jej wage"<<endl;

35cin>>a>>b>>c; //droga miedzy a i b o wadze c

36graf[a][b]=graf[b][a]=c; //wypelnianie tablicy danymi uzytkownika

37}

38

39// inicjalizacja danych do algorytmu Prima

40wiersz=1; //zaczynamy od pierwszego wiersza, czyli przeszukujemy wszystkie polaczenia pierwszego wierzcholka

41waga[wiersz]=0; // pierwsza waga rowna jest zero

42wierzcholki=1; //zaczynamy od pierwszech wierzcholka

43odwiedzone[wiersz]=1; // pierwszy wierzcholek odwiedzilismy, bo zaczynamy od

niego

45cout<<"Minimalne drzewo rozpinajace"<<endl;

46//algorytm Prima

47while(wierzcholki!=n) // n liczba wierzcholkow

48{

49for(int i=1; i<=n; i++) //przeszukanie pierwszego wiersza

50{

51	if(graf[wiersz][i]!=0)//jezeli nie ma polaczenia z wierzcholkien to nie
wchodz
52	{
53	if(odwiedzone[i]==0)// jezeli byl odiweczony to nie wchodz
54	{
55	if(waga[i]>graf[wiersz][i])// jezeli jest droga o mniejszym
koszcie to nie wchodz
56	{
57	waga[i]=graf[wiersz][i]; // znaleziono najtansza droge,
podmiana za wczesniejsza
58	}
59	}
60	}

61 }

62

63koszt=MX; // maksymalny koszt

64for(int i=1; i<=n; i++) // zanotowanie wagi w tabilcy

65{

66	if(odwiedzone[i]==0) // sprawdzenie czy byl odwiedzony
67	{
68	if(waga[i]<koszt) // sprawdzenie czy waga jest nizsza od maxa
69	{
70	koszt=waga[i]; // ustawienie nowej wagi jako koszt
71	wiersz=i; // ustawienie wiersza w ktorym zmienilem wage
72	}
73	}
74	}
75

76odwiedzone[wiersz]=1; // odwiedzony wierzcholek

77wierzcholki++; // przechodzimy do nstepnego wierzcholka

78}

79

80koszt=0; //koszty na poczatku rowne zero

81for(int i=1; i<=n; i++) // dodaje wagi

82{

83koszt+=waga[i]; //suma wag

84}

85

86 cout<<"koszt = "<<koszt<<endl; //wypisanie an ekran 87

88return 0;

89}