2019计算机考研知识点：图的应用之拓扑排序
时间：2018-01-10 来源：文都网校 浏览：2019考研备考已经开始了，为帮助大家快速进入备考状态，文都网校考研频道小编特意帮大家整理了计算机考研的知识点：图的应用之拓扑排序，希望对计算机考研的考生们有所帮助!
图是数据结构科目中难度最大的重点章节，在这两年的考试中也作为重点来考查。图这部分内容概念多、算法多、难度大。这就需要大家深刻理解每个知识点，多做练习，抓住规律，才能很好地解答这部分试题。图这部分要求大家掌握图的定义、特点、存储结构、遍历、图的基本应用等内容。图这部分的重点和难点是图的基本应用，这在09年和10年的考试中有所体现。图的基本应用包括：最小生成树、最短路径、拓扑排序、关键路径等。09年考试中重点考查了最短路径的判断与证明。建议大家把图的基本应用作为重点来复习。
下面介绍一下图的基本应用：
三、 拓扑排序
1.拓扑排序基本概念
AOV网是一种可以形象地反映出整个工程中各个活动之间前后关系的有向图。在AOV网中，若不存在回路，则所有活动可排成一个线性序列，使得每个活动的所有前驱活动都排在该活动的前面，那么该序列为拓扑序列。
2.拓扑排序特点：
(1)拓扑序列不是唯一的。
(2)AOV网不一定都有拓扑序列。在AOV网中如果出现了有向环，则意味着某项活动应以自己作为先决条件，这是不对的，工程将无法进行。
大家要注意拓扑排序的应用，例如：利用拓扑排序判断一个图中是否存在回路。
文都网校考研频道为大家持续更新考研资料，希望能帮助到大家，同学们可以关注文都考研，这里有你需要的资料，点击【kaoyan.wenduedu.com】风里、雨里，文都陪伴着你！有问题找文都☞☞☞详情咨询入口>>>
资讯推荐：
课程推荐：
|
1月主推课程 |
|
| 2018考研*定向复试特训班 | |
| 2019考研高端辅导英才成功卡 | |
| 2019考研专硕199管综VIP特训班 | |
| 2019考研VIP特训班【政治 英语二】 | |
| 2019考研专硕会计硕士全科VIP特训班 | |
- 2018考研 计算机考研知识点 图的应用
- 责任编辑：lq
