{"id":1385,"date":"2020-06-28T16:47:27","date_gmt":"2020-06-28T23:47:27","guid":{"rendered":"http:\/\/209.126.2.187\/?p=1385"},"modified":"2020-09-13T21:06:45","modified_gmt":"2020-09-14T04:06:45","slug":"minimum-spinning-tree","status":"publish","type":"post","link":"https:\/\/nanzhou.cc\/index.php\/2020\/06\/28\/minimum-spinning-tree\/","title":{"rendered":"Minimum Spinning Tree"},"content":{"rendered":"\n

Summary<\/h2>\n\n\n\n

A spanning tree<\/strong> of some graph G is a subgraph that is a tree which includes all of the vertices of G, with a minimum possible number of edges. <\/p>\n\n\n\n

A Minimum Spanning Tree<\/strong> (MST) is a spanning tree whose sum of edge weights is as small as possible.<\/p>\n\n\n\n

Kruskal’s Algorithm<\/h3>\n\n\n\n

Please refer to this page<\/a> for its concepts and pseudo codes. <\/p>\n\n\n\n

The following code is implemented with disjoint-set (Union Find) data structure. The time complexity is O(ElogE)<\/code>.<\/p>\n\n\n\n

struct UnionFind {\n    vector<int> parent;\n    vector<int> size;\n    int total_group;\n    UnionFind(int n) {\n        total_group = n;\n        for (int i = 0; i < n; ++i) {\n            parent.push_back(i);\n            size.push_back(1);\n        }\n    }\n    int Find(int i) {\n        if (i != parent[i]) {\n            parent[i] = Find(parent[i]);\n        }\n        return parent[i];\n    }\n    void Union(int i, int j) {\n        int root1 = Find(i), root2 = Find(j);\n        if (root1 != root2) {\n            total_group--;\n            size[root1] += size[root2];\n            size[root2] = 0;\n            parent[root2] = root1;\n        }\n    }\n};\n\nstruct Edge {\n    int from = 0, to = 0, cost = 0;\n    bool operator< (Edge const &e) const {\n        return cost < e.cost;\n    }\n};\n\npair<int, vector<Edge>> Kruskal(vector<Edge> &edges, int n) {\n    sort(edges.begin(), edges.end());\n\n    UnionFind uf(n);\n\n    int cost = 0;\n    vector<Edge> choosed;\n\n    for (auto const &e : edges) {\n        if (uf.Find(e.from) != uf.Find(e.to)) {\n            uf.Union(e.from, e.to);\n            cost += e.cost;\n            choosed.push_back(e);\n        }\n    }\n    return {cost, choosed};\n}\n<\/code><\/pre>\n\n\n\n
Prim’s Algorithm<\/h3>\n\n\n\n
This algorithm is very similar to the Dijkstra algorithm I introduced in this post<\/a>. <\/p>\n\n\n\n
We use a priority queue to stores the potential nodes we could visit and its current cost . Note that the cost here is not from the initial point to the node. It represents the cost to include the node into the MST. <\/p>\n\n\n\n
We randomly choose a point to start and greedily<\/strong> choose the node with lowest cost to visit. <\/p>\n\n\n\n
In each iteration, the cost we get is guaranteed to be the lowest cost to bring in the current node, which is a property of greedy<\/strong> (the first visit will always have smaller cost than other costs in queue). Note that<\/strong>: Not like BFS, where we can mark node as visited when we push them in the queue, a node is marked as visited (gains its lowest cost) only when it gets out of the queue.<\/p>\n\n\n\n
We then visit the newly introduced edges regarding the current node and update the lowest cost in the queue (to guarantee there are no duplicate nodes in the queue).<\/p>\n\n\n\n
The size of queue will be at most O(V)<\/code>; each node might have at most O(V)<\/code> edges; the graph has O(E)<\/code> edges, we visit each node once. So the time complexity will be O((E+V)logV)<\/code>. <\/p>\n\n\n\n
pair<int, vector<Edge>> Prim(unordered_map<int, vector<Edge>> adj_list, int n, int start_point) {\n\n    multiset<Edge> s;\n    unordered_map<int, int> node_cheapest_cost;\n    unordered_map<int, multiset<Edge>::iterator> node_s_iter;\n\n    int cost = 0;\n    vector<Edge> choosed;\n\n    node_cheapest_cost[start_point] = 0;\n    for (auto const &e : adj_list[start_point]) {\n        node_s_iter[e.to] = s.insert(e);\n    }\n\n    while (s.size() > 0) {\n        auto curr_e = *s.begin();\n        s.erase(s.begin());\n        \/\/ update iterator map when updating multiset\n        node_s_iter.erase(curr_e.to);\n\n        cost += curr_e.cost;\n        node_cheapest_cost[curr_e.to] = curr_e.cost;\n        choosed.push_back(curr_e);\n        for (auto const &next_e : adj_list[curr_e.to]) {\n            \/\/ not a must\n            if (node_cheapest_cost.count(next_e.to)) {\n                continue;\n            }\n            if (node_s_iter.count(next_e.to)) {\n                if (node_s_iter[next_e.to]->cost > next_e.cost) {\n                    s.erase(node_s_iter[next_e.to]);\n                    node_s_iter[next_e.to] = s.insert(next_e);\n                }\n            } else {\n                node_s_iter[next_e.to] = s.insert(next_e);\n            }\n        }\n    }\n\n    return {cost, choosed};\n}<\/code><\/pre>\n\n\n\n
Many lazy deletion implementation actually has O((E+V)logE)<\/code> complexity, but it is simpler to implement.<\/p>\n\n\n\n
pair<int, vector<Edge>> Prim(unordered_map<int, vector<Edge>> adj_list, int n, int start_point) {\n\n    multiset<Edge> s;\n    vector<int> node_cheapest_cost(n, INT_MAX);\n\n    int cost = 0;\n    vector<Edge> choosed;\n\n    node_cheapest_cost[start_point] = 0;\n    for (auto const &e : adj_list[start_point]) {\n        s.insert(e);\n    }\n\n    while (s.size() > 0) {\n        auto curr_e = *s.begin();\n        s.erase(s.begin());\n        \/\/ lazy deletion\n        if (node_cheapest_cost[curr_e.to] < INT_MAX) {\n            continue;\n        }\n        cost += curr_e.cost;\n        node_cheapest_cost[curr_e.to] = curr_e.cost;\n        choosed.push_back(curr_e);\n        for (auto const &next_e : adj_list[curr_e.to]) {\n            \/\/ This is a must, otherwise it leads to an infinite queue in any undirected graphs\n            if (next_e.cost < node_cheapest_cost[next_e.to]) {\n                s.insert(next_e);\n            }\n        }\n    }\n\n    return {cost, choosed};\n}<\/code><\/pre>\n\n\n\n
Note that, if the number of edges are much larger than the number of nodes (e.g. complete graph<\/strong>). Brute force searching the cheapest edge O(V^2)<\/code> might be better than using priority queues.<\/p>\n\n\n\n
int minCostConnectPoints(vector<vector<int>>& points) {\n    int n = points.size();\n    ll cost = 0;\n\n    vector<bool> visited(n, false);\n    vector<int> min_cost_to_join(n, INT_MAX);\n    vector<vector<int>> cost_table(n, vector<int>(n, 0));\n    int node_joined = 0;\n\n    for (int i = 0; i < n; ++i) {\n        for (int j = 0; j < n; ++j) {\n            cost_table[i][j] = GetCost(points[i], points[j]);\n        }\n    }\n    min_cost_to_join[0] = 0;\n\n    while (node_joined < n) {\n        int curr_min_dist = INT_MAX;\n        int curr_min_node = -1;\n        for (int i = 0; i < n; ++i) {\n            if (!visited[i] && min_cost_to_join[i] < curr_min_dist) {\n                curr_min_dist = min_cost_to_join[i];\n                curr_min_node = i;\n            }\n        }\n\n        cost += curr_min_dist;\n        visited[curr_min_node] = true;\n        node_joined++;\n\n        for (int i = 0; i < n; ++i) {\n            if (!visited[i]) {\n                min_cost_to_join[i] = min(min_cost_to_join[i], cost_table[curr_min_node][i]);\n            }\n        }\n    }\n    return cost;\n}<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
Summary A spanning tree of some graph G is a subgraph that is a tree which includes all of the vertices of G, with a minimum possible number of edges. A Minimum Spanning Tree (MST) is a spanning tree whose sum of edge weights is as small as possible. Kruskal’s Algorithm Please refer to this page for its concepts and pseudo codes. The following code…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[48,66],"tags":[],"class_list":["post-1385","post","type-post","status-publish","format-standard","hentry","category-alg","category-graph-alg"],"_links":{"self":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1385","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/comments?post=1385"}],"version-history":[{"count":17,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1385\/revisions"}],"predecessor-version":[{"id":1508,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/posts\/1385\/revisions\/1508"}],"wp:attachment":[{"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/media?parent=1385"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/categories?post=1385"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/nanzhou.cc\/index.php\/wp-json\/wp\/v2\/tags?post=1385"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}