Počítačová síť

Zadání

Limit: 2s

Jak na to:

1. Načíst vstup a uložit do listu hran. Je potřeba dávat pozor na to, že A→B je to stejné jako B→A. Mohou se tam také vyskytnout duplicitní nabídky, takže zachovat jenom tu s menší cenou
2. Seřadit hrany podle ceny, pokud jsou ceny stejné tak podle čísla první budovy
3. Inicializovat struktury na UNION-FIND - dvě pole:
   • „pole bossů“ - index je číslo budovy a obsah je kdo je boss budovy, na začátku je každý svůj boss
   • „pole hloubek“ - index je číslo budovy a obsah její hloubka, na začátku je hloubka 0
4. Procházet možné hrany od těch s nejmenších cenou a postupně je přidávat dokud jich nebude (počet budov-počet připojení k netu)
5. Nesmím ale přidat hranu, která by vytvořila cyklus - máme funkci můžuPřidatHranu(hrana), kterou řeší UNION-FIND:
   • pokud obě budovy z hrany mají stejného bosse, vzniknul by cyklus a vracím false
   • pokud obě budovy z hrany mají různého bosse, vracím true a přidávám hranu do dvou polí takto:
     • pokud hloubka bosse první budovy < hloubka bosse druhé budovy ⇒ boss první budovy je boss druhé budovy
     • pokud hloubka bosse první budovy > hloubka bosse druhé budovy ⇒ boss druhé budovy je boss první budovy
     • pokud hloubka bosse první budovy == hloubka bosse druhé budovy ⇒ boss druhé budovy je boss první budovy && zvyšuju hloubku u bosse první budovy o 1
6. Najít budovy, kam zavést interfernet, to už je easy:
   • Projdu pole bossů a uložím si tolik různých bossů, kolik mám zavést internetů
7. Všechno vypsat

Mnohem lépe vysvětlené než na přednáškách včetně praktických ukázek pseudokódu:Hledání minimální kostry a UNION-FIND problém

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;
      }
  }

}