-
Notifications
You must be signed in to change notification settings - Fork 0
/
algo_kruskal.html
217 lines (193 loc) · 17.3 KB
/
algo_kruskal.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
<!DOCTYPE html>
<html lang="zh_cn">
<head>
<meta charset="utf-8">
<meta http-equiv="X-UA-Compatible" content="IE=edge">
<meta name="viewport" content="width=device-width, initial-scale=1">
<meta name="description" content="今天学习了算法4书上面的Kruskal最小生成树算法。 Kruskal算法将所有的边都加入到优先队列中，每次取得最小的边，并使用union-find的方法来判断无效边。...">
<meta name="keywords" content="Algorithm, Graph, Python3">
<link rel="icon" href="./favicon.ico">
<title>【算法学习】Kruskal算法 - Rivarrl</title>
<!-- Stylesheets -->
<link href="./css/bootstrap.min.css" rel="stylesheet">
<link href="./css/fonts.css" rel="stylesheet">
<link href="./css/nest.css" rel="stylesheet">
<link href="./css/pygment.css" rel="stylesheet">
<!-- /Stylesheets -->
<!-- RSS Feeds -->
<!-- /RSS Feeds -->
<!-- HTML5 shim and Respond.js for IE8 support of HTML5 elements and media queries -->
<!--[if lt IE 9]>
<script src="https://oss.maxcdn.com/html5shiv/3.7.2/html5shiv.min.js"></script>
<script src="https://oss.maxcdn.com/respond/1.4.2/respond.min.js"></script>
<![endif]-->
<!-- mathjax config similar to math.stackexchange -->
<script type="text/x-mathjax-config">
MathJax.Hub.Config({
jax: ["input/TeX", "output/HTML-CSS"],
tex2jax: {
inlineMath: [ ['$', '$'] ],
displayMath: [ ['$$', '$$']],
processEscapes: true,
skipTags: ['script', 'noscript', 'style', 'textarea', 'pre', 'code']
},
messageStyle: "none",
"HTML-CSS": { preferredFont: "TeX", availableFonts: ["STIX","TeX"] }
});
</script>
<script type="text/javascript" src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.1/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
</head>
<body>
<!-- Header -->
<div class="header-container" style="background: linear-gradient(rgba(0, 0, 0, 0.2), rgba(0, 0, 0, 0.2)), url('./images/background.jpg'); background-position: center; background-size: cover;">
<!-- Static navbar -->
<div class="container">
<div class="header-nav">
<div class="header-logo">
<a class="pull-left" href="./"><img class="mr20" src="./images/logo.png" alt="logo">Rivarrl</a>
</div>
<div class="nav pull-right">
<a href="./">Homepage</a>
<a href="./categories.html">Categories</a>
</div>
</div>
</div>
<!-- /Static navbar -->
<!-- Header -->
<!-- Header -->
<div class="container header-wrapper">
<div class="row">
<div class="col-lg-12">
<div class="header-content">
<h1 class="header-title">【算法学习】Kruskal算法</h1>
<p class="header-date">By <a href="./author/rivarrl.html">Rivarrl</a>, 2019-11-23 22:33:00, modified 2019-11-23 22:33:00, in category <a href="./category/algorithm.html">Algorithm</a></p>
<div class="header-underline"></div>
<div class="clearfix"></div>
<p class="pull-right header-tags">
<span class="glyphicon glyphicon-tags mr5" aria-hidden="true"></span>
<a href="./tag/algorithm.html">Algorithm</a>, <a href="./tag/graph.html">Graph</a>, <a href="./tag/python3.html">Python3</a> </p>
</div>
</div>
</div>
</div>
<!-- /Header -->
<!-- /Header -->
</div>
<!-- /Header -->
<!-- Content -->
<div class="container content">
<blockquote>
<p>今天学习了算法4书上面的Kruskal最小生成树算法。 </p>
<p>Kruskal算法将所有的边都加入到优先队列中，每次取得最小的边，并使用union-find的方法来判断无效边。 </p>
<p>上面的第一句很好理解，每次找到全局最短的边，作为最小生成树的一个边。相当于每次找到两个点，把它们连起来(union)，将它们的连通性记录下来，为后面新的边是否有效做判断(find)。这种问题是典型的动态连通性问题，用union-find。</p>
</blockquote>
<p>如果不了解union-find，可以跳转学习<a href="https://rivarrl.github.io/algo_union_find">前置技能点：union-find</a></p>
<p>代码：</p>
<div class="highlight"><pre><span></span><span class="kn">import</span> <span class="nn">heapq</span>
<span class="c1"># Kruskal算法求最小生成树</span>
<span class="k">def</span> <span class="nf">kruskal</span><span class="p">(</span><span class="n">n</span><span class="p">,</span> <span class="n">graph</span><span class="p">):</span>
<span class="c1"># 加权quick-union</span>
<span class="n">uf</span> <span class="o">=</span> <span class="n">WeightedQuickUnionUF</span><span class="p">(</span><span class="n">n</span><span class="p">)</span>
<span class="n">pq</span> <span class="o">=</span> <span class="p">[]</span>
<span class="n">res</span> <span class="o">=</span> <span class="p">[]</span>
<span class="k">for</span> <span class="n">u</span> <span class="ow">in</span> <span class="nb">range</span><span class="p">(</span><span class="n">n</span><span class="p">):</span>
<span class="n">e</span> <span class="o">=</span> <span class="n">graph</span><span class="p">[</span><span class="n">u</span><span class="p">]</span>
<span class="k">while</span> <span class="n">e</span><span class="p">:</span>
<span class="n">heapq</span><span class="o">.</span><span class="n">heappush</span><span class="p">(</span><span class="n">pq</span><span class="p">,</span> <span class="n">e</span><span class="p">)</span>
<span class="n">e</span> <span class="o">=</span> <span class="n">e</span><span class="o">.</span><span class="n">next</span>
<span class="k">while</span> <span class="n">pq</span> <span class="ow">and</span> <span class="nb">len</span><span class="p">(</span><span class="n">res</span><span class="p">)</span> <span class="o"><</span> <span class="n">n</span> <span class="o">-</span> <span class="mi">1</span><span class="p">:</span>
<span class="n">e</span> <span class="o">=</span> <span class="n">heapq</span><span class="o">.</span><span class="n">heappop</span><span class="p">(</span><span class="n">pq</span><span class="p">)</span>
<span class="n">u</span><span class="p">,</span> <span class="n">v</span> <span class="o">=</span> <span class="n">e</span><span class="o">.</span><span class="n">u</span><span class="p">,</span> <span class="n">e</span><span class="o">.</span><span class="n">v</span>
<span class="c1"># 忽略失效边</span>
<span class="k">if</span> <span class="n">uf</span><span class="o">.</span><span class="n">connected</span><span class="p">(</span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">):</span> <span class="k">continue</span>
<span class="c1"># 添加新边时将边两端的节点连通</span>
<span class="n">uf</span><span class="o">.</span><span class="n">union</span><span class="p">(</span><span class="n">u</span><span class="p">,</span> <span class="n">v</span><span class="p">)</span>
<span class="n">res</span><span class="o">.</span><span class="n">append</span><span class="p">(</span><span class="n">e</span><span class="p">)</span>
<span class="k">for</span> <span class="n">e</span> <span class="ow">in</span> <span class="n">res</span><span class="p">:</span>
<span class="k">print</span><span class="p">(</span><span class="s2">"</span><span class="si">%d</span><span class="s2"> -[</span><span class="si">%.2f</span><span class="s2">]- </span><span class="si">%d</span><span class="s2">"</span> <span class="o">%</span> <span class="p">(</span><span class="n">e</span><span class="o">.</span><span class="n">u</span><span class="p">,</span> <span class="n">e</span><span class="o">.</span><span class="n">w</span><span class="p">,</span> <span class="n">e</span><span class="o">.</span><span class="n">v</span><span class="p">))</span>
<span class="k">if</span> <span class="vm">__name__</span> <span class="o">==</span> <span class="s1">'__main__'</span><span class="p">:</span>
<span class="n">graph</span> <span class="o">=</span> <span class="n">build_graph</span><span class="p">(</span><span class="mi">8</span><span class="p">,</span> <span class="p">[[</span><span class="mi">4</span><span class="p">,</span> <span class="mi">5</span><span class="p">,</span> <span class="o">.</span><span class="mi">35</span><span class="p">],</span> <span class="p">[</span><span class="mi">4</span><span class="p">,</span> <span class="mi">7</span><span class="p">,</span> <span class="o">.</span><span class="mi">37</span><span class="p">],</span> <span class="p">[</span><span class="mi">5</span><span class="p">,</span> <span class="mi">7</span><span class="p">,</span> <span class="o">.</span><span class="mi">28</span><span class="p">],</span> <span class="p">[</span><span class="mi">0</span><span class="p">,</span> <span class="mi">7</span><span class="p">,</span> <span class="o">.</span><span class="mi">16</span><span class="p">],</span> <span class="p">[</span><span class="mi">1</span><span class="p">,</span> <span class="mi">5</span><span class="p">,</span> <span class="o">.</span><span class="mi">32</span><span class="p">],</span> <span class="p">[</span><span class="mi">0</span><span class="p">,</span> <span class="mi">4</span><span class="p">,</span> <span class="o">.</span><span class="mi">38</span><span class="p">],</span> <span class="p">[</span><span class="mi">2</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="o">.</span><span class="mi">17</span><span class="p">],</span>
<span class="p">[</span><span class="mi">1</span><span class="p">,</span> <span class="mi">7</span><span class="p">,</span> <span class="o">.</span><span class="mi">19</span><span class="p">],</span> <span class="p">[</span><span class="mi">0</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="o">.</span><span class="mi">26</span><span class="p">],</span> <span class="p">[</span><span class="mi">1</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="o">.</span><span class="mi">36</span><span class="p">],</span> <span class="p">[</span><span class="mi">1</span><span class="p">,</span> <span class="mi">3</span><span class="p">,</span> <span class="o">.</span><span class="mi">29</span><span class="p">],</span> <span class="p">[</span><span class="mi">2</span><span class="p">,</span> <span class="mi">7</span><span class="p">,</span> <span class="o">.</span><span class="mi">34</span><span class="p">],</span> <span class="p">[</span><span class="mi">6</span><span class="p">,</span> <span class="mi">2</span><span class="p">,</span> <span class="o">.</span><span class="mi">40</span><span class="p">],</span> <span class="p">[</span><span class="mi">3</span><span class="p">,</span> <span class="mi">6</span><span class="p">,</span> <span class="o">.</span><span class="mi">52</span><span class="p">],</span>
<span class="p">[</span><span class="mi">6</span><span class="p">,</span> <span class="mi">0</span><span class="p">,</span> <span class="o">.</span><span class="mi">58</span><span class="p">],</span> <span class="p">[</span><span class="mi">6</span><span class="p">,</span> <span class="mi">4</span><span class="p">,</span> <span class="o">.</span><span class="mi">93</span><span class="p">]],</span>
<span class="n">direction</span><span class="o">=</span><span class="mi">0</span><span class="p">,</span> <span class="n">tp</span><span class="o">=</span><span class="mi">2</span><span class="p">)</span>
<span class="n">kruskal</span><span class="p">(</span><span class="mi">8</span><span class="p">,</span> <span class="n">graph</span><span class="p">)</span>
</pre></div>
<p>打印结果： </p>
<div class="highlight"><pre><span></span><span class="mi">0</span> <span class="o">-</span><span class="p">[</span><span class="mi">0</span><span class="p">.</span><span class="mi">16</span><span class="p">]</span><span class="o">-</span> <span class="mi">7</span>
<span class="mi">3</span> <span class="o">-</span><span class="p">[</span><span class="mi">0</span><span class="p">.</span><span class="mi">17</span><span class="p">]</span><span class="o">-</span> <span class="mi">2</span>
<span class="mi">1</span> <span class="o">-</span><span class="p">[</span><span class="mi">0</span><span class="p">.</span><span class="mi">19</span><span class="p">]</span><span class="o">-</span> <span class="mi">7</span>
<span class="mi">0</span> <span class="o">-</span><span class="p">[</span><span class="mi">0</span><span class="p">.</span><span class="mi">26</span><span class="p">]</span><span class="o">-</span> <span class="mi">2</span>
<span class="mi">7</span> <span class="o">-</span><span class="p">[</span><span class="mi">0</span><span class="p">.</span><span class="mi">28</span><span class="p">]</span><span class="o">-</span> <span class="mi">5</span>
<span class="mi">5</span> <span class="o">-</span><span class="p">[</span><span class="mi">0</span><span class="p">.</span><span class="mi">35</span><span class="p">]</span><span class="o">-</span> <span class="mi">4</span>
<span class="mi">2</span> <span class="o">-</span><span class="p">[</span><span class="mi">0</span><span class="p">.</span><span class="mi">40</span><span class="p">]</span><span class="o">-</span> <span class="mi">6</span>
</pre></div>
<blockquote>
<p>Kruskal算法的完整过程，可以想象成这样一个变化过程：<br>
每次找到一个零散的树枝，最后慢慢拼接成完整的一棵树。（星星之火可以燎原，个人认为这句话很适合形容这个过程）</p>
</blockquote>
</div>
<!-- /Content -->
<!-- Footer -->
<div class="footer gradient-2">
<div class="container footer-container ">
<div class="row">
<div class="col-xs-4 col-sm-3 col-md-3 col-lg-3">
<div class="footer-title">Sitemap</div>
<ul class="list-unstyled">
<li><a href="./archives.html">Archives</a></li>
<li><a href="./tags.html">Tags</a></li>
<li><a href="./authors.html">Authors</a></li>
</ul>
</div>
<div class="col-xs-4 col-sm-3 col-md-3 col-lg-3">
<div class="footer-title">Social</div>
<ul class="list-unstyled">
<li><a href="tencent://message/?uin=1049793871&Site=Sambow&Menu=yes" target="_blank">QQ</a></li>
<li><a href="http://github.com/Rivarrl" target="_blank">GitHub</a></li>
</ul>
</div>
<div class="col-xs-4 col-sm-3 col-md-3 col-lg-3">
<div class="footer-title">Links</div>
<ul class="list-unstyled">
<li><a href="http://getpelican.com/" target="_blank">Pelican</a></li>
<li><a href="http://python.org/" target="_blank">Python.org</a></li>
<li><a href="http://jinja.pocoo.org/" target="_blank">Jinja2</a></li>
</ul>
</div>
<div class="col-xs-12 col-sm-3 col-md-3 col-lg-3">
<p class="pull-right text-right">
<small><em>Proudly powered by <a href="http://docs.getpelican.com/" target="_blank">pelican</a></em></small><br/>
<small><em>Theme and code by <a href="https://github.com/molivier" target="_blank">molivier</a></em></small><br/>
<small>© Rivarrl 2018</small>
</p>
</div>
</div>
</div>
</div>
<!-- /Footer -->
<!-- live2d -->
<script src="./js/L2Dwidget.min.js"></script>
<script src="./js/L2Dwidget.0.min.js"></script>
<script>
L2Dwidget.init({
"model":{
"scale":1,"hHeadPos":0.5,"vHeadPos":0.618,
"jsonPath": "./live2d-models/live2d-widget-model-tororo/assets/tororo.model.json"
},
"display":{
"superSample":2,"width":100,"height":220,"position":"right","hOffset":-30,"vOffset":-200
},
"mobile":{
"show":false,"scale":0.5
},
"react":{
"opacityDefault":0.9,"opacityOnHover":0.2
}
});
</script>
<div id="live2d-widget">
<canvas id="live2dcanvas" width="200" height="440"
style="position: fixed; opacity: 1; right: 0px; bottom: 0; z-index: 99999; pointer-events: none;"></canvas>
</div>
</body>
</html>