content: package graphs;
  
  import java.util.ArrayList;
  import java.util.Arrays;
  import java.util.List;
  
  public class MinimumSpanningTree {
  
      /*
       * Find the minimum spanning tree of a connected, undirected graph with weighted edges.
       *
       *
       *
       * Runtime Complexity:
       * Quadratic, O(n2)
       * Here, 'n' is the number of vertices.
       *
       * Memory Complexity:
       * Linear, O(n + e).
       * Here, 'n' is the number of vertices and 'e' is the number of edges.
       *
       * A spanning tree of a connected, undirected graph is a subgraph that is a tree and connects
       * all the vertices together. One graph can have many different spanning trees.
       * A graph with n vertices has a spanning tree with n-1 edges.
       *
       * A weight can be assigned to each edge of the graph.
       * The weight of a spanning tree is the sum of weights of all the edges of the spanning tree.
       * A minimum spanning tree(MST) for a weighted, connected and undirected graph is a spanning tree with
       * weight less than or equal to the weight of every other spanning tree.
       *
       * Find the minimum spanning tree of a graph using Prim's algorithm.
       * This algorithm builds the tree one vertex at a time, starting from any arbitrary vertex.
       * It adds the minimum weight edge from the tree being constructed to a vertex from the remaining
       * vertices at each step.
       * */
  
      protected static class Vertex {
          private int id;
          private boolean visited;
  
          public Vertex(int id, boolean visited) {
              super();
              this.id = id;
              this.visited = visited;
          }
  
          int getId() {
              return id;
          }
  
          void setId(int id) {
              this.id = id;
          }
  
          boolean isVisited() {
              return visited;
          }
  
          void setVisited(boolean visited) {
              this.visited = visited;
          }
      }
  
      protected static class Edge {
          private int weight;
          private boolean visited;
          private Vertex src;
          private Vertex dest;
  
          public Edge(int weight, boolean visited, Vertex src,
                      Vertex dest) {
              this.weight = weight;
              this.visited = visited;
              this.src = src;
              this.dest = dest;
          }
  
          int getWeight() {
              return weight;
          }
  
          void setWeight(int weight) {
              this.weight = weight;
          }
  
          boolean isVisited() {
              return visited;
          }
  
          void setVisited(boolean visited) {
              this.visited = visited;
          }
  
          Vertex getSrc() {
              return src;
          }
  
          void setSrc(Vertex src) {
              this.src = src;
          }
  
          Vertex getDest() {
              return dest;
          }
  
          void setDest(Vertex dest) {
              this.dest = dest;
          }
      }
  
      protected static class Graph {
          private List<Vertex> g;   //vertices
          private List<Edge> e;     //edges
  
          public Graph(List<Vertex> g, List<Edge> e) {
              super();
              this.g = g;
              this.e = e;
          }
  
          public List<Vertex> getG() {
              return g;
          }
  
          public void setG(List<Vertex> g) {
              this.g = g;
          }
  
          public List<Edge> getE() {
              return e;
          }
  
          public void setE(List<Edge> e) {
              this.e = e;
          }
  
          // This method returns the vertex with a given id if it
          // already exists in the graph, returns NULL otherwise
          Vertex vertexExists(int id) {
              for (int i = 0; i < g.size(); i++) {
                  if (g.get(i).getId() == id) {
                      return g.get(i);
                  }
              }
              return null;
          }
  
          // This method generates the graph with v vertices
          // and e edges
          void generateGraph(int vertices,
                             List<ArrayList<Integer>> edges) {
              // create vertices
              for (int i = 0; i < vertices; i++) {
                  Vertex v = new Vertex(i + 1, false);
                  g.add(v);
              }
  
              // create edges
              for (int i = 0; i < edges.size(); i++) {
                  Vertex src = vertexExists(edges.get(i).get(1));
                  Vertex dest = vertexExists(edges.get(i).get(2));
                  Edge e = new Edge(edges.get(i).get(0), false, src,
                          dest);
                  getE().add(e);
              }
          }
  
          // This method finds the MST of a graph using
          // Prim's Algorithm
          // returns the weight of the MST
          int findMinSpanningTree() {
              int vertex_count = 0;
              int weight = 0;
  
              // Add first vertex to the MST
              Vertex current = g.get(0);
              current.setVisited(true);
              vertex_count++;
  
              // Construct the remaining MST using the
              // smallest weight edge
              while (vertex_count < g.size()) {
                  Edge smallest = null;
                  for (int i = 0; i < e.size(); i++) {
                      if (e.get(i).isVisited() == false
                              && e.get(i).getDest().isVisited() == false) {
                          smallest = e.get(i);
                          break;
                      }
                  }
  
                  for (int i = 0; i < e.size(); i++) {
                      if (e.get(i).isVisited() == false) {
                          if (e.get(i).getSrc().isVisited() == true
                                  && e.get(i).getDest().isVisited() == false
                                  && (e.get(i).getWeight() < smallest
                                  .getWeight())) {
                              smallest = e.get(i);
                          }
                      }
                  }
  
                  smallest.setVisited(true);
                  smallest.getDest().setVisited(true);
                  weight += smallest.getWeight();
                  vertex_count++;
              }
              return weight;
          }
  
          void printMst(int w) {
              System.out.println("MST");
              for (int i = 0; i < e.size(); i++) {
                  if (e.get(i).isVisited() == true) {
                      System.out.println(e.get(i).getSrc().getId() + "->"
                              + e.get(i).getDest().getId());
                  }
              }
              System.out.println("weight: " + w);
              System.out.println();
          }
      };
  
  
  
      public static void testGraph1() {
          Graph g = new Graph(new ArrayList<>(), new ArrayList<>());
          int v = 5;
  
          // each edge contains the following: weight, src, dest
          ArrayList<Integer> e1 = new ArrayList<Integer>(Arrays.asList(1, 1, 2));
          ArrayList<Integer> e2 = new ArrayList<Integer>(Arrays.asList(1, 1, 3));
          ArrayList<Integer> e3 = new ArrayList<Integer>(Arrays.asList(2, 2, 3));
          ArrayList<Integer> e4 = new ArrayList<Integer>(Arrays.asList(3, 2, 4));
          ArrayList<Integer> e5 = new ArrayList<Integer>(Arrays.asList(3, 3, 5));
          ArrayList<Integer> e6 = new ArrayList<Integer>(Arrays.asList(2, 4, 5));
  
          List<ArrayList<Integer>> e = new ArrayList<>();
          e.add(e1);
          e.add(e2);
          e.add(e3);
          e.add(e4);
          e.add(e5);
          e.add(e6);
  
          g.generateGraph(v, e);
          System.out.println("Testing graph 1...");
          int w = g.findMinSpanningTree();
          g.printMst(w);
      }
  
      public static void testGraph2() {
          Graph g = new Graph(new ArrayList<>(), new ArrayList<>());
          int v = 7;
  
          // each edge contains the following: weight, src, dest
          ArrayList<Integer> e1 = new ArrayList<>(Arrays.asList(2, 1, 4));
          ArrayList<Integer> e2 = new ArrayList<>(Arrays.asList(1, 1, 3));
          ArrayList<Integer> e3 = new ArrayList<>(Arrays.asList(2, 1, 2));
          ArrayList<Integer> e4 = new ArrayList<>(Arrays.asList(1, 3, 4));
          ArrayList<Integer> e5 = new ArrayList<>(Arrays.asList(3, 2, 4));
          ArrayList<Integer> e6 = new ArrayList<>(Arrays.asList(2, 3, 5));
          ArrayList<Integer> e7 = new ArrayList<>(Arrays.asList(2, 4, 7));
          ArrayList<Integer> e8 = new ArrayList<>(Arrays.asList(1, 5, 6));
          ArrayList<Integer> e9 = new ArrayList<>(Arrays.asList(2, 5, 7));
  
          List<ArrayList<Integer>> e = new ArrayList<>();
          e.add(e1);
          e.add(e2);
          e.add(e3);
          e.add(e4);
          e.add(e5);
          e.add(e6);
          e.add(e7);
          e.add(e8);
          e.add(e9);
  
          g.generateGraph(v, e);
          System.out.println("Testing graph 2...");
          int w = g.findMinSpanningTree();
          g.printMst(w);
      }
  
      public static void main(String[] args) {
          testGraph1();
          testGraph2();
      }
  }
  