ds7.4.3.htm

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

</span><span lang="EN-US" style="font-family: Symbol; 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; mso-char-type: symbol">&sup1;</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"> 
</span><span lang="EN-US" style="font-family: 楷体_GB2312; mso-ascii-font-family: 楷体_GB2312; 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">-</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">1</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><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">&amp;&amp;</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><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[i]</span><span style="font-family: 楷体_GB2312; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 3">最小</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-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 3"> 
</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">i</span></b>，<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 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">v</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><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; mso-color-index: 3">(</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[v], 
v)</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="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[v]</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></b></font></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"> 
</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[v]  
</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-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical"> 
</span><span style="font-family: 楷体_GB2312; mso-ascii-font-family: 楷体_GB2312; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 3">-</span><span style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 3">1</span><span style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical">,<span style="mso-spacerun: yes">&nbsp;  
</span></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-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; mso-color-index: 3">(  
</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[v], 
v, lowcost[v] ) </span><span style="mso-spacerun: yes; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-fareast-language: ZH-CN" lang="EN-US">&nbsp;</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"><font color="#FFFFFF" size="5"><b><span style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical"><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 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[i]  
= min{ lowcost[i], Edge[v][i]</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><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">}</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><span style="font-family: 楷体_GB2312; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 3">生成树顶点集合外各顶点</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">i</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><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="font-family: 楷体_GB2312; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 3">刚加入该集合的新顶点</span><span style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 3"> 
</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">v</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><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-color-index: 3; mso-fareast-language: ZH-CN">Edge[v][i]</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><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-color-index: 3; mso-fareast-language: ZH-CN">lowcost[i]</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><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">&nbsp;  
</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></b></font><span style="mso-fareast-font-family:楷体_GB2312;
mso-hansi-font-family:&quot;Times New Roman&quot;;font-size:133%;text-shadow:auto;
layout-flow:vertical"><b><span style="mso-spacerun: yes"></span></b></span></p>
<p ALIGN="JUSTIFY"><font color="#FFFFFF" size="5"><b><span style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical"><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="font-family: 楷体_GB2312; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 3">生成树顶点集合外顶点</span><span style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 3"> 
</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">i  
</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="font-family: 楷体_GB2312; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 3">刚加入该集合的新顶点</span><span style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical; mso-color-index: 3"> 
</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">v  
</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">nearvex[i]</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 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]  
= v</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><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">i</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">v</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></b></font></p> 
<p ALIGN="JUSTIFY"><img border="0" src="ds7.4.8.gif" width="1208" height="696"></p>
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b><span style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; layout-flow: vertical"><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></b></font></p>
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><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; layout-flow: vertical"><span style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; layout-flow: vertical; mso-color-index: 3">(0,  
5, 10), (5, 4, 25), (4, 3, 22),</span></span></b></font></p> 
<p ALIGN="JUSTIFY"><font size="5" color="#FFFFFF"><b><span style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; layout-flow: vertical; mso-color-index: 3">&nbsp;</span><span style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; layout-flow: vertical"><span style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; layout-flow: vertical; mso-color-index: 3">(3,  
2, 12), (2, 1, 16), (1, 6, 14)</span></span></b></font></p> 
<p ALIGN="JUSTIFY">　</p>
<p ALIGN="center"><b><font size="5"><a href="ds7.4.htm"><font color="#FFFF00">返回</font></a></font></b></p>
<!--mstheme--></font>

</body>

</html>