📄 ds7.4.3.htm
字号:
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<meta name="GENERATOR" content="Microsoft FrontPage 4.0">
<meta name="ProgId" content="FrontPage.Editor.Document">
<title>第一章 绪论</title>
<meta name="Microsoft Theme" content="hounk 010">
</head>
<body background bgcolor="#000099" text="#CCCC99" link="#FF9900" vlink="#996600" alink="#FF3300">
<!--mstheme--><font face="宋体">
<p align="center"><b><span style="mso-bidi-font-size: 10.0pt; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><span lang="EN-US" style="mso-bidi-font-size: 10.0pt; font-family: Times New Roman; mso-fareast-font-family: 宋体; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA"><font size="6" color="#FFFF00">7.4.2<span style="mso-spacerun: yes; mso-bidi-font-size: 10.0pt; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">
</span></font></span><font size="6" color="#FFFF00"><span style="mso-bidi-font-size: 10.0pt; font-family: 宋体; mso-ascii-font-family: Times New Roman; mso-hansi-font-family: Times New Roman; mso-bidi-font-family: Times New Roman; mso-font-kerning: 1.0pt; mso-ansi-language: EN-US; mso-fareast-language: ZH-CN; mso-bidi-language: AR-SA">最小生成树</span></font></span></b></p>
<p align="left"><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"><b>
使用不同的遍历图的方法，可以得到不同的生成树；从不同的顶点出发，也可能得到不同的生成树。</b></span></font></p>
<p align="left"><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><font color="#FFFFFF" size="5"><span style="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"><b>按照生成树的定义，</b></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"><b>n
</b></span><span style="font-family: 楷体_GB2312; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical"><b>个顶点的连通网络的生成树有</b></span><span style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical"><b>
</b></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"><b>n
</b></span><span style="font-family: 楷体_GB2312; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical"><b>个顶点、</b></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"><b>n</b></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-fareast-language: ZH-CN"><b>-</b></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"><b>1
</b></span><span style="font-family: 楷体_GB2312; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical"><b>条边。</b></span></span></font></p>
<p align="left"><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">MST（Minimum
Cost Spanning Tree）性质:</span></b></font></p>
<p align="left"><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">
假设N=（V，{E}）是一个连通网，U是顶点集V的一个非空子集。若（u,v）是一条具有最小权值（代价）的边，其中u属于U，v属于V-U，则必存在一棵包含边（u,v）的最小生成树。</span></b></font></p>
<p align="left"><font color="#FFFFFF" size="5"><span style="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"><b>构造最小生成树的准则</b></span><span style="mso-special-format: bullet; mso-color-index: 3; position: absolute; left: -3.01%; top: .3em; font-family: Monotype Sorts; text-shadow: auto; layout-flow: vertical">u</span><span style="mso-special-format: bullet; mso-color-index: 3; font-family: Monotype Sorts">：</span></span></font></p>
<ol>
<li>
<p align="left"><font color="#FFFFFF" size="5"><span style="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"><b>必须只使用该网络中的边来构造最小生成树；</b></span></span></font></li>
<li>
<p align="left"><font color="#FFFFFF" size="5"><span style="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"><b>必须使用且仅使用</b></span><span style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical"><b>
</b></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"><b>n</b></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-fareast-language: ZH-CN"><b>-</b></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"><b>1
</b></span><span style="font-family: 楷体_GB2312; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical"><b>条边来联结网络中的</b></span><span style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical"><b>
</b></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"><b>n
</b></span><span style="font-family: 楷体_GB2312; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical"><b>个顶点；</b></span></span></font></li>
<li>
<p align="left" style="margin-bottom: 8"><font color="#FFFFFF" size="5"><span style="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"><b>不能使用产生回路的边。</b></span></span></font></li>
</ol>
<b><!--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="宋体">
<p style="margin-top: 8"><font color="#FFFFFF"><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">克鲁斯卡尔</font><font SIZE="5">
</font><font FACE="Times New Roman" SIZE="5">(Kruskal) </font><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">算法</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 color="#FFFFFF"><font FACE="楷体_GB2312" LANG="ZH-CN" SIZE="5">
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -