{"id":58,"date":"2020-05-09T02:04:31","date_gmt":"2020-05-09T02:04:31","guid":{"rendered":"http:\/\/sites.tntech.edu\/acrockett\/?p=58"},"modified":"2020-05-09T02:07:23","modified_gmt":"2020-05-09T02:07:23","slug":"prims-greedy-algorithm","status":"publish","type":"post","link":"https:\/\/sites.tntech.edu\/acrockett\/2020\/05\/09\/prims-greedy-algorithm\/","title":{"rendered":"Prims Greedy Algorithm"},"content":{"rendered":"\n<h2 class=\"wp-block-heading\">Problem Description<\/h2>\n\n\n\n<p><strong><u>Prim\u2019s algorithm<\/u><\/strong> uses the greedy approach to connect n points in the cheapest possible way to make a path.<\/p>\n\n\n\n<p>The <strong><u>greedy approach<\/u><\/strong> suggests a \u201cgreedy\u201d grab of the best alternative available in the hope that a sequence of optimal choices will yield an optimal solution to the whole problem.&nbsp; \u201cJump as close to the goal as possible on each move!\u201d<\/p>\n\n\n\n<p><strong>Prim\u2019s algorithm solves the <mark><span style=\"color:#cf2e2e\" class=\"tadv-color\">minimum spanning tree<\/span><\/mark> problem.<\/strong><\/p>\n\n\n\n<p>A <strong><u>spanning tree<\/u><\/strong> is a subset of an undirected connected graph.\u00a0 This subset is a connected acyclic tree that contains all vertices of the graph.<\/p>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"555\" src=\"https:\/\/sites.tntech.edu\/acrockett\/wp-content\/uploads\/sites\/108\/2020\/05\/image-1024x555.png\" alt=\"\" class=\"wp-image-59\" srcset=\"https:\/\/sites.tntech.edu\/acrockett\/wp-content\/uploads\/sites\/108\/2020\/05\/image-1024x555.png 1024w, https:\/\/sites.tntech.edu\/acrockett\/wp-content\/uploads\/sites\/108\/2020\/05\/image-300x163.png 300w, https:\/\/sites.tntech.edu\/acrockett\/wp-content\/uploads\/sites\/108\/2020\/05\/image-768x416.png 768w, https:\/\/sites.tntech.edu\/acrockett\/wp-content\/uploads\/sites\/108\/2020\/05\/image.png 1076w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<p>If a graph has weights assigned to its edges, a <strong><u>minimum spanning tree (MST)<\/u><\/strong> is a spanning tree that has the smallest weight of all other spanning trees of the graph, where weight is defined as the sum of weights on all edges.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\">Videos<\/h2>\n\n\n\n<figure class=\"wp-block-embed-youtube wp-block-embed is-type-video is-provider-youtube wp-embed-aspect-4-3 wp-has-aspect-ratio\"><div class=\"wp-block-embed__wrapper\">\n<iframe loading=\"lazy\" title=\"Prims Greedy Algorithm\" width=\"1140\" height=\"855\" src=\"https:\/\/www.youtube.com\/embed\/WQMhsgLMZOc?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe>\n<\/div><figcaption>Video made by April Crockett for Design of Algorithms in April 2020<\/figcaption><\/figure>\n\n\n\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=\"Prim&#039;s Algorithm - Review and Tutorial\" width=\"1140\" height=\"641\" src=\"https:\/\/www.youtube.com\/embed\/1DxW6Igy7UE?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe>\n<\/div><figcaption>Video made by Joe Doonis for Design of algorithms on May 4, 2020<br><\/figcaption><\/figure>\n\n\n\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=\"Prim&#039;s Algorithm In 7 Minutes\" width=\"1140\" height=\"641\" src=\"https:\/\/www.youtube.com\/embed\/-pGNDPIs2vA?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; encrypted-media; gyroscope; picture-in-picture\" allowfullscreen><\/iframe>\n<\/div><figcaption>Video made by Nicholas Vlahakos for Design of Algorithms in May 2020<br><\/figcaption><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\">Algorithm Steps Explained with Given Input<\/h2>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"873\" height=\"598\" src=\"https:\/\/sites.tntech.edu\/acrockett\/wp-content\/uploads\/sites\/108\/2020\/05\/image-1.png\" alt=\"\" class=\"wp-image-60\" srcset=\"https:\/\/sites.tntech.edu\/acrockett\/wp-content\/uploads\/sites\/108\/2020\/05\/image-1.png 873w, https:\/\/sites.tntech.edu\/acrockett\/wp-content\/uploads\/sites\/108\/2020\/05\/image-1-300x205.png 300w, https:\/\/sites.tntech.edu\/acrockett\/wp-content\/uploads\/sites\/108\/2020\/05\/image-1-768x526.png 768w\" sizes=\"auto, (max-width: 873px) 100vw, 873px\" \/><figcaption><br><\/figcaption><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1024\" height=\"534\" src=\"https:\/\/sites.tntech.edu\/acrockett\/wp-content\/uploads\/sites\/108\/2020\/05\/image-2-1024x534.png\" alt=\"\" class=\"wp-image-61\" srcset=\"https:\/\/sites.tntech.edu\/acrockett\/wp-content\/uploads\/sites\/108\/2020\/05\/image-2-1024x534.png 1024w, https:\/\/sites.tntech.edu\/acrockett\/wp-content\/uploads\/sites\/108\/2020\/05\/image-2-300x157.png 300w, https:\/\/sites.tntech.edu\/acrockett\/wp-content\/uploads\/sites\/108\/2020\/05\/image-2-768x401.png 768w, https:\/\/sites.tntech.edu\/acrockett\/wp-content\/uploads\/sites\/108\/2020\/05\/image-2.png 1261w\" sizes=\"auto, (max-width: 1024px) 100vw, 1024px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"981\" height=\"696\" src=\"https:\/\/sites.tntech.edu\/acrockett\/wp-content\/uploads\/sites\/108\/2020\/05\/image-3.png\" alt=\"\" class=\"wp-image-62\" srcset=\"https:\/\/sites.tntech.edu\/acrockett\/wp-content\/uploads\/sites\/108\/2020\/05\/image-3.png 981w, https:\/\/sites.tntech.edu\/acrockett\/wp-content\/uploads\/sites\/108\/2020\/05\/image-3-300x213.png 300w, https:\/\/sites.tntech.edu\/acrockett\/wp-content\/uploads\/sites\/108\/2020\/05\/image-3-768x545.png 768w\" sizes=\"auto, (max-width: 981px) 100vw, 981px\" \/><\/figure>\n\n\n\n<figure class=\"wp-block-image size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"1021\" height=\"383\" src=\"https:\/\/sites.tntech.edu\/acrockett\/wp-content\/uploads\/sites\/108\/2020\/05\/image-4.png\" alt=\"\" class=\"wp-image-63\" srcset=\"https:\/\/sites.tntech.edu\/acrockett\/wp-content\/uploads\/sites\/108\/2020\/05\/image-4.png 1021w, https:\/\/sites.tntech.edu\/acrockett\/wp-content\/uploads\/sites\/108\/2020\/05\/image-4-300x113.png 300w, https:\/\/sites.tntech.edu\/acrockett\/wp-content\/uploads\/sites\/108\/2020\/05\/image-4-768x288.png 768w\" sizes=\"auto, (max-width: 1021px) 100vw, 1021px\" \/><\/figure>\n\n\n\n<div class=\"wp-block-image\"><figure class=\"aligncenter size-large\"><img loading=\"lazy\" decoding=\"async\" width=\"303\" height=\"291\" src=\"https:\/\/sites.tntech.edu\/acrockett\/wp-content\/uploads\/sites\/108\/2020\/05\/image-5.png\" alt=\"\" class=\"wp-image-64\" srcset=\"https:\/\/sites.tntech.edu\/acrockett\/wp-content\/uploads\/sites\/108\/2020\/05\/image-5.png 303w, https:\/\/sites.tntech.edu\/acrockett\/wp-content\/uploads\/sites\/108\/2020\/05\/image-5-300x288.png 300w\" sizes=\"auto, (max-width: 303px) 100vw, 303px\" \/><\/figure><\/div>\n\n\n\n<h2 class=\"wp-block-heading\">Time Efficiency<\/h2>\n\n\n\n<p>\u2022The time efficiency of Prim\u2019s algorithm depends on the data structures used to implement the algorithm.<br>\u2022Using a weight matrix &amp; priority queue array, the efficiency is <strong>\u0398(|V|<\/strong><strong><sup>2<\/sup><\/strong><strong>)<br><\/strong> \u2022Using a weight matrix &amp; minimum heap, the effiency is <strong>O(|E| <\/strong><strong>log|V<\/strong><strong>|)<\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem Description Prim\u2019s algorithm uses the greedy approach to connect n points in the cheapest possible way to make a path. The greedy approach suggests a \u201cgreedy\u201d grab of the best alternative available in the hope that a sequence of optimal choices will yield an optimal solution to the whole problem.&nbsp; \u201cJump as close to [&hellip;]<\/p>\n","protected":false},"author":119,"featured_media":59,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[5],"tags":[4,6],"class_list":{"0":"post-58","1":"post","2":"type-post","3":"status-publish","4":"format-standard","5":"has-post-thumbnail","7":"category-algorithms","8":"tag-algorithms","9":"tag-greedy-algorithms","10":"czr-hentry"},"_links":{"self":[{"href":"https:\/\/sites.tntech.edu\/acrockett\/wp-json\/wp\/v2\/posts\/58","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/sites.tntech.edu\/acrockett\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/sites.tntech.edu\/acrockett\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/sites.tntech.edu\/acrockett\/wp-json\/wp\/v2\/users\/119"}],"replies":[{"embeddable":true,"href":"https:\/\/sites.tntech.edu\/acrockett\/wp-json\/wp\/v2\/comments?post=58"}],"version-history":[{"count":1,"href":"https:\/\/sites.tntech.edu\/acrockett\/wp-json\/wp\/v2\/posts\/58\/revisions"}],"predecessor-version":[{"id":65,"href":"https:\/\/sites.tntech.edu\/acrockett\/wp-json\/wp\/v2\/posts\/58\/revisions\/65"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/sites.tntech.edu\/acrockett\/wp-json\/wp\/v2\/media\/59"}],"wp:attachment":[{"href":"https:\/\/sites.tntech.edu\/acrockett\/wp-json\/wp\/v2\/media?parent=58"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/sites.tntech.edu\/acrockett\/wp-json\/wp\/v2\/categories?post=58"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/sites.tntech.edu\/acrockett\/wp-json\/wp\/v2\/tags?post=58"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}