ds7.4.3.htm

这是清华大学所用的数据结构的电子版教材

设有一个有</font><font SIZE="5"> </font><font FACE="Times New Roman" SIZE="5">n  
</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">个顶点的连通网络</font><font SIZE="5"> 
</font><font FACE="Times New Roman" SIZE="5">N = { V, E },</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">最初先构造一个只有</font><font SIZE="5">  
</font><font FACE="Times New Roman" SIZE="5">n </font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">个顶点，没有边的非连通图</font><font SIZE="5">  
</font><font FACE="Times New Roman" SIZE="5">T = { V, <font FACE="Symbol">&AElig;</font>  
}, </font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">图中每个顶点自成一个连通分量。当在</font><font SIZE="5">  
</font><font FACE="Times New Roman" SIZE="5">E </font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">中选到一条具有最小权值的边时</font><font FACE="Times New Roman" SIZE="5">,</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">若该边的两个顶点落在不同的连通分量上，则将此边加入到</font><font SIZE="5">  
</font><font FACE="Times New Roman" SIZE="5">T </font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">中；否则将此边舍去，重新选择一条权值最小的边。如此重复下去，直到所有顶点在同一个连通分量上为止。</font></font></p> 
<p><font color="#FFFFFF" size="5"><span style="font-family: 楷体_GB2312; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical">应用克鲁斯卡尔算法构造最小生成树的过程</span></font></p>
<p><img border="0" src="ds7.4.4.gif" width="962" height="600"></p>
<!--mstheme--></font>
<!--msthemelist--><table border="0" cellpadding="0" cellspacing="0" width="100%">
  <!--msthemelist--><tr>
    <!--msthemelist--><td valign="baseline" width="42"><img src="aricebu1.gif" width="15" height="15" hspace="13"></td>
    <td valign="top" width="100%"><!--mstheme--><font face="宋体"><font size="5" color="#FFFFFF"><font FACE="楷体_GB2312" LANG="ZH-CN">普里姆</font><font FACE="Times New Roman">(Prim)</font><font FACE="楷体_GB2312" LANG="ZH-CN">算法</font></font><!--mstheme--></font><!--msthemelist--></td>
  </tr>
<!--msthemelist--></table>
<!--mstheme--><font face="宋体">
<p><font FACE="楷体_GB2312" LANG="ZH-CN" size="5" color="#FFFFFF">普里姆算法的基本思想：</font></p>
<font FACE="Times New Roman" SIZE="5" COLOR="#0000ff">
<p></font><font size="5" color="#FFFFFF"><font FACE="楷体_GB2312" LANG="ZH-CN">&nbsp;  
从连通网络</font> <font FACE="Times New Roman">N = { V, E }</font><font FACE="楷体_GB2312" LANG="ZH-CN">中的某一顶点</font>  
<font FACE="Times New Roman">u</font><sub><font FACE="Times New Roman">0 </font></sub><font FACE="楷体_GB2312" LANG="ZH-CN">出发，选择与它关联的具有最小权值的边</font><font FACE="Times New Roman">(u<sub>0</sub>,  
v)</font><font FACE="楷体_GB2312" LANG="ZH-CN">，将其顶点加入到生成树的顶点集合</font><font FACE="Times New Roman">U</font><font FACE="楷体_GB2312" LANG="ZH-CN">中。</font></font></p>
<font FACE="Times New Roman" SIZE="5" COLOR="#0000ff">
<p></font><font size="5" color="#FFFFFF"><font FACE="楷体_GB2312" LANG="ZH-CN">&nbsp;  
以后每一步从一个顶点在</font><font FACE="Times New Roman">U</font><font FACE="楷体_GB2312" LANG="ZH-CN">中，而另一个顶点不在</font><font FACE="Times New Roman">U</font><font FACE="楷体_GB2312" LANG="ZH-CN">中的各条边中选择权值最小的边</font><font FACE="Times New Roman">(u,  
v),</font><font FACE="楷体_GB2312" LANG="ZH-CN">把它的顶点加入到集合</font><font FACE="Times New Roman">U</font><font FACE="楷体_GB2312" LANG="ZH-CN">中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合</font><font FACE="Times New Roman">U</font><font FACE="楷体_GB2312" LANG="ZH-CN">中为止。</font></font></p>
<p><span style="font-family: 楷体_GB2312; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical"><font size="5" color="#FFFFFF">用普里姆算法构造最小生成树的过程</font></span></p>
</b>
<p align="center"><img border="0" src="ds7.4.5.gif" align="middle" width="963" height="640"></p>
<b>
<p><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5" color="#FFFFFF">采用邻接矩阵作为图的存储表示。</font></p>
<p ALIGN="JUSTIFY"><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5" color="#FFFFFF">在构造过程中，还设置了两个辅助数组：</font></p>
<font FACE="Times New Roman" SIZE="5" COLOR="#0000ff">
<p ALIGN="JUSTIFY"></font><font color="#FFFFFF"><font FACE="Times New Roman" SIZE="5">&nbsp;&nbsp;  
lowcost</font><font FACE="Times New Roman" SIZE="5">[ ] </font><font FACE="楷体_GB2312" LANG="ZH-CN" color="#FFFFFF" size="5">:</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">存放生成树顶点集合内顶点到生成树外各顶点的各边上的当前最小权值；</font></font></p>
<font FACE="Times New Roman" SIZE="5" COLOR="#0000ff">
<p ALIGN="JUSTIFY"></font><font color="#FFFFFF"><font FACE="Times New Roman" SIZE="5">&nbsp;  
nearvex</font><font FACE="Times New Roman" SIZE="5">[ ] </font><font FACE="楷体_GB2312" LANG="ZH-CN" color="#FFFFFF" size="5">:</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">记录生成树顶点集合外各顶点距离集合内哪个顶点最近</font><font FACE="Times New Roman" SIZE="5">(</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">即权值最小</font><font FACE="Times New Roman" SIZE="5">)</font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">。</font></font></p>
<blockquote>
  <p ALIGN="JUSTIFY"><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5" color="#FFFFFF">例子</font></p>
</blockquote>
</b>
<p ALIGN="JUSTIFY"><img border="0" src="ds7.4.6.gif" width="915" height="372"></p>
<p ALIGN="JUSTIFY"><font color="#FFFFFF" size="5"><b><span style="font-family: 楷体_GB2312; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical">&nbsp;  
若选择从顶点</span><span style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical">0</span><span style="font-family: 楷体_GB2312; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical">出发，即</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-fareast-language: ZH-CN">u</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; position: relative; top: .37em; mso-text-raise: -25%; mso-fareast-language: ZH-CN">0</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-fareast-language: ZH-CN"><span style="mso-spacerun: yes">&nbsp;</span>=  
0</span><span lang="EN-US" style="font-family: 楷体_GB2312; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-fareast-language: ZH-CN">，则两个辅助数</span><span style="font-family: 楷体_GB2312; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical">组的初始状态为：</span></b></font></p>
<p ALIGN="JUSTIFY"><img border="0" src="ds7.4.7.gif" width="1120" height="88"></p>
<p ALIGN="JUSTIFY"><font color="#FFFFFF" size="5"><b><span style="font-family: 楷体_GB2312; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical">然后反复做以下工作：</span></b></font></p>
<p ALIGN="JUSTIFY">&nbsp;&nbsp; <font color="#FFFFFF" size="5"><b><span style="font-family: 楷体_GB2312; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical">在</span><span style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical">  
</span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 3; mso-fareast-language: ZH-CN">lowcost 
[ ]</span><span style="font-family: 楷体_GB2312; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical">中选择</span><span style="mso-spacerun: yes; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical"></span><span lang="EN-US" style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 3; mso-fareast-language: ZH-CN">nearvex[i]