Facebook
From Sweltering Human, 5 Years ago, written in C++.
Embed
Download Paste or View Raw
Hits: 226
  1. #pragma once
  2. #include "Wierzcholek.h"
  3. #include "Krawedz.h"
  4.  
  5. class Graf
  6. {
  7. public:
  8.         Graf(const int ile);
  9.         void UstawGraf(int **MS,const int n);
  10.         void DFS(int v,  int &skladowa);
  11.         void UstawNieodwiedzone();
  12.         int CzyOdwiedzony(const int i);
  13.         void Zwolni();
  14.         void Ponumeruj();
  15.         void UstawLiczbeKrawedzi(const int l);
  16.         void UstawWszystko(int **MI,int n, int l);
  17.         void Wypisz();
  18.         void Dijkstra(int s, int **wagi);
  19.         void InitG(int s, int rozmiar);
  20.         int Minimum();
  21.         void Relax(int u, int v, int w);
  22.         void Wypisz_d_p();
  23.         int **ZwrocWagi();
  24.         void ADD_S();
  25.         bool Bellman_Ford(int **wagi,int zrodlo);
  26.         void Johnson();
  27.         void Kruskal(int **MI,int l);
  28.         void make(int x);
  29.         void polacz(int x, int y);
  30.         int znajdz_i_ustaw(int x);
  31.         ~Graf();
  32.         static bool wypisz;
  33. private:
  34.         //Glowny graf
  35.         std::vector<Wierzcholek> G_graf;
  36.         //Graf o jeden wierzcholek wiekszy od G_graf uzywany w Johnosnie
  37.         std::vector<int> G_prim;
  38.         //Wektor wag
  39.         std::vector<int> d;
  40.         //Wektor wag, uzywany w Johnsoie
  41.         std::vector<int> d_prim;
  42.         //to w suemie nie jest potrzebne
  43.         std::vector<int> p_prim;
  44.         //Wektor poprzedikow
  45.         std::vector<int> p;
  46.         //Wektor gotowych wierzcholow w algorytmie Dijkstry
  47.         //(tego szpiega z Wiedzmina)
  48.         std::vector<int> S;
  49.         //Wektor wierzcholkow ktore jescze musimy odwiedzic (do algorytmu Dijkstry)
  50.         std::vector<int> Niegotowe;
  51.         //wektor reprezentantow danego wierzcholka
  52.         std::vector<int> ojciec;
  53.         //okresla ilosc zbiorow polaczonych
  54.         std::vector<int> ranga;
  55.         //tablica wag laczacych dana krawedz
  56.         int **G_wagi;
  57.         //tablica wag dla grafu G_prim
  58.         int **G_wagi_prim;
  59.         //std::vector<Krawedz> G_krawedz;
  60.         //rozmiar oryginalnego grafu
  61.         int G_rozmiar;
  62.  
  63.         //int G_rozmiarK;
  64.  
  65. };
  66.  
  67.  
  68.  
  69.  
  70.   ///////////////////////////////////////  
  71.  
  72.   ////////////////////////////////////
  73.  
  74.   ////////////////////////////////////
  75.  
  76.   ////////////////////////////////////
  77.  
  78.  
  79.   #include "Graf.h"
  80. #include <limits>
  81. //Zmienna uzywana w algorytmie DIjkstry(uzywamy go wieloktornie,
  82. //a chcemy wypisac dane tyklko do zad2)
  83. bool Graf::wypisz = true;
  84.  
  85. //Konstukotr ustaiwajacy rozmiar grafu
  86. Graf::Graf(const int ile)
  87. {
  88.         G_graf.resize(ile);
  89.         G_rozmiar = ile;
  90. }
  91.  
  92. //Szukamy spojnej skladowej
  93. void Graf::DFS(int v,int &skladowa)
  94. {
  95.         G_graf[v].W_skladowa = skladowa;
  96.         G_graf[v].W_odwiedzony = 1;
  97.         for(int i = 0; i < G_graf[v].W_ilosc_sasiadow; i++)
  98.         {
  99.                 if(G_graf[v].W_sasiedzi[i]->W_odwiedzony == -1)
  100.                 {
  101.                         G_graf[v].W_sasiedzi[i]->WDFS(i,skladowa);
  102.                 }
  103.         }
  104. }
  105.  
  106. //Do ustawiania ze kazdy wierzcholek jest nieodiwedziony
  107. void Graf::UstawNieodwiedzone()
  108. {
  109.         for(int i = 0; i < G_rozmiar; i++)
  110.         {
  111.                 G_graf[i].W_odwiedzony = -1;
  112.         }
  113. }
  114.  
  115. //Ustawia graf wedlug macierzy sasiedztaw, n - liczba wierzcholkow
  116. void Graf::UstawGraf(int **MS, const int n)
  117. {
  118.         for(int i = 0; i < n; i++)
  119.         {
  120.                 int ilosc = 0;
  121.                 for (int j = 0; j< n; j++)
  122.                 {
  123.                         if(MS[i][j] == 1) ilosc++;
  124.                 }
  125.                 G_graf[i].W_sasiedzi = new Wierzcholek *[ilosc];
  126.                 G_graf[i].W_ilosc_sasiadow = ilosc;
  127.                 G_graf[i].W_free = 1;
  128.         }
  129.  
  130.  
  131.         for(int i = 0; i < n; i++)
  132.         {
  133.                 int k = 0;
  134.                 for (int j = 0; j< n; j++)
  135.                 {
  136.                         if(MS[i][j] == 1)
  137.                         {
  138.                                 G_graf[i].W_sasiedzi[k] = &G_graf[j];
  139.                                 k++;
  140.                         }
  141.                 }
  142.         }
  143. }
  144.  
  145.  
  146. //Sprawdza czy dany wierzcholek jest odwiedzony
  147. int Graf::CzyOdwiedzony(const int i)
  148. {
  149.         return G_graf[i].W_odwiedzony;
  150. }
  151.  
  152. //Main.cpp
  153. void Graf::Zwolni()
  154. {
  155.         for(int i = 0; i < G_rozmiar; i++)
  156.         {
  157.                 if(G_graf[i].W_free) delete [] G_graf[i].W_sasiedzi;
  158.         }
  159. }
  160.  
  161. //Numeruje wierzcholki od 0!
  162. void Graf::Ponumeruj()
  163. {
  164.         for(int i = 0; i < G_rozmiar; i++)
  165.         {
  166.                 G_graf[i].W_nr_wierzcholka = i;
  167.         }
  168. }
  169.  
  170. //Ustawia wagi i sasiadow kazdego wierzcholka
  171. void Graf::UstawWszystko(int **MI,int n, int l)
  172. {
  173.         for(int i = 0; i < l; i++)
  174.         {
  175.                 for(int j = 0; j < n; j++)
  176.                 {
  177.                         if(MI[j][i] != 0)
  178.                         {
  179.                                 G_graf[j].W_waga.push_back(MI[j][i]);
  180.                         }
  181.                 }
  182.         }
  183.  
  184.         G_wagi = new int *[n];
  185.         for(int i = 0; i < n; i++)
  186.         {
  187.                 G_wagi[i] = new int [n];
  188.                 for(int j = 0; j< n; j++)
  189.                 {
  190.                         G_wagi[i][j] = 0;
  191.                 }
  192.                 G_wagi[i][i] = 0;
  193.         }
  194.  
  195.         for(int i = 0; i < G_rozmiar; i++)
  196.         {
  197.                 for(int j = 0; j < G_graf[i].W_ilosc_sasiadow; j++)
  198.                 {
  199.                         G_wagi[i][G_graf[i].W_sasiedzi[j]->W_nr_wierzcholka] = G_graf[i].W_waga[j];
  200.                 }
  201.         }
  202.  
  203.         std::cout<<"\nMACIERZ WAG\n";
  204.         for(int i = 0; i < n; i++)
  205.         {
  206.                 for(int j = 0; j < n; j++)
  207.                 {
  208.                         std::cout<<G_wagi[i][j];
  209.                         if(G_wagi[i][j] >= 10 || G_wagi[i][j] < 0) std::cout<<" ";
  210.                         else std::cout<<"  ";
  211.                 }
  212.                 std::cout<<"\n";
  213.         }
  214.  
  215.         std::cout<<"\n\n";
  216.  
  217. }
  218.  
  219. //Wypisuje dane w formie NR_wierzcholka: NR_sasiada(waga_krawedzi)
  220. void Graf::Wypisz()
  221. {
  222.         for(int i = 0; i < G_rozmiar; i++)
  223.         {
  224.                 std::cout<<G_graf[i].W_nr_wierzcholka<<": ";
  225.                 for(int j = 0; j < G_graf[i].W_ilosc_sasiadow; j++)
  226.                 {
  227.                         std::cout<<G_graf[i].W_sasiedzi[j]->W_nr_wierzcholka<<"("<<G_graf[i].W_waga[j]<<")";
  228.                         if(j != G_graf[i].W_ilosc_sasiadow -1) std::cout<<", ";
  229.                 }
  230.                 std::cout<<"\n";
  231.         }
  232. }
  233.  
  234. int** Graf::ZwrocWagi()
  235. {
  236.         return G_wagi;
  237. }
  238.  
  239. //Alorytm do zestawu 3
  240. //iniciuje tablice(vector) wag i poprzednikow
  241. void Graf::InitG(int s, int rozmiar)
  242. {
  243.         d.resize(G_rozmiar);
  244.         d_prim.resize(rozmiar);
  245.         p_prim.resize(rozmiar);
  246.         p.resize(G_rozmiar);
  247.         for(int i = 0; i < G_rozmiar; i++)
  248.         {
  249.                 d[i] = std::numeric_limits<int>::max();
  250.                 p[i] = -1;
  251.                 d_prim[i] = std::numeric_limits<int>::max();
  252.                 p_prim[i] = -1;
  253.         }
  254.         if(s < G_rozmiar)
  255.                 d[s] = 0;
  256.  
  257.         d_prim[s] = 0;
  258.         if(rozmiar > G_rozmiar) d_prim[G_rozmiar] = 0;
  259. }
  260.  
  261. //Wyszukuje minimum w vectorze d w tych wierzcholkach
  262. //ktore jeszcze sa nieodowiedzone (Przechowywane w tablicy Niegotowe)
  263. int Graf::Minimum()
  264. {
  265.         //Inicjalizacja minimum i numeru indeksu pod ktorym sie to minimum znajduej
  266.         int min = std::numeric_limits<int>::max();
  267.         int index= - 1;
  268.         for(int i = 0; i < G_rozmiar; i++)
  269.         {
  270.                 bool test = false;
  271.                 if(min > d[i])
  272.                 {
  273.                         for(int j = 0; j < G_rozmiar; j++)
  274.                         {
  275.                                 //Jesli znalezlismy wierzcholek nieodiwedzony(o numerze i)
  276.                                 if(i == Niegotowe[j])
  277.                                 {
  278.                                         test = true;
  279.                                         break;
  280.                                 }
  281.                         }
  282.                         //to zmieniamy minimum
  283.                         //i ustalami pod ktorym indeksem sie zajduje
  284.                         if(test)
  285.                         {
  286.                                 min = d[i];
  287.                                 index = i;
  288.                         }
  289.                 }
  290.         }
  291.         //tu zmieniami wartosc w tablicy NIegotowe aby miec pewnosc, ze
  292.         //juz nie zostanie ponownie uzyta
  293.         if(index != -1) Niegotowe[index] = std::numeric_limits<int>::max();
  294.         return index;
  295. }
  296.  
  297. //Relaksacja krawedzi
  298. //u - poprzednik
  299. //v - obecny wierzcholek
  300. //w - waga krawedzi u--v
  301. void Graf::Relax(int u, int v, int w)
  302. {
  303.         //Sprawdzamy czy obecny koszt jest wiekszy od nowego
  304.         // jesli tak to zaminiemy i zmieniamy poprzednika
  305.         if(d[v] > d[u] + w)
  306.         {
  307.                 d[v] = d[u] + w;
  308.                 p[v] = u;
  309.         }
  310.         if(d_prim[v] > d_prim[u] + w)
  311.         {
  312.                 d_prim[v] = d_prim[u] + w;
  313.                 //p[v] = u;
  314.         }
  315. }
  316.  
  317. //Wypisuje wektor d - koszt, p -poprzezdnik
  318. void Graf::Wypisz_d_p()
  319. {
  320.         for(int i = 0; i < G_rozmiar; i++)
  321.                 std::cout<<"d("<<i<<")"<<"="<<d[i]<<"\n";
  322.         std::cout<<"\n\n";
  323.         for(int i = 0; i < G_rozmiar; i++)
  324.                 std::cout<<"p["<<i<<"]"<<" = "<<p[i]<<"\n";
  325. }
  326.  
  327. //ALgorytm Dijkstry
  328. void Graf::Dijkstra(int s,int **wagi)
  329. {
  330.         //Inicjalizacja wektorow d i p
  331.         InitG(s,G_rozmiar);
  332.         if(int(Niegotowe.size()) > 0) Niegotowe.resize(0);
  333.         if(int(S.size()) > 0) S.resize(0);
  334.         //Wstawiamy do Niegotwoe numer kazdego wierzcholka
  335.         for(int i = 0; i < G_rozmiar; i++)
  336.         {
  337.                 Niegotowe.push_back(i);
  338.                 //std::cout<<Niegotowe[i]<<" ";
  339.         }
  340.         //std::cout<<"\n";
  341.         //Dopkoki S nie zawiera wszystkich wierzcholkow
  342.         while (int(S.size()) != G_rozmiar)
  343.         {
  344.                 //Szukamu indeksu minimum(rownoczesnie numer wierzcholka)
  345.                 int u = Minimum();
  346.                 //std::cout<<"u="<<u<<"\n";
  347.                 //Wstawiamu gotowy numer do S
  348.                 S.push_back(u);
  349.                 std::vector<int> Sasiedzi;
  350.                 for(int i = 0; i < G_graf[u].W_ilosc_sasiadow; i++)
  351.                 {
  352.                         bool sprawdz = true;
  353.                         //W sumie nie pamietam co to mialo robic
  354.                         //ale cos waznego
  355.                         //jak sobie przypomne do dopisze
  356.                         //a tak zostawiam dla waszej interpretacji
  357.                         for(int j = 0; j < int(S.size()); j++)
  358.                         {
  359.                                 //std::cout<<S[j]<<"-"<<G_graf[u].W_sasiedzi[i]->W_nr_wierzcholka<<" ";
  360.                                 if(S[j] == G_graf[u].W_sasiedzi[i]->W_nr_wierzcholka)
  361.                                 {
  362.                                         sprawdz = false;
  363.                                         break;
  364.                                 }
  365.                         }
  366.                         if(sprawdz) Sasiedzi.push_back(G_graf[u].W_sasiedzi[i]->W_nr_wierzcholka);
  367.                 }
  368.  
  369.                 //Obliczamy koszty do wszystkich sasiadow daneg wierzcholka u
  370.                 for(int i = 0; i < int(Sasiedzi.size()); i++)
  371.                 {
  372.                         int v = Sasiedzi[i];
  373.                         Relax(u,v,wagi[u][v]);
  374.                 }
  375.                 //Wypisz_d_p();
  376.         }
  377.  
  378.         //std::cout<<"\nOSTATECZNIE\n";
  379.  
  380.         //Wypisujemu tablice d i p
  381.         //drogi do kazdego wierzcholka(od wierzcholka zrodlowego s)
  382.         //i ich koszty
  383.         if(wypisz)
  384.         {
  385.                 Wypisz_d_p();
  386.                 wypisz = false;
  387.                 std::cout<<"\n";
  388.                 for(int i = 0; i < G_rozmiar; i++)
  389.                 {      
  390.                         int new_i = i;
  391.                         std::cout<<i<<"<--";
  392.                         while(new_i != s)
  393.                         {
  394.                                 new_i = p[new_i];
  395.                                 std::cout<<new_i;
  396.                                 if(new_i != s) std::cout<<"<--";
  397.  
  398.                         }
  399.                         std::cout<<"  koszt: "<<d[i]<<"\n";
  400.                 }
  401.         }
  402. }
  403.  
  404. //Sluzy do ustawiania nowego grafu ktory zaweiera staary graf
  405. // powiekszony o 1 wierzcholek ktory jest polaczony krawedzia o koszcie 0
  406. // z kazdym innym wierzcholkiem grafu
  407. void Graf::ADD_S()
  408. {
  409.         for(int i = 0; i <= G_rozmiar; i++)
  410.         {
  411.                 G_prim.push_back(i);
  412.         }
  413.  
  414.         G_wagi_prim = new int *[int(G_prim.size())];
  415.         for(int i = 0; i < int(G_prim.size());i++)
  416.         {
  417.                 G_wagi_prim[i] = new int[int(G_prim.size())];
  418.                 for(int j = 0; j < int(G_prim.size()); j++)
  419.                 {
  420.                         G_wagi_prim[i][j] = 0;
  421.                 }
  422.         }
  423.  
  424.         for(int i = 0; i < G_rozmiar; i++)
  425.         {
  426.                 for(int j = 0; j < G_rozmiar; j++)
  427.                 {
  428.                         G_wagi_prim[i][j] = G_wagi[i][j];
  429.                 }
  430.         }
  431.  
  432. }
  433.  
  434. //Sluzy do sprawdzania czy jest ujemna waga w grafie
  435. //jesli tak do wyrzca false
  436. bool Graf::Bellman_Ford(int **wagi,int zrodlo)
  437. {
  438.         int rozmiar = (G_prim.size());
  439.         InitG(zrodlo,rozmiar);
  440.         for(int i = 0; i < rozmiar - 1;i++)
  441.         {
  442.                 for(int u = 0; u < rozmiar - 1; u++)
  443.                 {
  444.                         for(int v = 0; v< rozmiar - 1; v++)
  445.                         {
  446.                                 if(wagi[u][v] != 0)
  447.                                 {
  448.                                         Relax(u,v,wagi[u][v]);
  449.                                 }
  450.                         }
  451.                 }
  452.         }
  453.  
  454.         for(int  u = 0; u< rozmiar - 1; u++)
  455.         {
  456.                 for(int v = 0; v < rozmiar - 1; v++)
  457.                 {
  458.                         if(wagi[u][v] != 0)
  459.                         {
  460.                                 if(d_prim[v] > d_prim[u] + wagi[u][v]) return false;
  461.                         }
  462.                 }
  463.         }
  464.  
  465.         return true;
  466. }
  467.  
  468. //Sluzy do wyznaczania macierzy odleglosci
  469. //zobaczcie na algorytmy ze strony Pani Wach
  470. void Graf::Johnson()
  471. {
  472.         ADD_S();
  473.         std::vector<int> h;
  474.         int rozmiar = int(G_prim.size());
  475.         bool tryb = Bellman_Ford(G_wagi,G_rozmiar);
  476.         //Jesli nie ma ujemnej krawdzi
  477.         if(tryb)
  478.         {
  479.                
  480.                 for(int i = 0; i < rozmiar; i++)
  481.                 {
  482.                         h.push_back(d_prim[i]);
  483.                 }
  484.                 for( int u = 0; u < rozmiar; u++)
  485.                 {
  486.                         for(int v = 0; v < rozmiar; v++)
  487.                         {
  488.                                 if(G_wagi_prim[u][v] != 0)
  489.                                 {
  490.                                         G_wagi_prim[u][v] = G_wagi[u][v] + h[u] - h[v];
  491.                                 }
  492.                         }
  493.                 }
  494.                 //D - macierz odleglosci
  495.                 int **D = new int *[G_rozmiar];
  496.                 for(int i = 0; i < G_rozmiar; i++)
  497.                 {
  498.                         D[i] = new int [G_rozmiar];
  499.                 }
  500.  
  501.                 for(int u = 0; u < G_rozmiar; u++)
  502.                 {
  503.                         Dijkstra(u,G_wagi_prim);
  504.                         for(int v= 0; v < G_rozmiar; v++)
  505.                         {
  506.                                 D[u][v] = d[v] - h[u] + h[v];
  507.                         }
  508.                 }
  509.  
  510.                 std::cout<<"\nMacierz odleglosci\n";
  511.                 for(int i = 0; i < G_rozmiar; i++)
  512.                 {
  513.                         for (int j = 0; j < G_rozmiar; j++)
  514.                         {
  515.                                 std::cout<<D[i][j];
  516.                                 if(D[i][j] >= 10) std::cout<<" ";
  517.                                 else std::cout<<"  ";
  518.                         }
  519.                         std::cout<<"\n";
  520.                 }
  521.                 //Szukamu centrum grafu tj. wierzcholka dla ktorego suma
  522.                 //wag w wierszu macierzy D jest najmniejsza
  523.                 int min = std::numeric_limits<int>::max();
  524.                 int centrum_grafu;
  525.  
  526.                 for(int i = 0; i < G_rozmiar; i++)
  527.                 {
  528.                         int suma = 0;
  529.                         for(int j = 0; j < G_rozmiar; j++)
  530.                         {
  531.                                 suma += D[i][j];
  532.                         }
  533.                         if(suma < min)
  534.                         {
  535.                                 min = suma;
  536.                                 centrum_grafu = i;
  537.                         }
  538.                 }
  539.  
  540.                 std::cout<<"\nCentrum grafu: "<<centrum_grafu<<"\n\n";
  541.  
  542.                 //Szukamy wierzcholka minmax.
  543.                 //do wektora minmax zapisujemy kolejno najwieksze wagi z kazdego wiersza
  544.                 //indeks pod ktorym znajduje sie najmniejsza waga w wektorze minmax jest naszym
  545.                 //szukanym wierzcholkiem
  546.                 std::vector<int> minmax;
  547.                 minmax.resize(G_rozmiar);
  548.  
  549.                 for(int i = 0; i < G_rozmiar; i++)
  550.                 {
  551.                         int max = D[i][0];
  552.                         minmax[i] = max;
  553.                         for(int j = 1; j < G_rozmiar; j++)
  554.                         {
  555.                                 if(max < D[i][j])
  556.                                 {
  557.                                         max = D[i][j];
  558.                                         minmax[i] = max;
  559.                                 }
  560.                         }
  561.                         //std::cout<<minmax[i]<<" ";
  562.                 }
  563.                 min = minmax[0];
  564.                 int idx = 0;
  565.                 for( int i = 1; i < G_rozmiar; i++)
  566.                 {
  567.                         if(min > minmax[i])
  568.                         {
  569.                                 min = minmax[i];
  570.                                 idx = i;
  571.                         }
  572.                 }
  573.  
  574.                 std::cout<<"\nCentrum minimax: "<<idx<<"\n";
  575.  
  576.                 for(int i = 0; i < G_rozmiar; i++)
  577.                 {
  578.                         delete [] D[i];
  579.                 }
  580.                 delete [] D;
  581.         }
  582.         else
  583.         {
  584.                 std::cout<<"\n Graf zawiera krawedz o ujemnej wadze.\n";
  585.                 exit(-1);
  586.         }
  587.  
  588.        
  589. }
  590.  
  591. //Ustawiamy, ze reprezentantem kazdego wierzcholka jest od sam
  592. //wiec mamy las w ktorym znajduja sie wszystkie nasze wierzcholki
  593. //kazdy jest osobnym grafem
  594. void Graf::make(int x)
  595. {
  596.         ojciec[x] = x;
  597.         ranga[x] = 0;
  598. }
  599.  
  600. //Laczymy dwa wierzcholki
  601. //Jesli x nie jest reprezentantem swojego zbioru (wczesniej juz byl polaczony z innym wierzcholkiem)
  602. //to y staje sie tez czescia tego zbioru
  603. //w przeciwnym wypadku to x staje sie czescia zbioru do ktorego nalezy y
  604. void Graf::polacz(int x, int y)
  605. {
  606.         x = znajdz_i_ustaw(x);
  607.         y = znajdz_i_ustaw(y);
  608.         if(ranga[x] > ranga[y])
  609.         {
  610.                 ojciec[y] = x;
  611.         }
  612.         else
  613.         {
  614.                 ojciec[x] = y; 
  615.         }
  616.         if(ranga[x] == ranga[y]) ranga[y]++;
  617.  
  618. }
  619.  
  620. //Szukamy reprezentanta zbioru do ktorego nalezy x
  621. int Graf::znajdz_i_ustaw(int x)
  622. {
  623.         if(x != ojciec[x])
  624.         {
  625.                 ojciec[x] = znajdz_i_ustaw(ojciec[x]);
  626.         }
  627.  
  628.         return  ojciec[x];
  629. }
  630.  
  631. //Szukamy najmniejszego drzewa rozpinajacego
  632. //MI -macierz incydencji
  633. //l - liczba krawdzi
  634. void Graf::Kruskal(int **MI, int l)
  635. {      
  636.         //Tworzymy l tablic 3 elementowych
  637.         //[i][0] - waga danej krawedzi
  638.         //[i][1], [i][2] - numery wierzcholkow, ktore dana krawedz laczy
  639.         int **krawedzie = new int *[l];
  640.         for(int i = 0; i < l; i++)
  641.         {
  642.                 krawedzie[i] = new int [3];
  643.         }
  644.  
  645.         //Tu uzupelniamy tablice krawedzi danymi z macierz MI
  646.         for(int i = 0; i < l; i++)
  647.         {
  648.                 bool sprawdz = true;
  649.                 for(int j = 0; j < G_rozmiar; j++)
  650.                 {
  651.                         if(MI[j][i] != 0)
  652.                         {
  653.                                 if(sprawdz)
  654.                                 {
  655.                                         krawedzie[i][0] = MI[j][i];
  656.                                         krawedzie[i][1] = j;
  657.                                         sprawdz = false;
  658.                                 }
  659.                                 else
  660.                                 {
  661.                                         krawedzie[i][2] = j;
  662.                                 }
  663.                         }
  664.                 }
  665.         }
  666.        
  667.         //Sortujemy krawedzie wedlug wag
  668.         for(int i = 0; i < l-1; i++)
  669.         {
  670.                 int index = i;
  671.                 int min = krawedzie[i][0];
  672.                 for(int j = i+1; j < l; j++)
  673.                 {
  674.                         if(min > krawedzie[j][0])
  675.                         {
  676.                                 min = krawedzie[j][0];
  677.                                 index = j;
  678.                         }
  679.                 }
  680.  
  681.                 if(index != i)
  682.                 {
  683.                         int waga = krawedzie[i][0];
  684.                         int v1 = krawedzie[i][1];
  685.                         int v2 = krawedzie[i][2];
  686.                         krawedzie[i][0] = krawedzie[index][0];
  687.                         krawedzie[i][1] = krawedzie[index][1];
  688.                         krawedzie[i][2] = krawedzie[index][2];
  689.                         krawedzie[index][0] = waga;
  690.                         krawedzie[index][1] = v1;
  691.                         krawedzie[index][2] = v2;
  692.                 }
  693.         }
  694.  
  695.         ojciec.resize(G_rozmiar);
  696.         ranga.resize(G_rozmiar);
  697.  
  698.         for(int i = 0; i< G_rozmiar; i++) make(i);
  699.  
  700.  
  701.         //Algorytm do wyznaczania minimalnego drzewa rozpinajacego
  702.         //zobaczcie czy to rzzeczywiscie dziala
  703.         //troche zmienialem przy tym i wydaje sie ok
  704.         //ale tak dla pewnosci to mozecie odpalic program
  705.         //i zobaczyc czy rzeczywiscie laczy prawidlowo
  706.         std::vector<int> T;
  707.         //Wektor W chyba jest juz nie potrzebny
  708.         //ale zostawiam jak cos nie bezdie dzialalo to mam drugi pomysl
  709.         //do ktorego go wykorzystam
  710.         std::vector<int> W;
  711.         for(int i = 0; i < G_rozmiar; i++) W.push_back(1);
  712.         for(int i = 0; i < l; i++)
  713.         {
  714.                 //Szukamy reprezentantow danych wierzcholkow
  715.                 //jesli sa rozne to znaczy ze nie moze powstac cykl
  716.                 //wiec mozemy taka krawedz dodac
  717.                 int u = znajdz_i_ustaw(krawedzie[i][1]);
  718.                 int v = znajdz_i_ustaw(krawedzie[i][2]);
  719.                 if(u != v)
  720.                 {
  721.                         T.push_back(krawedzie[i][1]);
  722.                         T.push_back(krawedzie[i][2]);
  723.                         polacz(krawedzie[i][1],krawedzie[i][2]);
  724.                         W[krawedzie[i][1]] = 0;
  725.                         W[krawedzie[i][2]] = 0;
  726.                 }
  727.                 //bool wszystkie = false;
  728.                 //int sum = 0;
  729.                 //for(int k = 0; k < G_rozmiar; k++) sum += W[k];
  730.                 //if(sum == 0) wszystkie = true;
  731.                 if(int(T.size())/2 == G_rozmiar - 1 /*&& wszystkie*/) break;
  732.         }
  733.  
  734.         for(int i = 0; i < l; i++)
  735.         {
  736.                 for(int j = 0; j < 3; j++)
  737.                         std::cout<<krawedzie[i][j]<<" ";
  738.                 std::cout<<"\n";
  739.         }
  740.         for(int i = 0; i < G_rozmiar; i++) std::cout<<ojciec[i]<<" ";
  741.                 std::cout<<"\n";
  742.         for(int i = 0; i < G_rozmiar; i++)
  743.                 std::cout<<ranga[i]<<" ";
  744.  
  745.         std::cout<<"\n\nMinimalne drzewo rozpinajace\n";
  746.         for(int i = 0; i < int(T.size()); i+= 2)
  747.         {
  748.                 std::cout<<T[i]<<" "<<T[i+1]<<"\n";
  749.         }
  750.  
  751.         for(int i = 0; i < l; i++)
  752.                 delete [] krawedzie[i];
  753.         delete [] krawedzie;
  754. }
  755.  
  756.  
  757. Graf::~Graf()
  758. {
  759.         for(int i = 0; i < G_rozmiar; i++)
  760.         {
  761.                 delete [] G_graf[i].W_sasiedzi;
  762.                 delete [] G_wagi[i];
  763.                 delete [] G_wagi_prim[i];
  764.         }
  765.         delete [] G_wagi_prim[G_rozmiar];
  766.         delete [] G_wagi;
  767.         delete [] G_wagi_prim;
  768. }