
拓扑排序
1个回答
展开全部
通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。离散数学中关于偏序和全序的定义: 若集合X上的关系是R是自反的、反对称的和传递的,则称R是集合X上的偏序关系。 设R是集合X上的偏序(Partial Order),如果对每个x,y属于X必有xRy 或 yRx,则称R是集合X上的全序关系。 注意: ①若将图中顶点按拓扑次序排成一行,则图中所有的有向边均是从左指向右的。 ②若图中存在有向环,则不可能使顶点满足拓扑次序。 ③一个DAG的拓扑序列通常表示某种方案切实可行。
举例
【例】对学生选课工程图进行拓扑排序, 得到的拓扑有序序列为 C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7 或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6 【例】一本书的作者将书本中的各章节学习作为顶点,各章节的先学后修关系作为边,构成一个有向图。按有向图的拓扑次序安排章节,才能保证读者在学习某章节时,其预备知识已在前面的章节里介绍过。 ④一个DAG可能有多个拓扑序列。 【例】对图G9进行拓扑排序,至少可得到如下的两个(实际远不止两个)拓扑序列:C0,C1,C2,C4,C3,C5,C7,C8,C6和C0,C7,C9,C1,C4,C2,C3,C6,C5。 ⑤当有向图中存在有向环时,拓扑序列不存在 【例】下面(a)图中的有向环重排后如(b)所示,有向边<v3,vl>和其它边反向。若有向图被用来表示某项工程实施方案或某项工作计划,则找不到该图的拓扑序列(即含有向环),就意味着该方案或计划是不可行的。 无前趋的顶点优先的拓扑排序方法 该方法的每一步总是输出当前无前趋(即入度为零)的顶点,其抽象算法可描述为: NonPreFirstTopSort(G){//优先输出无前趋的顶点 while(G中有入度为0的顶点)do{ 从G中选择一个入度为0的顶点v且输出之; 从G中删去v及其所有出边; } if(输出的顶点数目<|V(G)|) //若此条件不成立,则表示所有顶点均已输出,排序成功。 Error("G中存在有向环,排序失败!"); } 对G9执行上述算法的执行过程【参见动画演示】和得到的拓扑序列是C0,C1,C2,C4,C3,C5,C7,C9,C6。 注意: 无前趋的顶点优先的拓扑排序算法在具体存储结构下,为便于考察每个顶点的入度,可保存各顶点当前的入度。为避免每次选入度为0的顶点时扫描整个存储空间,可设一个栈或队列暂存所有入度为零的顶点: 在开始排序前,扫描对应的存储空间,将入度为零的顶点均入栈(队)。以后每次选入度为零的顶点时,只需做出栈(队)操作即可。 拓扑排序是有向图的一个重要操作。在给定的有向图G中,若顶点序列vi1,vi2,...,vin满足下列条件:若在有向图G中从顶点vi到顶点vj有一条路径,则在序列中顶点vi必在顶点vj之前,便称这个序列为一个拓扑序列。求一个有向图拓扑序列的过程称为拓扑排序。
实现的基本方法
拓扑排序方法如下: (1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它. (2)从网中删去该顶点,并且删去从该顶点发出的全部有向边. (3)重复上述两步,直到剩余的网中不再存在没有前驱的顶点为止.
举例
【例】对学生选课工程图进行拓扑排序, 得到的拓扑有序序列为 C1 , C2 , C3 , C4 , C5 , C6 , C8 , C9 , C7 或 C1 , C8 , C9 , C2 , C5 , C3 , C4 , C7 , C6 【例】一本书的作者将书本中的各章节学习作为顶点,各章节的先学后修关系作为边,构成一个有向图。按有向图的拓扑次序安排章节,才能保证读者在学习某章节时,其预备知识已在前面的章节里介绍过。 ④一个DAG可能有多个拓扑序列。 【例】对图G9进行拓扑排序,至少可得到如下的两个(实际远不止两个)拓扑序列:C0,C1,C2,C4,C3,C5,C7,C8,C6和C0,C7,C9,C1,C4,C2,C3,C6,C5。 ⑤当有向图中存在有向环时,拓扑序列不存在 【例】下面(a)图中的有向环重排后如(b)所示,有向边<v3,vl>和其它边反向。若有向图被用来表示某项工程实施方案或某项工作计划,则找不到该图的拓扑序列(即含有向环),就意味着该方案或计划是不可行的。 无前趋的顶点优先的拓扑排序方法 该方法的每一步总是输出当前无前趋(即入度为零)的顶点,其抽象算法可描述为: NonPreFirstTopSort(G){//优先输出无前趋的顶点 while(G中有入度为0的顶点)do{ 从G中选择一个入度为0的顶点v且输出之; 从G中删去v及其所有出边; } if(输出的顶点数目<|V(G)|) //若此条件不成立,则表示所有顶点均已输出,排序成功。 Error("G中存在有向环,排序失败!"); } 对G9执行上述算法的执行过程【参见动画演示】和得到的拓扑序列是C0,C1,C2,C4,C3,C5,C7,C9,C6。 注意: 无前趋的顶点优先的拓扑排序算法在具体存储结构下,为便于考察每个顶点的入度,可保存各顶点当前的入度。为避免每次选入度为0的顶点时扫描整个存储空间,可设一个栈或队列暂存所有入度为零的顶点: 在开始排序前,扫描对应的存储空间,将入度为零的顶点均入栈(队)。以后每次选入度为零的顶点时,只需做出栈(队)操作即可。 拓扑排序是有向图的一个重要操作。在给定的有向图G中,若顶点序列vi1,vi2,...,vin满足下列条件:若在有向图G中从顶点vi到顶点vj有一条路径,则在序列中顶点vi必在顶点vj之前,便称这个序列为一个拓扑序列。求一个有向图拓扑序列的过程称为拓扑排序。
实现的基本方法
拓扑排序方法如下: (1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它. (2)从网中删去该顶点,并且删去从该顶点发出的全部有向边. (3)重复上述两步,直到剩余的网中不再存在没有前驱的顶点为止.

2023-08-15 广告
通常情况下,我们会按照结构模型把系统产生的数据分为三种类型:结构化数据、半结构化数据和非结构化数据。结构化数据,即行数据,是存储在数据库里,可以用二维表结构来逻辑表达实现的数据。最常见的就是数字数据和文本数据,它们可以某种标准格式存在于文件...
点击进入详情页
本回答由光点科技提供
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询