Zaimplementowany Algorytm. Problem Z Tablicami.

[The_Structor]

#include <iostream>#include <stdlib.h>#include <conio.h>using namespace std;int **graf;int **krawedzie;int *wagi;int *zbiory;int **drzewo;int ilosc_wierzcholkow, ilosc_krawedzi, n;int partition (int p, int k){        int x = wagi [p];        int i = p - 1;        int j = k + 1;        int z;        while (i < j)        {                do                {                        j--;                }                while (wagi[j] > x);                do                {                        i++;                }                while (wagi[i] < x);                if (i < j)                {                        z = wagi [i];                        wagi [i] = wagi [j];                        wagi [j] = z;                        z = krawedzie [i][0];                        krawedzie [i][0] = krawedzie [j][0];                        krawedzie [j][0] = z;                        z = krawedzie [i][1];                        krawedzie [i][1] = krawedzie [j][1];                        krawedzie [j][1] = z;                }        }        return j;}void quicksort (int p, int k){        int q;        if (p < k)        {                q = partition (p, k);                quicksort (p, q);                quicksort (q + 1, k);        }}int find (int a){    return zbiory [a];}int unionn (int a, int b){    int i, x = zbiory [b];    for (i = 0; i < ilosc_wierzcholkow; i++)    {        if (zbiory [i] == x)            zbiory [i] = zbiory [a];    }}void kruskal (){    int i, licznik = 0;      for (i = 0; i < ilosc_wierzcholkow - 1; i++)    {        drzewo [i][0] = -1;        drzewo [i][1] = -1;    }      for (i = 0; i < ilosc_wierzcholkow; i++)        zbiory [i] = i;    quicksort (0, ilosc_krawedzi - 1);    for (i = 0; i < ilosc_krawedzi; i++)    {        if (find (krawedzie [i][0]) != find (krawedzie [i][1]))        {                drzewo [licznik][0] = krawedzie [i][0];                drzewo [licznik][1] = krawedzie [i][1];                unionn (krawedzie [i][0], krawedzie [i][1]);                licznik ++;        }    }}int main () {    int i,j,licznik=0,n;    cout << "Podaj ilosc wierzcholkow w grafie:\n";    cin >> n;    ilosc_wierzcholkow = n;    graf = new int * [n];    for (i=0; i<n; i++) {        graf[i] = new int [n];    }    krawedzie = new int * [2];    for (i=0; i<n; i++) {        krawedzie[i]=new int[2];    }      wagi=new int[n*n];    zbiory=new int[n];    drzewo=new int * [2];    for (i=0; i<n-1; i++) {        drzewo[i]=new int[2];    }      cout << "Podaj odleglosci pomiedzy poszczegolnymi wierzcholkami, jesli nie wystepuje krawedz to wpisz:-1\n";    for (i=0; i<n; i++) {        for (j=0; j<n; j++) {            cout << "Odleglosc od wierzcholka " << i+1 << " do " << j+1 << " = ";            cin >> graf[i][j];        }    }        for (i = 0; i < n; i++) {        licznik =0;        for (j = 0; j < n; j++) {            if (graf[i][j] > -1)            {                krawedzie [licznik][0] = i;                krawedzie [licznik][1] = j;                wagi [licznik] = graf[i][j];                licznik++;            }        }    }                ilosc_krawedzi = licznik;    kruskal ();      cout << "Wierzcholki nalezace do Minimalnego drzewa rozpinajacego:\n\n";    for (i = 0; i < n - 1; i++) {        cout << "\n" <<  drzewo [i][0] << " " << drzewo [i][1] << "\n";    }      for(i=0;i<n;i++) {        delete [] graf[i];    }                  delete [] graf;      for (i=0; i<2; i++) {        delete [] krawedzie[i];    }      delete [] krawedzie;    delete [] wagi;    delete []zbiory;    for (i=0; i<2; i++) {        delete [] drzewo[i];    }      delete [] drzewo;              system ("pause");    return 0;}

 

Program dziala jedynie dla dwoch wierzcholkow, jak podam wiecej to juz kupa :(. Mialem napisac algorytm Kruskala... Ale to akurat malo wazne, bo algorytm niby zaimplementowany, tylko ten "segmentation fault" ;/

Dzieki wszystkim za pomoc - probowalem wszystkiego ale nie moge sobie poradzic :(.

Edytowane 31 Stycznia 2005 przez The_Structor