📄 ds7.5.1.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="left"><b><font color="#FFFFFF" size="5"><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">7.5.1
拓扑排序</span></font></b></p>
<p align="left"><b><font color="#FFFFFF" size="5"><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></b></p>
<p align="left"><b><font color="#FFFFFF" size="5"><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></b></p>
<p><b><font size="5" color="#FFFF00"><font FACE="楷体_GB2312" LANG="ZH-CN">活动网络</font>
(Activity Network)</font></b></p>
<p><font size="5" color="#FFFFFF"><b><font FACE="楷体_GB2312" LANG="ZH-CN">计划、施工过程、生产流程、程序流程等都是</font>“<font FACE="楷体_GB2312" LANG="ZH-CN">工程</font>”<font FACE="楷体_GB2312" LANG="ZH-CN">。除了很小的工程外，一般都把工程分为若干个叫做</font>“<font FACE="楷体_GB2312" LANG="ZH-CN">活动</font>”<font FACE="楷体_GB2312" LANG="ZH-CN">的子工程。完成了这些活动，这个工程就可以完成了。</font></b></font></p>
<p><font FACE="楷体_GB2312" LANG="ZH-CN" size="5" color="#FFFFFF"><b>例如，计算机专业学生的学习就是一个工程，每一门课程的学习就是整个工程的一些活动。其中有些课程要求先修课程，有些则不要求。这样在有的课程之间有领先关系，有的课程可以并行地学习。</b></font></p>
<p align="center" style="margin-bottom: 0"><img border="0" src="ds7.5.2.gif" width="537" height="377"></p>
<p align="center" style="margin-top: 0"><img border="0" src="ds7.5.4.gif" width="536" height="365"></p>
<p align="left" style="margin-top: 0"><font size="5" color="#FFFFFF"><span style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; 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; 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 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 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">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">,
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; position: relative; top: .37em; mso-text-raise: -25%; mso-fareast-language: ZH-CN">j</span><span style="mso-fareast-language: ZH-CN" lang="EN-US">></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 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">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 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">j<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><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">AOV</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>(Activity<span style="mso-spacerun: yes; mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; text-shadow: auto; layout-flow: vertical">
</span>On Vertices)<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">AOV</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 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">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 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">j
</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 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">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">,
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; position: relative; top: .37em; mso-text-raise: -25%; mso-fareast-language: ZH-CN">j</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-fareast-language: ZH-CN">
AOV</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">AOV</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">因此，对给定的</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">AOV</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></span></font></p>
<p align="left" style="margin-top: 0"><font size="5" color="#FFFFFF"><span style="mso-fareast-font-family: 楷体_GB2312; mso-hansi-font-family: Times New Roman; 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">
检测有向环的一种方法是对</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">AOV</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">代表各个活动</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">AOV</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">AOV</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">AOV</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">AOV</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">AOV</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">AOV</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></span></font><span style="mso-special-format: bullet; color: #CC3300; mso-color-index: 6; position: absolute; left: -3.51%; top: .91em; font-family: Monotype Sorts; font-size: 50%; text-shadow: auto; layout-flow: vertical">n</span></p>
<p align="left" style="margin-top: 0"><b><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">
例如，对学生选课工程图进行拓扑排序，得到的拓扑有序序列为</span><span style="mso-special-format: bullet; mso-color-index: 6; position: absolute; left: -4.16%; top: .91em; font-family: Monotype Sorts; text-shadow: auto; layout-flow: vertical">n</span><span style="mso-special-format: bullet; mso-color-index: 6; font-family: Monotype Sorts">：</span></span></font></b></p>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -