Prim's (MST) : Special Subtree

  • + 0 comments

    Java Code

     public static int prims(int n, List<List<Integer>> edges, int start) {
             Set<Integer> connected = new HashSet<>();
            connected.add(start);
            int totalPrice = 0;
            while (connected.size() < n) {
                int minPrice = Integer.MAX_VALUE;
                List<Integer> edgeConnect = null;
                
                for (List<Integer> e : edges) {
                    int node1 = e.get(0);
                    int node2 = e.get(1);
                    int weight = e.get(2);
                    
                    if ((connected.contains(node1) && !connected.contains(node2)) || 
                        (connected.contains(node2) && !connected.contains(node1))) {
                        if (weight < minPrice) {
                            minPrice = weight;
                            edgeConnect = e;
                        }
                    }
                }
                
                if (edgeConnect == null) {
                    // If no edge found, graph might be disconnected
                    return -1; // or handle the disconnected graph case accordingly
                }
                
                connected.add(edgeConnect.get(0));
                connected.add(edgeConnect.get(1));
                totalPrice += minPrice;   
        }
            return totalPrice;
    
        }