SHARE
TWEET

Untitled

a guest Nov 15th, 2019 88 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. package ilya;
  2.  
  3. import java.util.*;
  4.  
  5. public class PrimAlgorithm {
  6.     //graph - array of hashmaps where key - vertex and value - edge
  7.  
  8.     public static void main(String[] args) {
  9.         //read graph
  10.         Scanner in = new Scanner(System.in);
  11.         int N = in.nextInt();
  12.         List<Map<Integer, Integer>> input = new ArrayList<>();
  13.         for (int i = 0; i < N; i++) {
  14.             String line = in.nextLine();
  15.             String[] parsed = line.split(" ");
  16.             for (int j = 0; i < parsed.length  - 1; j += 2) {
  17.                 input.get(i).put(Integer.parseInt(parsed[j]), Integer.parseInt(parsed[j + 1]));
  18.             }
  19.         }
  20.  
  21.         PrimAlgorithm.graphPrezentation(getMinimumSpanningTree(input));
  22.     }
  23.  
  24.     private static List<Map<Integer, Integer>> getMinimumSpanningTree(List<Map<Integer, Integer>> source) {
  25.         boolean[] visited = new boolean[source.size()];
  26.         List<Map<Integer, Integer>> result = new ArrayList<>();
  27.         for (int i = 0; i < source.size(); i++) {
  28.             result.add(new HashMap<>());
  29.         }
  30.  
  31.         return result;
  32.     }
  33.  
  34.     private Integer getMin(List<Map<Integer, Integer>> source, int vertex, boolean[] visited) {
  35.         Integer min = null;
  36.         Map<Integer, Integer> s = source.get(vertex);
  37.         for (Map.Entry<Integer, Integer> entry : s.entrySet()) {
  38.             if (!visited[entry.getKey()]) {
  39.                 if (min != null) {
  40.                     if ()
  41.                 }
  42.             }
  43.         }
  44.     }
  45.  
  46.     private static void graphPrezentation(List<Map<Integer, Integer>> graph) {
  47.         for (int i = 0; i < graph.size(); i++) {
  48.             System.out.printf("%d:", i);
  49.             for (Map.Entry<Integer, Integer> entry : graph.get(i).entrySet()) {
  50.                 System.out.printf(" -%d- %d", entry.getValue(), entry.getKey());
  51.             }
  52.             System.out.println();
  53.         }
  54.     }
  55.  
  56. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top