Kruskalov algoritem/Kopica

Iz MaFiRaWiki

  1. public class Kopica {
  2. /*
  3. Razred Kopica - KOPICA iz povezav JE PREDSTAVLJENA S TABELO, za n podatkov potrebujemo
  4. tabelo dolzine 3n, ker vanjo zapored zapisujeo ceno in obe krajisci povezave.
  5. */
  6.  
  7. private int[][] kop; //tabela, ki predstavlja kopico
  8. private int m; //velikost kopice
  9.  
  10. //konstruktorji:
  11.  
  12. public Kopica(int velikost) { //naredi prazno kopico dane velikosti
  13. kop = new int[velikost][3];
  14. m = velikost;
  15. }
  16.  
  17. public Kopica(int[][] matrika){
  18. //zlozi elemente iz matrike n*n v kopico
  19.  
  20. int n = matrika.length;
  21. //velikost kopice, stevilo povezav v zgornjitrikotni matriki
  22. m = n * (n - 1) / 2;
  23. kop = new int[m][3];
  24. //stevec v kopici
  25. int k = 0;
  26. for (int i = 0; i < n; i++) {
  27. for (int j = i + 1; j < n; j++) {
  28. kop[k][0] = matrika[i][j];
  29. kop[k][1] = i;
  30. kop[k][2] = j;
  31. k++;
  32. }
  33. }
  34. //dejanska velikost kopice
  35. m = k;
  36. narediKopico();
  37. } //konstruktor
  38.  
  39. public Kopica(int[][] matrika, int neskoncno){
  40. //zlozi elemente iz matrike n*n v kopico, elemente, ki imajo vrednost neskoncno, izloci
  41.  
  42. int n = matrika.length;
  43. //max velikost kopice, povezav bo najvec toliko
  44. m = n * (n - 1) / 2;
  45. kop = new int[m][3];
  46. //stevec v kopici
  47. int k = 0;
  48. for (int i = 0; i < n; i++) {
  49. for (int j = i + 1; j < n; j++) {
  50. //neskoncne povezave takoj izlocimo, da bo manj dela
  51. if (matrika[i][j] < neskoncno) {
  52. kop[k][0] = matrika[i][j];
  53. kop[k][1] = i;
  54. kop[k][2] = j;
  55. k++;
  56. }
  57. }
  58. }
  59. //dejanska velikost kopice
  60. m = k;
  61. narediKopico();
  62. } //konstruktor
  63.  
  64. //druge metode:
  65.  
  66. public int[] povejVrh() {
  67. int[] r = new int[3];
  68. r[0] = kop[0][0];
  69. r[1] = kop[0][1];
  70. r[2] = kop[0][2];
  71. return r;
  72. }
  73.  
  74. public int[] povejZadnjega() {
  75. int[] r = new int[3];
  76. r[0] = kop[m-1][0];
  77. r[1] = kop[m-1][1];
  78. r[2] = kop[m-1][2];
  79. return r;
  80. }
  81.  
  82. public void spremeniVrh(int[] podatek) {
  83.  
  84. if(podatek.length != 3) System.out.println("Napaka!");
  85. //s preverjanjem podatkov se sicer nisem ukvarjala, marsikje bi morali biti
  86. // podobni "lovilci"
  87. else {
  88. kop[0][0] = podatek[0];
  89. kop[0][1] = podatek[1];
  90. kop[0][2] = podatek[2];
  91. }
  92. }
  93.  
  94. public void brisi() {
  95.  
  96. //zadnjega premaknemo na vrh, nato ga potopimo
  97. spremeniVrh(povejZadnjega());
  98. m--;
  99. popraviKopico(0);
  100. }
  101.  
  102. /*
  103. najbolj pomembni metodi,
  104. s prvo naredimo kopico, z drugo pa vzdrzujemo strukturo kopice pri vstavljanju
  105. ali brisanju
  106. */
  107.  
  108. public void narediKopico(){
  109. //iz neurejene tabele naredi kopico
  110.  
  111. for (int k = m - 1; k >= 0; k--) {
  112. if (kop[k][0] < kop[(k - 1)/2][0]) {
  113. zamenjaj(k, (k - 1)/2);
  114. //od m/2 naprej so listi, teh ni treba
  115. if (k < m/2 - 1) popraviKopico(k);
  116. //prestavljati; indeksi so za 1 manjsi, ker zacnemo z 0
  117. }
  118. }
  119. }
  120. private void popraviKopico(int k){
  121. //potopi k-ti element do koder je treba
  122. //ce je oce vecji od manjsego sina
  123. if ((2*k + 1 < m) && (kop[k][0] > Math.min(kop[2*k + 1][0],kop[2*k + 2][0]))) {
  124. if (kop[2*k + 1][0] < kop[2*k + 2][0]) {
  125. zamenjaj(k, 2*k + 1);
  126. //rekurzivno gremo do listov - v smeri manjsega sina
  127. popraviKopico(2*k + 1);
  128. }
  129. else {
  130. zamenjaj(k, 2*k + 2);
  131. //drugi sin
  132. popraviKopico(2*k + 2);
  133. }
  134. }
  135. }
  136.  
  137. private void zamenjaj(int k, int j) {
  138.  
  139. int[] pom = new int[3];
  140. for (int i = 0; i < 3; i++) {
  141. pom[i] = kop[k][i];
  142. kop[k][i] = kop[j][i];
  143. kop[j][i] = pom[i];
  144. }
  145. }
  146.  
  147. public int velikost() {
  148. return m;
  149. }
  150. }class Kopica
Osebna orodja