Question

数据结构拓扑排序？

如图，是严蔚敏数据结构书上拓扑排序的一段内容，图(a)是偏序关系，而图(b)是全序关系。
我的问题:全序关系的定义是，对于任意a,b属于X,则有xRy,或者yRx。既然v1,v4属于集合X,那么就有v1Rv4，也就是在图(b)中应添加一条从v1指向v4的弧线，为什么没有呢？

Answer 1

不需要有v1到v4的弧线，图b中连v1到v3和v2到v4的弧线都不需要有。关系R是传递的，由v1Rv2、v2Rv3、v3Rv4可推导出v1Rv3、v2Rv4、v1Rv4。

Answer 2

数据结构(data structure)是带有结构特性的数据元素的集合，它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系，并对这种结构定义相适应的运算，设计出相应的算法，并确保经过这些运算以后所得到的新结构仍保持原来的结构类型。简而言之，数据结构是相互之间存在一种或多种特定关系的数据元素的集合，即带“结构”的数据元素的集合。“结构”就是指数据元素之间存在的关系，分为逻辑结构和存储结构。[2]
数据的逻辑结构和物理结构是数据结构的两个密切相关的方面，同一逻辑结构可以对应不同的存储结构。算法的设计取决于数据的逻辑结构，而算法的实现依赖于指定的存储结构。[2]
数据结构的研究内容是构造复杂软件系统的基础，它的核心技术是分解与抽象。通过分解可以划分出数据的3个层次；再通过抽象，舍弃数据元素的具体内容，就得到逻辑结构。类似地，通过分解将处理要求划分成各种功能，再通过抽象舍弃实现细节，就得到运算的定义。上述两个方面的结合可以将问题变换为数据结构。这是一个从具体（即具体问题）到抽象（即数据结构）的过程。