Kruskal算法
<code class="hljs cs has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">const</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> MAXN = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1010</span>;
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">const</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> MAXM = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">200020</span>;
<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">struct</span> Edge
{<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">from</span>; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//邊的起點</span><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> to; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//邊的終點</span><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> w; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//權值</span>
}Edges[MAXM];<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> father[MAXN];<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> find(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> x)
{<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(x != father[x])father[x] = find(father[x]);<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> father[x];
}<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> cmp(Edge a,Edge b) <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//將邊按權值排序</span>
{<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(a.w != b.w)<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> a.w < b.w; <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//return a.w > b.w;求最大生成樹</span><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(a.<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">from</span> != b.<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">from</span>)<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> a.<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">from</span> < b.<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">from</span>;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> a.to < b.to;
}<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> Kruskal(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> N,<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> M)
{sort(Edges,Edges+M,cmp);<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//先將邊按權值排序</span><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> ans = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>,Count = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>;<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//Count表示合并的變數,ans存放MST大小</span><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> i = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>; i < M; i++){<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> u = find(Edges[i].<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">from</span>);<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> v = find(Edges[i].to);<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(u != v){ans += Edges[i].w;father[v] = u;Count++;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(Count == N-<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>)<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//合并了N-1條邊，已經找到了最小生成樹</span><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">break</span>;}}<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(Count == N-<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>) <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//找到最小生成樹</span><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> ans;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">else</span> <span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//圖不連通</span><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span> -<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>;
}
<span class="hljs-comment" style="color: rgb(136, 0, 0); box-sizing: border-box;">//初始化及構圖</span><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> i = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>; i < N; i++) father[i] = i; Sum = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> i = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>; i < M; i++) { scanf(<span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">"%d%d%d"</span>,&x,&y,&w); Edges[i].<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">from</span> = x; Edges[i].to = y; Edges[i].w = w; Sum += w; } <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> ans = Kruskal(); </code><ul class="pre-numbering" style="box-sizing: border-box; position: absolute; width: 50px; top: 0px; left: 0px; margin: 0px; padding: 6px 0px 40px; border-right-width: 1px; border-right-style: solid; border-right-color: rgb(221, 221, 221); list-style: none; text-align: right; background-color: rgb(238, 238, 238);"><li style="box-sizing: border-box; padding: 0px 5px;">1</li><li style="box-sizing: border-box; padding: 0px 5px;">2</li><li style="box-sizing: border-box; padding: 0px 5px;">3</li><li style="box-sizing: border-box; padding: 0px 5px;">4</li><li style="box-sizing: border-box; padding: 0px 5px;">5</li><li style="box-sizing: border-box; padding: 0px 5px;">6</li><li style="box-sizing: border-box; padding: 0px 5px;">7</li><li style="box-sizing: border-box; padding: 0px 5px;">8</li><li style="box-sizing: border-box; padding: 0px 5px;">9</li><li style="box-sizing: border-box; padding: 0px 5px;">10</li><li style="box-sizing: border-box; padding: 0px 5px;">11</li><li style="box-sizing: border-box; padding: 0px 5px;">12</li><li style="box-sizing: border-box; padding: 0px 5px;">13</li><li style="box-sizing: border-box; padding: 0px 5px;">14</li><li style="box-sizing: border-box; padding: 0px 5px;">15</li><li style="box-sizing: border-box; padding: 0px 5px;">16</li><li style="box-sizing: border-box; padding: 0px 5px;">17</li><li style="box-sizing: border-box; padding: 0px 5px;">18</li><li style="box-sizing: border-box; padding: 0px 5px;">19</li><li style="box-sizing: border-box; padding: 0px 5px;">20</li><li style="box-sizing: border-box; padding: 0px 5px;">21</li><li style="box-sizing: border-box; padding: 0px 5px;">22</li><li style="box-sizing: border-box; padding: 0px 5px;">23</li><li style="box-sizing: border-box; padding: 0px 5px;">24</li><li style="box-sizing: border-box; padding: 0px 5px;">25</li><li style="box-sizing: border-box; padding: 0px 5px;">26</li><li style="box-sizing: border-box; padding: 0px 5px;">27</li><li style="box-sizing: border-box; padding: 0px 5px;">28</li><li style="box-sizing: border-box; padding: 0px 5px;">29</li><li style="box-sizing: border-box; padding: 0px 5px;">30</li><li style="box-sizing: border-box; padding: 0px 5px;">31</li><li style="box-sizing: border-box; padding: 0px 5px;">32</li><li style="box-sizing: border-box; padding: 0px 5px;">33</li><li style="box-sizing: border-box; padding: 0px 5px;">34</li><li style="box-sizing: border-box; padding: 0px 5px;">35</li><li style="box-sizing: border-box; padding: 0px 5px;">36</li><li style="box-sizing: border-box; padding: 0px 5px;">37</li><li style="box-sizing: border-box; padding: 0px 5px;">38</li><li style="box-sizing: border-box; padding: 0px 5px;">39</li><li style="box-sizing: border-box; padding: 0px 5px;">40</li><li style="box-sizing: border-box; padding: 0px 5px;">41</li><li style="box-sizing: border-box; padding: 0px 5px;">42</li><li style="box-sizing: border-box; padding: 0px 5px;">43</li><li style="box-sizing: border-box; padding: 0px 5px;">44</li><li style="box-sizing: border-box; padding: 0px 5px;">45</li><li style="box-sizing: border-box; padding: 0px 5px;">46</li><li style="box-sizing: border-box; padding: 0px 5px;">47</li><li style="box-sizing: border-box; padding: 0px 5px;">48</li><li style="box-sizing: border-box; padding: 0px 5px;">49</li><li style="box-sizing: border-box; padding: 0px 5px;">50</li><li style="box-sizing: border-box; padding: 0px 5px;">51</li><li style="box-sizing: border-box; padding: 0px 5px;">52</li><li style="box-sizing: border-box; padding: 0px 5px;">53</li><li style="box-sizing: border-box; padding: 0px 5px;">54</li><li style="box-sizing: border-box; padding: 0px 5px;">55</li><li style="box-sizing: border-box; padding: 0px 5px;">56</li><li style="box-sizing: border-box; padding: 0px 5px;">57</li><li style="box-sizing: border-box; padding: 0px 5px;">58</li><li style="box-sizing: border-box; padding: 0px 5px;">59</li><li style="box-sizing: border-box; padding: 0px 5px;">60</li><li style="box-sizing: border-box; padding: 0px 5px;">61</li><li style="box-sizing: border-box; padding: 0px 5px;">62</li></ul>
Prim算法
<code class="hljs perl has-numbering" style="display: block; padding: 0px; color: inherit; box-sizing: border-box; font-family: 'Source Code Pro', monospace;font-size:undefined; white-space: pre; border-radius: 0px; word-wrap: normal; background: transparent;"><span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> G[<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">110</span>][<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">110</span>],vis[<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">110</span>],low[<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">110</span>],pre[<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">110</span>];
<span class="hljs-regexp" style="color: rgb(0, 136, 0); box-sizing: border-box;">//</span>G[][]存放圖，vis[]表示Va、Vb集合，low[]表示生成樹邊長集合
//pre[i]對應Dist[i]中所表示的最短邊，記錄當前點的父節點
void Prim(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> N)
{memset(vis,<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>,sizeof(vis));<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> ans = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>,<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">pos</span> = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>;<span class="hljs-regexp" style="color: rgb(0, 136, 0); box-sizing: border-box;">//ans</span>記錄MST大小，<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">pos</span>記錄加點位置vis[<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">pos</span>] = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; <span class="hljs-regexp" style="color: rgb(0, 136, 0); box-sizing: border-box;">//</span>low[<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">pos</span>] = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>; <span class="hljs-regexp" style="color: rgb(0, 136, 0); box-sizing: border-box;">//</span>無意義<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> i = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; i <= N; i++) //初始化{<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(i != <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">pos</span>){low[i] = G[<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">pos</span>][i];pre[i] = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>;}}<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> i = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; i < N; i++) //循環N-<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>次，每次加入一個點{<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> Min = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0xffffff0</span>;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">pos</span> = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> j = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; j <= N; j++){<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(!vis[j] && low[j] < Min){Min = low[j];<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">pos</span> = j;}}<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">pos</span> == <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0</span>) <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">return</span>; <span class="hljs-regexp" style="color: rgb(0, 136, 0); box-sizing: border-box;">//</span>沒有點可以擴展，圖G不連通，可用于判斷聯通ans += Min; <span class="hljs-regexp" style="color: rgb(0, 136, 0); box-sizing: border-box;">//</span>添加邊vis[<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">pos</span>] = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>;<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> j = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; j <= N; j++) //對每個與<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">pos</span>點相鄰的未遍歷的點j，更新到j點最近的點及距離{<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">if</span>(!vis[j] && low[j] > G[<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">pos</span>][j]){low[j] = G[<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">pos</span>][j];pre[j] = <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">pos</span>;}}}<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">printf</span>(<span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">"<span class="hljs-variable" style="color: rgb(102, 0, 102); box-sizing: border-box;">%d</span>\n"</span>,ans);}//初始化調用<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> i = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; i <= N; i++) <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> j = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; j <= N; j++) G[i][j] = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">0xffffff0</span>; <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">for</span>(<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">int</span> i = <span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>; i <= n<span class="hljs-variable" style="color: rgb(102, 0, 102); box-sizing: border-box;">*(</span>n-<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">1</span>)/<span class="hljs-number" style="color: rgb(0, 102, 102); box-sizing: border-box;">2</span>; i++) { scanf(<span class="hljs-string" style="color: rgb(0, 136, 0); box-sizing: border-box;">"<span class="hljs-variable" style="color: rgb(102, 0, 102); box-sizing: border-box;">%d</span><span class="hljs-variable" style="color: rgb(102, 0, 102); box-sizing: border-box;">%d</span><span class="hljs-variable" style="color: rgb(102, 0, 102); box-sizing: border-box;">%d</span>"</span>,&<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">x</span>,&<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">y</span>,&d); <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">map</span>[<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">x</span>][<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">y</span>] = <span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">map</span>[<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">y</span>][<span class="hljs-keyword" style="color: rgb(0, 0, 136); box-sizing: border-box;">x</span>] = d; } </code>
《新程序員》：云原生和全面數字化實踐50位技術專家共同創作，文字、視頻、音頻交互閱讀
總結
以上是生活随笔為你收集整理的最小生成树【模板】的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
