现在的位置: 首页 > 综合 > 正文

什么是拓扑排序,以及计算机一般实现方法

2019年11月07日 ⁄ 综合 ⁄ 共 306字 ⁄ 字号 评论关闭

来自维基百科中文版:

 

图论中,由一个有向无环图的顶点组成的序列,当且仅当满足下列条件时,称为该的一个拓扑排序英语Topological
sorting
)。

  1. 每个顶点出现且只出现一次;
  2. 若A在序列中排在B的前面,则在图中不存在从B到A的路径

也可以定义为:拓扑排序是对有向无环图的顶点的一种排序,它使得如果存在一条从顶点A到顶点B的路径,那么在排序中B出现在A的后面[1]

 

 

来自百度百科:

 

实现的基本方法

拓扑排序方法如下:
(1)从有向图中选择一个没有前驱(即入度为0)的顶点并且输出它.
(2)从网中删去该顶点,并且删去从该顶点发出的全部有向边.
(3)重复上述两步,直到剩余的网中不再存在没有前趋的顶点为止.

 

【上篇】
【下篇】

抱歉!评论已关闭.