拓扑排序
文章目录
背景
用【有向图】表示一个【工程的施工图】或【程序的数据流图】，则图中不允许出现回路
例子：
【回路】 打地基->做房子结构->砌墙->装修->打地基
【解释】 “做房子结构“的前提是“打地基”，“砌墙”的前提是“做房子结构”，“装修”的前提是“砌墙”，“打地基”的前提是“装修”
【说明】 到底是哪一个先开始，有回路就没法做了
AOV网
【AOV网】在这种情况下的有向图即为AOV网
【定义】Activity On Vertex Network，活动在顶点上的网，用顶点代表某个活动，用顶点之间的边代表活动之间的关系
【特点】
- AOV网描述了一种有实际意义的点，这种有实际意义的点自然有先后顺序，即可以看成有向图
- 这种网中是不能有环的
- 可以导出很多种执行序列
- 生产次序1：原材料->部件1->部件2->部件3->成品
- 生产次序2：原材料->部件3->部件2->部件1->成品
- 生产次序3：原材料->部件1->部件2->成品->部件3（×，部件3没有生产，成品不能先生产）
如何导出正确的执行序列呢？进行拓扑排序，拓扑排序序列即为正确的执行序列
拓扑排序
如何检查【有向图】中是否存在【回路】的方法之一：对【有向图】进行【拓扑排序】
拓扑排序是什么
按照【有向图】给出的【次序关系】，将图中【顶点】排成一个【线性序列】，对于【有向图】中没有限定次序关系的顶点，则可以人为加上任意的次序关系
这样得到的【线性序列】称为【拓扑有序序列】
【拓扑排序】的目标呢：就是构造一个【拓扑有序序列】
如何进行拓扑排序
- 从【有向图】中选取一个没有前驱的顶点，并输出=>选【入度为0的顶点】
- 从有向图中删去【此顶点】以及所有【以它为尾的弧】=>弧头顶点的入度减1
- 重复以上两步，直至【图空】，或者【图不空但找不到无前驱的顶点】为止
举例
例一
| 步骤数 | 入度为0的有 | 选择顶点 并删除顶点与弧 |
输出 |
|---|---|---|---|
| 1 | A,B,C | A | “A” |
| 2 | B,C | B | “AB” |
| 3 | D,C | D | “ABD” |
| 4 | F,G,C | F | “ABDF” |
| 5 | G,C | G | “ABDFG” |
| 6 | C | C | “ABDFGC” |
| 7 | E | E | “ABDFGCE” |
| 8 | H | H | “ABDFGCEH” |
| 9 | I | I | “ABDFGCEHI” |
图空，没有回路，"ABDFGCEHI"为【拓扑有序序列】
例二
| 步骤数 | 入度为0的有 | 选择顶点 并删除顶点与弧 |
输出 |
|---|---|---|---|
| 1 | A,C | A | “A” |
| 2 | C | C | “AC” |
找不到入度为0的顶点=>退出=>图还没有空图=>有回路
定量分析
思路
取入度为0的顶点v;
while (v<>0) {
printf(v); ++m;
// 所有入度减1
w:=FirstAdj(v);
while (w<>0) {
inDegree[w]--;
w:=nextAdj(v,w);
}
取下一个入度为0的顶点v
}
if m<n printf("图中有回路")
优化
为避免每次都要搜索【入度为0的顶点】
在算法中设置一个“栈”，以保存“入度为0”的顶点
CountInDegree(G, indegree); //对各个顶点求入度
InitStack(S);
for (i=0; i<G.vexnum; ++i) {
if (!indegree[i]) Push(S,i); //入度为0的顶点入栈
}
count = 0; //对输出顶点计数
while (!emptyStack(S)) {
Pop(S,v); ++count; printf(v);
for (w=FirstAdj(v); w; w=NextAdj(G,v,w)) {
--indegree(w);
}
//新产生的入度为零的顶点入栈
if (!indegree[w]) Push(S,w);
}
if (count<G.vexnum) printf("图中有回路")
相关阅读
前言计算机网络基础 该是程序猿需掌握的知识，但往往会被忽略今天，我将献上一份详细 & 清晰的计算机网络基础 学习指南，涵盖 TCP / UD
优化安卓APP网络流量 套餐虽然优惠，流量还是很贵，对用户而言网络流量就是钱呐！用户习惯打开系统自带 APP 流量统计功能（如下），从 APP 的
利用MATLAB 2016a进行BP神经网络的预测（含有神经网络工
利用MATLAB 2016a进行BP神经网络的预测（含有神经网络工具箱） 最近一段时间在研究如何利用预测其销量个数，在网上搜索了一下，发现
微软office 2007中文安装版（附office2007序列号）
http://www.xiazaizhijia.com/soft/59442.html office2007是微软Office产品史上最具创新与革命性的一个版本，全新设计的用户界面
e1000网络驱动分析e1000是intel千兆以太网卡的驱动源码。官方关于驱动的使用可以参考如下链接。https://www.intel.cn/content/ww