Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- courses:a4m33pal:uloha2-2010 [2010/10/20 22:23]
redtop
+++ courses:a4m33pal:uloha2-2010 [2025/01/03 18:28] (aktuální)
@@ Řádek 4: / Řádek 4: @@
 [[http://cw.felk.cvut.cz/courses/a4m33pal/task.php?task=pocitacova_sit|Zadání]]
+Limit: 2s
 Jak na to:
@@ Řádek 22: / Řádek 24: @@
   - Všechno vypsat
+====== Hledání koster a UNION-FIND ======
+Mnohem lépe vysvětlené než na přednáškách včetně praktických ukázek pseudokódu:{{:courses:a4m33pal:kostry.pdf|Hledání minimální kostry a UNION-FIND problém}}
+====== Generátor grafů ======
+Přidávám svůj generátor grafů pro tuhle úlohu. Snad někomu pomůže. Pro opravdu velké grafy je nutné krapet přepsat a flushovat více String Buildery
+public class MatrixGenerator {
+    public static void main(String[] args) {
+        if(args.length!=4){
+            System.out.println("Run the program with [nodes] [connections] [edges] [full/random/noconn] params.");
+            return;
+        }
+        final int NODES = Integer.parseInt(args[0]);
+        final int CONNECTIONS = Integer.parseInt(args[1]);
+        final int EDGES = Integer.parseInt(args[2]);
+        final String type = args[3];
+        if("full".equals(type.toLowerCase())){
+            makeFullGraph(NODES,CONNECTIONS);
+        }else if("random".equals(type.toLowerCase())){
+            makeRandomGraph(NODES, CONNECTIONS,EDGES);
+        }else{
+            makeNotConnectableFullGraph(NODES,CONNECTIONS);
+        }
+    }
+    public static void makeRandomGraph(int NODES,int CONNECTIONS, int EDGES){
+        StringBuilder sb = new StringBuilder();
+        final boolean random = true;
+        sb.append(NODES);
+        sb.append("\n");
+        sb.append(CONNECTIONS);
+        sb.append("\n");
+        for(int i = 0 ; i<= EDGES ; i++){
+            int x = (int)(1+((Math.random()*NODES)%(NODES-1)));
+            int y = (int)(1+((Math.random()*NODES)%(NODES-1)));
+            if(x == y){
+                i--;
+                continue;
+            }
+            sb.append(x);
+            sb.append(" ");
+            sb.append(y);
+            sb.append(" ");
+            sb.append(getWeight(random));
+            sb.append("\n");
+        }
+        sb.append("0 0 0\n");
+        System.out.println(sb.toString());
+    }
+    public static void makeNotConnectableFullGraph(int NODES,int CONNECTIONS) {
+        final boolean random = true;
+        StringBuilder sb = new StringBuilder();
+        sb.append(NODES+CONNECTIONS+1);
+        sb.append("\n");
+        sb.append(CONNECTIONS);
+        sb.append("\n");
+        for (int i = 1; i <= NODES; i++) {
+            for (int y = 1; y <= NODES; y++) {
+                if (i != y) {
+                    sb.append(y);
+                    sb.append(" ");
+                    sb.append(i);
+                    sb.append(" ");
+                    sb.append(getWeight(random));
+                    sb.append("\n");
+                }
+            }
+        }
+        sb.append("0 0 0\n");
+        System.out.println(sb.toString());
+    }
+    public static void makeFullGraph(int NODES,int CONNECTIONS) {
+        final boolean random = true;
+        StringBuilder sb = new StringBuilder();
+        sb.append(NODES);
+        sb.append("\n");
+        sb.append(CONNECTIONS);
+        sb.append("\n");
+        for (int i = 1; i <= NODES; i++) {
+            for (int y = 1; y <= NODES; y++) {
+                if (i != y) {
+                    sb.append(y);
+                    sb.append(" ");
+                    sb.append(i);
+                    sb.append(" ");
+                    sb.append(getWeight(random));
+                    sb.append("\n");
+                }
+            }
+        }
+        sb.append("0 0 0\n");
+        System.out.println(sb.toString());
+    }
+    public static int getWeight(boolean random) {
+        if (random) {
+            return (int) (Math.random() * 99 + 1);
+        } else {
+            return 10;
+        }
+    }
+}
+====== Diskuze ======
 ~~DISCUSSION~~

courses/a4m33pal/uloha2-2010.1287606184.txt.gz · Poslední úprava: 2025/01/03 18:24 (upraveno mimo DokuWiki)

Nahoru