{"id":6124,"date":"2020-01-24T07:59:23","date_gmt":"2020-01-24T15:59:23","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=6124"},"modified":"2020-01-26T10:04:27","modified_gmt":"2020-01-26T18:04:27","slug":"minimum-spanning-tree-sp18","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/sp\/minimum-spanning-tree-sp18\/","title":{"rendered":"\u82b1\u82b1\u9171 Minimum Spanning Tree (MST) \u6700\u5c0f\u751f\u6210\u6811 SP18"},"content":{"rendered":"\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-16-9 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 \u6700\u5c0f\u751f\u6210\u6811 (Minimum Spanning Tree) \u5237\u9898\u627e\u5de5\u4f5c SP18\" width=\"500\" height=\"281\" src=\"https:\/\/www.youtube.com\/embed\/wmW8G8SrXDs?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe>\n<\/div><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Prim&#8217;s Algorithm<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(ElogV)<br>Space complexity: O(V+E)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\n#include <iostream>\n#include <queue>\n#include <vector>\nusing namespace std;\n\nint main(int argc, char** argv) {\n  const int n = 4;\n  vector<vector<int>> edges{{0,1,1},{0,3,3},{0,2,6},{2,3,2},{1,2,4},{1,3,5}};\n  vector<vector<pair<int, int>>> g(n);\n  for (const auto& e : edges) {\n    g[e[0]].emplace_back(e[1], e[2]);\n    g[e[1]].emplace_back(e[0], e[2]);\n  }\n\n  priority_queue<pair<int, int>> q; \/\/ (-w, v)\n  vector<int> seen(n);\n  q.emplace(0, 0); \/\/ (-w, v)\n\n  int cost = 0;\n  for (int i = 0; i < n; ++i) {\n    while (true) {\n      const int w = -q.top().first;\n      const int v = q.top().second;\n      q.pop();\n      if (seen[v]++) continue;\n      cost += w;\n      for (const auto&#038; p : g[v]) {\n        if (seen[p.first]) continue;\n        q.emplace(-p.second, p.first);\n      }\n      break;\n    }\n  }\n  cout << cost << endl;\n  return 0;\n}\n<\/pre>\n<\/div><\/div>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">Python<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\"># Author: Huahua\nfrom collections import defaultdict\nfrom heapq import *\n\nn = 4\nedges = [[0,1,1],[0,3,3],[0,2,6],[2,3,2],[1,2,4],[1,3,5]]\ng = defaultdict(list)\nfor e in edges:\n  g[e[0]].append((e[1], e[2]))\n  g[e[1]].append((e[0], e[2]))\n\nq = []\ncost = 0\nseen = set()\nheappush(q, (0, 0))\nfor _ in range(n):\n  while True:\n    w, u = heappop(q)\n    if u in seen: continue  \n    cost += w\n    seen.add(u)\n    for v, w in g[u]:\n      if v in seen: continue\n      heappush(q, (w, v))\n    break\n\nprint(cost)\n<\/pre>\n<\/div><\/div>\n\n\n\n<h2 class=\"wp-block-heading\"><strong>Kruskal's Algorithm<\/strong><\/h2>\n\n\n\n<p>Time complexity: O(ElogV)<br>Space complexity: O(V+E)<\/p>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"C++\">\n\/\/ Author: Huahua\n#include <iostream>\n#include <queue>\n#include <vector>\n#include <functional>\n#include <numeric>\nusing namespace std;\n\nint main(int argc, char** argv) {\n  const int n = 4;\n  vector<vector<int>> edges{{0,1,1},{0,3,3},{0,2,6},{2,3,2},{1,2,4},{1,3,5}};    \n  vector<vector<int>> q; \/\/ (w, u, v)  \n  for (const auto& e : edges)    \n    q.push_back({e[2], e[0], e[1]});\n  sort(begin(q), end(q));\n\n  vector<int> p(n);\n  iota(begin(p), end(p), 0);\n\n  function<int(int)> find = [&](int x) {\n    return x == p[x] ? x : p[x] = find(p[p[x]]);\n  };\n\n  int cost = 0;\n  for (const auto& t : q) {    \n    int w = t[0], u = t[1], v = t[2];      \n    int ru = find(u), rv = find(v);      \n    if (ru == rv) continue;\n    p[ru] = rv; \/\/ merge (u, v)      \n    cost += w;\n  }  \n  cout << cost << endl;\n\n  return 0;\n}\n<\/pre>\n<\/div><\/div>\n\n\n\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">Python<\/h2>\n<div class=\"tabcontent\">\n\n<pre lang=\"python\">from collections import defaultdict\nfrom heapq import *\n\nn = 4\nedges = [[0,1,1],[0,3,3],[0,2,6],[2,3,2],[1,2,4],[1,3,5]]\np = list(range(n))\n\n\ndef find(x):\n  if x != p[x]: p[x] = find(p[p[x]])\n  return p[x]\n\ncost = 0\nfor u, v, w in sorted(edges, key=lambda x: x[2]):\n  ru, rv = find(u), find(v)\n  if ru == rv: continue\n  p[ru] = rv\n  cost += w\n\nprint(cost)\n<\/pre>\n<\/div><\/div>\n\n\n\n<p><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Prim&#8217;s Algorithm Time complexity: O(ElogV)Space complexity: O(V+E) \/\/ Author: Huahua #include #include #include using namespace std; int main(int argc, char** argv) { const int n&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[170],"tags":[77,533,534],"class_list":["post-6124","post","type-post","status-publish","format-standard","hentry","category-sp","tag-graph","tag-mst","tag-oelogv","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6124","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=6124"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6124\/revisions"}],"predecessor-version":[{"id":6141,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/6124\/revisions\/6141"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=6124"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=6124"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=6124"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}