Skip to main content

Minimum Spanning Tree

Minimum Spanning Tree

Minimum Spanning Tree

What is a Minimum Spanning Tree?

A minimum spanning tree (MST) is a subset of the edges of a connected, edge-weighted undirected graph that connects all the vertices together, without any cycles and with the minimum possible total edge weight. That is, it is a spanning tree whose sum of edge weights is as small as possible. More generally, any edge-weighted undirected graph (not necessarily connected) has a minimum spanning forest, which is a union of minimum spanning trees for its connected components.

Why MST?

  • Network design (telephone, hydraulic, electrical, TV cable, power, road)
  • cluster analysis
  • image processing (segmentation)

How to find MST?

Prim's Algorithm

- slowPrim(G=(V,E), starting vertex s):
    - Let (s,u) be the lightest edge incident to s
    - MST = {(s,u)}
    - verticesVisited = {s,u}
    - while |verticesVisited| < |V|:
        - Let (u,v) be the lightest edge with u in verticesVisited and v not in verticesVisited
        - MST = MST U {(u,v)}
        - verticesVisited = verticesVisited U {v}
    - return MST

Efficient implementation

  • K[x] is the distance of x from the growing tree.
  • p[b] = a, meaning that a was the vertex that k[b] comes from.
- Until all the vertices are reached:
    - Actuvate the unreached vertex u with the smallest k[u]
    - for each edge (u,v) with v unreached:
        - if w(u,v) < k[v]:
            - k[v] = w(u,v)
            - p[v] = u
    - Mark u as reached, MST = MST U {(p[u],u)}

Compared to Dijkstra's algorithm

  • Dijkstra's algorithm when update d[v] = min(d[v], d[u] + w(u,v)), but Prim's algorithm when update d[v] = min(d[v], w(u,v))

Running time

  • O(mlog(n)) using a red-black tree as a priority queue
  • O(m + nlog(n)) using a Fibonacci heap as a priority queue

Kruskal's Algorithm

Always choose the lightest edge that does not form a cycle.

- slowKruskal(G=(V,E)):
    - sort the edges in E by non-decreasing weight
    - MST = {}
    - for each edge (u,v) in E:
        - if MST U {(u,v)} has no cycles:
            - MST = MST U {(u,v)}
    - return MST

Efficient implementation

Union-Find data structure (disjoint-set data structure)

Supports:

  • makeSet(x): create a new set whose only member is x
  • find(u): return the representative of the set containing u
  • union(u,v): merge the two sets containing u and v
- Kruskal(G=(V,E)):
    - sort the edges in E by non-decreasing weight
    - MST = {}
    - for each vertex v in V:
        - makeSet(v)
    - for each edge (u,v) in E:
        - if find(u) != find(v):
            - MST = MST U {(u,v)}
            - union(u,v)
    - return MST

Leetcode 1584. Min Cost to Connect All Points

Prim's algorithm

class Solution {
public:
    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size(), res = 0, i = 0, connected = 0;
        vector<bool> visited(n);
        priority_queue<pair<int,int>> pq;
        while(++connected<n){
            visited[i] = true;
            for(int j=0;j<n;++j){
                if (not visited[j]) pq.push(make_pair(-(abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1])), j));
            }
            while (visited[pq.top().second]) pq.pop();
            res -= pq.top().first;
            i = pq.top().second;
            pq.pop();
        }
        return res;
    }
};

Kruskal's algorithm

class Solution{
public:
    int find(vector<int>& parent, int i){
        if (parent[i] == i) return i;
        return parent[i] = find(parent, parent[i]);
    }
    void unionSet(vector<int>& parent, int i, int j){
        int pi = find(parent, i), pj = find(parent, j);
        if (pi != pj) parent[pi] = pj;
    }

    int minCostConnectPoints(vector<vector<int>>& points) {
        int n = points.size(), res = 0;
        vector<int> parent(n);
        iota(parent.begin(), parent.end(), 0);
        vector<array<int,3>> edges;
        for(int i=0;i<n;++i){
            for(int j=i+1;j<n;++j){
                edges.push_back({abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]), i, j});
            }
        }
        sort(edges.begin(), edges.end());
        for(auto& edge: edges){
            if (find(parent, edge[1]) != find(parent, edge[2])){
                res += edge[0];
                unionSet(parent, edge[1], edge[2]);
            }
        }
        return res;    
    }
};

Comments

Post a Comment

Popular posts from this blog

Tries

Tries Tries Tries and Patricia Tries Motivation: The autocomplete feature in a text editor. We have a dictionary of words, and we want to find all the words that start with a given prefix. The data structure we use to store the dictionary is called a trie. Each edge is labeled with a character. Some nodes are marked as terminal nodes. By convention, children of a node are ordered alphabetically. A preordering traversal of the trie yields the words in the dictionary in alphabetical order. The total length of our text strings is m and the length of our pattern string is n . Time to build the trie: O(m) Time to search for a pattern: O(n) How long does it take to find all the words that start with a given prefix? The $ symbol is called the sentinel or marker, add this to the end of each word. It is used to mark the end of a word, it precedes all other characters in the alphabet....
Post a Comment
Read more

Recap on BFS, DFS and Strongly Connected Components

graph graph DFS topological sort considering the dependencies between tasks, we can use topological sort to find the order of tasks. def topological_sort ( graph ): visited = set () stack = [] for node in graph: if node not in visited: dfs(graph, node, visited, stack) return stack[::- 1 ] def dfs ( graph, node, visited, stack ): visited.add(node) for neighbor in graph[node]: if neighbor not in visited: dfs(graph, neighbor, visited, stack) stack.append(node) if A -> B then B.finishtime < A.finishtime, that's why we need to reverse the stack. Topological Sorting on a DAG do DFS on the graph when a node is finished, insert it into the front of a linked list Another use of DFS is in-order traversal of a binary tree . BFS BFS is used to find the shortest path in an unweighted graph . we can...
Post a Comment
Read more

Balanced Trees

Balanced Trees Balanced Trees Balanced search trees are among the most useful and versatile data structures. Many programming languages include balanced search trees in their standard libraries. e.g. C++: std::map , Java: TreeMap , Python: dict , etc. Many advanced data structures are layered on top of balanced search trees.. A quick BST recap A binary search tree is a binary tree where each node has a key and a value, and the following properties hold: Each node in the BST stores a key, and optinally, some information associated with the key. The keys in the left subtree are less than the key in its parent node, and the keys in the right subtree are greater than the key in its parent node. The height of a BST is the number of nodes on the longest path from the root to a leaf. A tree with one node has height 0, A tree with no nodes has height -1. Deleting from a BST Deleting a n...
Post a Comment
Read more