ds7.5.1.htm

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

最后得到的拓扑有序序列为 <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">C</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; position: relative; top: .37em; mso-text-raise: -25%; mso-fareast-language: ZH-CN">4</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 style="mso-spacerun: yes; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical">&nbsp;</span>, 
C</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; 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-color-index: 3; mso-fareast-language: ZH-CN"><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>, 
C</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; position: relative; top: .37em; mso-text-raise: -25%; mso-fareast-language: ZH-CN">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"><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>, 
C</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; position: relative; top: .37em; mso-text-raise: -25%; mso-fareast-language: ZH-CN">2</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 style="mso-spacerun: yes; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical">&nbsp;</span>, 
C</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; position: relative; top: .37em; mso-text-raise: -25%; 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-color-index: 3; mso-fareast-language: ZH-CN">, 
C</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; position: relative; top: .37em; mso-text-raise: -25%; mso-fareast-language: ZH-CN">5</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><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">C</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">4</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">C</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">2</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></b></font></p>
<p align="left"><b><span style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical"><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"><font size="5" color="#FFFF00">AOV</font></span><font size="5" color="#FFFF00"><span style="font-family: 楷体_GB2312; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical">网络及其邻接表表示（其中count记录顶点的入度）</span></font></span></b></p>
<p align="left"><img border="0" src="ds7.5.7.gif" width="1047" height="356"></p>
<p align="left"><font size="5" color="#FFFFFF"><span style="text-shadow: auto; layout-flow: vertical"><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></b><span style="mso-special-format: bullet; mso-color-index: 6; position: absolute; left: -3.7%; top: .91em; font-family: Monotype Sorts; text-shadow: auto; layout-flow: vertical">n</span></span></font></p>
<p align="left">&nbsp; <font size="5" color="#FFFFFF"><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><span style="mso-spacerun: yes; text-shadow: auto; layout-flow: vertical"> 
</span></b></span></span></font></p>
<p align="left"><font size="5" color="#FFFFFF"><b><span style="mso-spacerun: yes; text-shadow: auto; layout-flow: vertical; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman">&nbsp;</span></b><span style="text-shadow: auto; layout-flow: vertical"><span style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical"><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></font></p>
<p align="left"><font size="5" color="#FFFFFF"><b><span style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical">&nbsp;</span></b><span style="text-shadow: auto; layout-flow: vertical"><span style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical"><b>(2) 
</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 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" style="margin-top: 0; margin-bottom: 0"><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;&nbsp; 
1.</span></b><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 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>;<span style="mso-spacerun: yes; text-shadow: auto; layout-flow: vertical"></span></b></span></span></font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><b><span style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical">&nbsp;&nbsp; 
2.</span></b><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>AOV</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 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></font></p>
<p align="left" style="margin-top: 0; margin-bottom: 0"><font size="5" color="#FFFFFF"><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>&nbsp;&nbsp;&nbsp;&nbsp; 
3.如果边的终顶点入度减至</b></span><span style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical"><b>0, 
</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 style="mso-special-format: bullet; mso-color-index: 6; position: absolute; left: -3.58%; top: .91em; font-family: Monotype Sorts; text-shadow: auto; layout-flow: vertical">n</span></span></font></p>
<p align="left">&nbsp; <font size="5" color="#FFFFFF"><span style="text-shadow: auto; layout-flow: vertical"><span style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical"><b>(3) 
</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>AOV</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 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="center">　</p>
<p align="center"><b><a href="ds7.5.htm"><font size="5" color="#FFFF00">返回</font></a></b></p>
<!--mstheme--></font>

</body>

</html>