Kruskalov algoritem/Implementacija (Java)

Iz MaFiRaWiki

  1. /**
  2. Program poisce minimalno vpeto drevo danega povezanega grafa. Pri tem uporabi Kruskalov postopek: resitev gradi kot mnozico (pod)dreves, na vsakem koraku poveze dve poddrevesi z najcenejso razpolozljivo povezavo in pazi, da ne dobi ciklov.
  3. Metode:
  4. * int preberi(String niz): prebere STEVILO (trenutno samo iz vnosnega okna) ali pa ga doloci nakljucno; niz je morebiten komentar za uporabnika
  5. * void branjeMatrike(int[][] matrika): prebere elemente zgornjetrikotne kvadratne matrike n*n
  6. krusk(kopica, n) - to je osrednji del, kruskalov algoritem, resitev je tabela povezav, ki sestavljajo minimalno vpeto drevo; v tabeli skupaj hranimo cene in krajisca posameznih povezav.
  7. * public static int[][] krusk(Kopica kopica, int n): izvede kruskalov algoritem na kopici povezav,
  8. n je stevilo vozlisc, ne povezav.
  9. * public static boolean dopustna(int[] povezava) - preveri, ali je povezava dopustna - ali sta krajisci ze nepovezani; hkrati metoda se zdruzi na novo povezani poddrevesi
  10. * public static void dodaj(int[][] resitev, int i, int[] povezava): resitvi na mesto z indeksom i doda povezavo
  11. * public static void izpisResitve(Graphics g, int[][] resitev): na graficno povrsino izpise vektor resitve: povezave in cene, v istem vrstnem redu, kot jih je določil algoritem
  12. * public static void narisiGraf(Graphics g, int[][] pov): na graficno povrsino narise graf, dan z matriko povezav pov
  13. * public static void narisiDrevo(Graphics g, int[][] drevo): na ze narisanem grafu oznaci minimalno vpeto drevo, povezave dodaja kot v Kruskalovem algoritmu
  14. * public static void narisiVozlisce(Graphics g, int i): narise vozlisce i, pozicije vozlisc so fiksirane (tabeli koordinat vozX in vozY)
  15. * public static void narisiPovezavo(Graphics g, int i, int j, int cena): narise povezavo med i-tim in j-tim vozliscem, njihove pozicije so fiksne - tabeli vozX in vozY
  16. * public static void crta(Graphics g, int x1, int y1, int x2, int y2): narise debelejso crto od A(x1,y1) do B(x2,y2)
  17. * public static void cakaj(int koliko): kratka prekinitev med koraki (pri risanju)
  18. */
  19.  
  20. public class Kruskal extends Applet {
  21.  
  22. static final int NESKONCNO = 100;
  23. //seznam povezanih oz. nepovezanih vozlisc
  24. static int[] poddrevesa;
  25. //stevilo vozlisc
  26. int n;
  27. //nacin vnosa: preko vnosnega okna ali nakljucen
  28. boolean nakljucenVnos;
  29. //matrika povezav
  30. int[][] pov;
  31.  
  32. //koordinate vozlisc, za zdaj jih je najvec 8
  33. static int[] vozX = {60, 20, 60, 160, 260, 300, 260, 160};
  34. static int[] vozY = {60, 160, 260, 300, 260, 160, 60, 20};
  35. Kopica kopica;
  36. int[][] resitev;
  37.  
  38. public void init() {
  39.  
  40. //nacin branja podatkov
  41. int nacin = preberi("Nacin branja (1-vnosno okno, 2-nakljucno): ", false);
  42. nakljucenVnos = false;
  43. if (nacin == 2) nakljucenVnos = true;
  44. n = preberi("Stevilo vozlisc (ce je vecje od 8, ni slike!): ", false);
  45.  
  46. //branje
  47. //matrika povezav - niti ni potrebna, le zaradi preglednosti
  48. //lahko bi takoj prebrali povezave (cene in krajisca) v (linearno) tabelo
  49. pov = new int[n][n];
  50. branjeMatrike(pov, nakljucenVnos);
  51. //povezave zlozimo v minimalno kopico, pri tem izpustimo neskoncne povezave, da bo manj dela
  52. //pobrisano: /*Kopica*/
  53. kopica = new Kopica(pov, NESKONCNO);
  54.  
  55. //evidenca o poddrevesih - na zacetku jih je toliko kot vozlisc, pozneje se zdruzujejo
  56. poddrevesa = new int[n];
  57. for (int i = 0; i < n; i++) {
  58. poddrevesa[i] = i;
  59. }
  60. resitev = new int[n][3];
  61. resitev = krusk(kopica, n);
  62. setBackground(new Color(200, 200, 200));
  63. } //init
  64.  
  65. public void paint(Graphics g) {
  66. //kruskalov algoritem - osrednji del
  67.  
  68. izpisResitve(g, resitev);
  69. //graf narisemo za najvec 8 vozlisc
  70. if (n <= 8) {
  71. narisiGraf(g, pov);
  72. narisiDrevo(g, resitev);
  73. }
  74. } //paint
  75.  
  76. //METODE
  77.  
  78. public static int preberi(String niz, boolean nakljVnos) {
  79. //"prebere" stevilo: glede na izbrani nacin ga doloci nakljucno v danih mejah, ali pa ga
  80. // prebere iz vnosnega okna
  81. int r;
  82. if (nakljVnos) {
  83. //nakljucno stevilo od 1 do 15
  84. r = (int)(Math.random()*15 + 1);
  85. //nekaterih povezav ni
  86. if (r > 10) r = NESKONCNO;
  87. }
  88. else r = Integer.parseInt(JOptionPane.showInputDialog(niz));
  89. return r;
  90. } //preberi
  91.  
  92. public static void branjeMatrike(int[][] matrika, boolean naklj) {
  93. for (int i = 0; i < matrika.length; i++) {
  94. for (int j = i + 1; j < matrika.length; j++) {
  95. matrika[i][j] = preberi("pov("+i+", "+j+"):", naklj);
  96. }
  97. }
  98. } //branjeMatrike
  99.  
  100. public static int[][] krusk(Kopica kopica, int n) {
  101. //po Krusklalovem postopku poisce minimalno vpeto drevo
  102. //resitev je malo "sirsi" vektor, vsaka komponenta ima tri mesta
  103. int[][] resitev = new int[n][3];
  104. //nova povezava; če je dopustna, jo bomo dodali
  105. int[] nova = new int[3];
  106. int i = 0;
  107. //natanko n-1 korakov
  108. while(i < n-1) {
  109. nova = kopica.povejVrh();
  110. kopica.brisi();
  111. if (dopustna(nova)) {
  112. dodaj(resitev, i, nova);
  113. i++;
  114. }
  115. }
  116. return resitev;
  117. } //krusk
  118.  
  119. public static boolean dopustna(int[] povezava){
  120. //preveri, ali je povezava dopustna - ali sta krajisci ze nepovezani; hkrati metoda se zdruzi
  121. //poddrevesi
  122.  
  123. int i = povezava[1];
  124. int j = povezava[2];
  125. i = poddrevesa[i];
  126. j = poddrevesa[j];
  127. //sta ze povezani
  128. if (i == j) return false;
  129. for (int k = 0; k < poddrevesa.length; k++) {
  130. //zdruzimo dve poddrevesi - indeksi bodo enaki
  131. if (poddrevesa[k] == j) poddrevesa[k] = i;
  132. }
  133. return true;
  134. } //dopustna
  135.  
  136. public static void dodaj(int[][] resitev, int i, int[] povezava) {
  137. //resitvi na mesto z indeksom i doda povezavo
  138.  
  139. resitev[i][0] = povezava[0];
  140. resitev[i][1] = povezava[1];
  141. resitev[i][2] = povezava[2];
  142. } //dodaj
  143.  
  144. public static void izpisResitve(Graphics g, int[][] resitev) {
  145. //na graficno povrsino izpise vektor resitve: povezave in cene, v istem vrstnem redu,
  146. //kot jih je določil algoritem
  147.  
  148. g.drawString(" povezava cena", 330, 10);
  149. g.drawString("-------------------------", 330, 20);
  150. int y = 30;
  151. int vsotaCen = 0;
  152. for (int k = 0; k < resitev.length-1; k++) {
  153. g.drawString(" ("+(resitev[k][1] + 1)+", "+(resitev[k][2] + 1)+")
  154. "+resitev[k][0], 330, y);
  155. vsotaCen = vsotaCen + resitev[k][0];
  156. y = y + 10;
  157. }
  158. g.drawString("-------------------------", 330, y);
  159. g.drawString("skupna cena: "+vsotaCen, 330, y + 10);
  160. } //izpisResitve
  161.  
  162. public static void narisiGraf(Graphics g, int[][] pov){
  163. //na graficno povrsino narise graf, dan z matriko povezav pov
  164.  
  165. int n = pov.length;
  166. for (int i = 0; i < n; i++) {
  167. for (int j = i + 1; j < n; j++) {
  168. //nepotrebno, pogoj je ce v metodi sami
  169. if (pov[i][j] != NESKONCNO) {
  170. g.setColor(new Color(150, 150, 150));
  171. narisiPovezavo(g, i, j, pov[i][j]);
  172. }
  173. }
  174. }
  175. for (int k = 0; k < n; k++) {
  176. narisiVozlisce(g, k);
  177. }
  178. }
  179.  
  180. public static void narisiDrevo(Graphics g, int[][] drevo) {
  181. //ze narisanem grafu označi minimalno vpeto drevo, povezave dodaja kot v Kruskalovem
  182. //algoritmu
  183.  
  184. for (int k = 0; k < drevo.length-1; k++) {
  185. g.setColor(new Color(0, 0, 250));
  186. narisiPovezavo(g, drevo[k][1], drevo[k][2], drevo[k][0]);
  187. cakaj(1500);
  188. }
  189. } //narisiDrevo
  190.  
  191. public static void narisiVozlisce(Graphics g, int i) {
  192. //narise vozlisce i, pozicije vozlisc so fiksirane (tabeli x in y)
  193.  
  194. g.setColor(new Color(250, 0, 0));
  195. g.fillOval(vozX[i] - 10, vozY[i] - 10, 20, 20);
  196. //vozlisca so oznacena od 1, ne od 0 naprej
  197. String oznaka = "" + (i + 1);
  198. g.setColor(new Color(0, 0, 0));
  199. g.drawString(oznaka, vozX[i] - 3, vozY[i] + 3);
  200. } //narisiVozlisce
  201.  
  202. public static void narisiPovezavo(Graphics g, int i, int j, int cena) {
  203. //narise povezavo med i-tim in j-tim vozliscem, njihove pozicije so fiksne - tabeli
  204. // vozX in vozY
  205.  
  206. if (cena < NESKONCNO) {
  207. crta(g, vozX[i], vozY[i], vozX[j], vozY[j]);
  208. int x = (3* vozX[i] + vozX[j]) / 4 - 4;
  209. int y = (3* vozY[i] + vozY[j]) / 4 + 4;
  210. narisiVozlisce(g, i);
  211. narisiVozlisce(g, j);
  212. g.setColor(new Color(0, 0, 0));
  213. g.drawString(""+cena, x, y);
  214. }
  215. } //narisiPovezavo
  216.  
  217. public static void crta(Graphics g, int x1, int y1, int x2, int y2) {
  218. //narise debelejso crto, barva je izbrana prej
  219. g.drawLine(x1, y1, x2, y2);
  220. g.drawLine(x1+1, y1, x2+1, y2);
  221. g.drawLine(x1-1, y1, x2-1, y2);
  222. g.drawLine(x1, y1-1, x2, y2-1);
  223. g.drawLine(x1, y1+1, x2, y2+1);
  224. } //crta
  225.  
  226. public static void cakaj(int koliko) {
  227. long zdaj = System.currentTimeMillis();
  228. while (zdaj > System.currentTimeMillis() - koliko);
  229. } //cakaj
  230. } //class
Osebna orodja