成都网站建设设计

将想法与焦点和您一起共享

C#中怎么实现拓扑排序

这篇文章给大家介绍 C#中怎么实现拓扑排序,内容非常详细,感兴趣的小伙伴们可以参考借鉴,希望对大家能有所帮助。

在岐山等地区,都构建了全面的区域性战略布局,加强发展的系统性、市场前瞻性、产品创新能力,以专注、极致的服务理念,为客户提供成都做网站、网站设计、外贸营销网站建设 网站设计制作按需策划,公司网站建设,企业网站建设,品牌网站建设,营销型网站,成都外贸网站制作,岐山网站建设费用合理。

.原理

先来一个基本定义:

在图论中,拓扑排序(Topological Sorting)是一个有向无环图(DAG, Directed Acyclic Graph)的所有顶点的线性序列。且该序列必须满足下面两个条件:

  1. 每个顶点出现且只出现一次。

  2. 若存在一条从顶点 A 到顶点 B 的路径,那么在序列中顶点 A 出现在顶点 B 的前面。

有向无环图(DAG)才有拓扑排序,非DAG图没有拓扑排序一说。

例如,有一个集合它的依赖关系如下图:

C#中怎么实现拓扑排序

可以看到他有一个依赖关系:

  1. Module D 依赖于 Module E 与 Module B 。

  2. Module E 依赖于 Module B 与 Module C 。

  3. Module B 依赖于 Module A 与 Module C 。

  4. Module C 依赖于 Module A 。

  5. Module A 无依赖 。

这个就是一个 DAG 图,我们要得到它的拓扑排序,一个简单的步骤如下:

  1. 从 DAG 图中选择一个没有前驱的顶点并输出。

  2. 从 DAG 图中删除该顶点,以及以它为起点的有向边。

  3. 重复步骤 1、2 直到当前的 DAG 图为空,或者当前图不存在无前驱的顶点为止

按照以上步骤,我们来进行一个排序试试。

C#中怎么实现拓扑排序

最后的排序结果就是:

Module D -> Module E -> Module B -> Module C -> Module A

emmmm,其实一个有向无环图可以有一个或者多个拓扑序列的,因为有的时候会存在一种情况,即以下这种情况:

C#中怎么实现拓扑排序

这个时候你就可能会有这两种结果

D->E->B->C->F->A

D->E->B->F->C->A

因为 F 与 C 是平级的,他们初始化顺序即便不同也没有什么影响,因为他们的依赖层级是一致的,不过细心的朋友可能会发现这个顺序好像是反的,我们还需要将其再反转一次。

3.实现

上面这种方法仅适用于已知入度的时候,也就是说这些内容本身就是存在于一个有向无环图之中的,如果按照以上方法进行拓扑排序,你需要维护一个入度为 0 的队列,然后每次迭代移除入度为 0 顶点所指向的顶点入度。

例如有以下图:

C#中怎么实现拓扑排序

按照我们之前的算法,

  1. 首先初始化队列,将 5 与 4 这两个入度为 0 的顶点加入队列当中。

  2. 执行 While 循环,条件是队列不为空。

  3. 之后首先拿出 4 。

  4. 然后针对其指向的顶点 0 与 顶点 1 的入度减去 1。

  5. 减去指向顶点入度的时候同时判断,被减去入度的顶点其值是否为 0 。

  6. 这里 1 入度被减去 1 ,为 0 ,添加到队列。

  7. 0 顶点入度减去 1 ,为 1。

  8. 队列现在有 5 与 1 这两个顶点,循环判断队列不为空。

  9. 5 指向的顶点 0 入度 减去 1,顶点 0 入度为 0 ,插入队列。

这样反复循环,最终队列全部清空,退出循环,得到拓扑排序的结果4, 5, 2, 0, 3, 1 。

4.深度优先搜索实现

在参考资料 1 的代码当中使用的是深度优先算法,它适用于有向无环图。

有以下有向环图 G2:

C#中怎么实现拓扑排序

对上图 G2 进行深度优先遍历,首先从入度为 0 的顶点 A 开始遍历:

C#中怎么实现拓扑排序

它的步骤如下:

  1. 访问 A 。

  2. 访问 B 。

  3. 访问 C 。

在访问了 B 后应该是访问 B 的另外一个顶点,这里可以是随机的也可以是有序的,具体取决于你存储的序列顺序,这里先访问 C 。

  1. 访问 E 。

  2. 访问 D 。

这里访问 D 是因为 B 已经被访问过了,所以访问顶点 D 。

  1. 访问 F 。

因为顶点 C 已经被访问过,所以应该回溯访问顶点 B 的另一个有向边指向的顶点 F 。

  1. 访问 G 。

因此最后的访问顺序就是 A -> B -> C -> E -> D -> F -> G ,注意顺序还是不太对哦。

看起来跟之前的方法差不多,实现当中,其 Sort() 方法内部包含一个 visited 字典,用于标记已经访问过的顶点,sorted 则是已经排序完成的集合列表。

在字典里 Key 是顶点的值,其 value 值用来标识是否已经访问完所有路径,为 true 则表示正在处理该顶点,为 false 则表示已经处理完成。

现在我们来写实现吧:

C#中怎么实现拓扑排序

C#中怎么实现拓扑排序

结果:

C#中怎么实现拓扑排序

关于 C#中怎么实现拓扑排序就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。


文章题目:C#中怎么实现拓扑排序
文章转载:http://chengdu.cdxwcx.cn/article/ggicip.html