Minimum spanning tree

0. Build the minimum spanning tree

• Ideas of two solutions

• 1584- The minimum cost of connecting all points

 To give you one points  Array , Express  2D  Some points on the plane , among  points[i] = [xi, yi] .

 Connection point  [xi, yi]  Sum point  [xj, yj]  The cost is between them   Manhattan distance  ：|xi - xj| + |yi - yj| , among  |val|  Express  val  The absolute value of .

 Please return the minimum total cost of connecting all points . Just between any two points   Yes and no   A simple path , All the points are connected .

Example 1：

 Input ：points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
 Output ：20

 explain ：
 We can connect all the points as shown in the figure above to get the minimum total cost , The total cost is  20 .
 Notice that there is only one path between any two points to reach each other .

 Example  2：
 Input ：points = [[3,12],[-2,5],[-4,1]]
 Output ：18

 Example  3：
 Input ：points = [[0,0],[1,1],[1,0],[-1,1]]
 Output ：4

 Example  4：
 Input ：points = [[-1000000,-1000000],[1000000,1000000]]
 Output ：4000000

 Example  5：
 Input ：points = [[0,0]]
 Output ：0

1.Kruskal Algorithm

• And look up the path compression of the set ：

Kruskal Algorithm ideas ：

• Sort each edge according to the weight from small to large
• Add edges in turn
• Judge whether the newly added edge is looped by using the union search set

/* * @Date: 2022-06-30 * @Author: bFeng */
/* * @lc app=leetcode.cn id=1584 lang=cpp * * [1584]  The minimum cost of connecting all points  */

// @lc code=start
class UnionFind {
    
 public:
  UnionFind(int n) {
    
    count_ = n;
    parent_.resize(n);
    for (int i = 0; i < n; ++i) {
    
      parent_[i] = i;  //  Be your own parent node 
    }
  }
  //  and 
  void Union(int point1, int point2) {
    
    int f1 = Find(point1);
    int f2 = Find(point2);
    if (f1 == f2) return;  //  The root node is the same , It is already in a picture 
    parent_[f1] = f2;  // f1（point1 The ancestors of the ）  The parent of is set to  f2（point2 The ancestors of the ）
  }
  //  check 
  // int Find(int point) {
    
  // //  If the parent node is not itself , Then go all the way up to find the root node 
  // while (parent_[point] != point) {
    
  // parent_[point] = parent_[parent_[point]];
  // point = parent_[point];
  // }
  // return parent_[point];
  // }

  //  check   recursive 
  // int Find(int point) {
    
  // if (parent_[point] == point)
  // return point;
  // else
  // return find(parent_[point]);
  // }
  //  If the root node is the same , Is connected 

  //  check   recursive 
  int Find(int i) {
    
    if (parent_[i] == i)
      return i;
    else {
    
      //  Path compression 
      parent_[i] = Find(parent_[i]);
      return parent_[i];
    }
  }
  //  If the root node is the same , Is connected 
  bool Connected(int point1, int point2) {
    
    return Find(point1) == Find(point2);
  }

 private:
  int count_;
  std::vector<int> parent_;
};

struct Edge {
    
  int p1_;
  int p2_;
  int manhattan_;
  Edge(int p1, int p2, int manhattan)
      : p1_(p1), p2_(p2), manhattan_(manhattan) {
    }
};

class Solution {
    
 public:
  int minCostConnectPoints(vector<vector<int>>& points) {
    
    int points_size = points.size();
    UnionFind union_find(points_size);

    std::vector<Edge> edges;
    for (int i = 0; i < points_size; ++i) {
    
      for (int j = i + 1; j < points_size; ++j) {
    
        int i_x = points[i][0];
        int i_y = points[i][1];
        int j_x = points[j][0];
        int j_y = points[j][1];
        int manhattan = std::abs(i_x - j_x) + std::abs(i_y - j_y);
        edges.emplace_back(i, j, manhattan);
      }
    }
    //  If it is the largest spanning tree , Take this  ‘<’  Change it to  ‘>’  that will do 
    std::sort(edges.begin(), edges.end(),
              [&](Edge& a, Edge& b) {
     return a.manhattan_ < b.manhattan_; });

    int res_mst = 0;
    //  Greedy choice 
    for (auto edge : edges) {
    
      int point1 = edge.p1_;
      int point2 = edge.p2_;
      int distance = edge.manhattan_;
      if (union_find.Connected(point1, point2)) continue;
      res_mst += distance;
      union_find.Union(point1, point2);
    }

    return res_mst;
  }
};
// @lc code=end

• Kruskal The algorithm takes edges as cells , Time $O(mlog(m))$ Mainly depends on the number of sides , It is more suitable for sparse graphs .

2.Prim Algorithm

prim The algorithm is actually BFS thought .

/* * @Date: 2022-06-30 * @Author: bFeng */
/* * @lc app=leetcode.cn id=1584 lang=cpp * * [1584]  The minimum cost of connecting all points  */

// @lc code=start
struct Edge {
    
  int p1_;
  int p2_;
  int manhattan_;
  Edge(int p1, int p2, int manhattan)
      : p1_(p1), p2_(p2), manhattan_(manhattan) {
    }
};

//  Pay attention to the priority queue  class Compare = std::less<typename Container::value_type>
// less  Time is the largest heap 
//  To build the largest spanning tree , Put the  ‘>’  Change it to  '<'
struct Cmp {
    
  bool operator()(Edge& a, Edge& b) {
     return a.manhattan_ > b.manhattan_; }
};

class Solution {
    
 public:
  int minCostConnectPoints(vector<vector<int>>& points) {
    
    int points_size = points.size(); //  Example 1： points_size = 5
    visited_.resize(points_size);
    //  From top to bottom , From left to right   Number nodes  0 1 2 3 4
    //  Adjacency list 
    // graph[0]: (p1, w01),(p2, w02),(p3, w03),(p4, w04)
    // graph[1]: (p2, w12),(p3, w13),(p4, w14)
    // graph[2]: (p3, w23),(p4, w24)
    // graph[3]: (p4, w34)
    // graph[4]: 
    std::vector<std::vector<pair<int, int>>> graph(points_size);

    for (int i = 0; i < points_size; ++i) {
    
      for (int j = i + 1; j < points_size; ++j) {
    
        int i_x = points[i][0];
        int i_y = points[i][1];
        int j_x = points[j][0];
        int j_y = points[j][1];
        int manhattan = std::abs(i_x - j_x) + std::abs(i_y - j_y);
        graph[i].push_back({
    j, manhattan});
        graph[j].push_back({
    i, manhattan});
      }
    }

    int res_mst = 0;
    visited_[0] = true;
    cut(0, graph);
    //  Greedy choice 
    while(!edge_queue_.empty()) {
    
      //  Take out the edge with the lowest weight in this list 
      Edge edge = edge_queue_.top();
      edge_queue_.pop();
      int to_point = edge.p2_;
      int weight = edge.manhattan_;
      if (visited_[to_point]) continue;
      res_mst += weight;
      visited_[to_point] = true;
      // BFS
      cut(to_point, graph);
    }

    return res_mst;
  }

  private:
  std::priority_queue<Edge, std::vector<Edge>, Cmp> edge_queue_; //
  std::vector<bool> visited_ = {
    false};
  void cut(int point, std::vector<std::vector<std::pair<int,int>>>& graph) {
    
    for (auto& p : graph[point]) {
     //  Traverse a table , Build edges and sort 
      int to_point = p.first;
      int weight = p.second;
      if (visited_[to_point]) continue;
      edge_queue_.push({
    point, to_point, weight});
    }
  }
};

Pay attention to the priority queue cmp , A little counter intuitive .

• Time complexity $O(n^2)$, Suitable for dense map