图,这个玩意儿竟然还可以用来排序!

阅读本文大概需要6分钟

之前我写过一篇深度技术文:我敢说,这图绝对跟你想象中的不太一样!在这篇文章里我详细分析了图这种数据结构。

本文是基于图这种数据结构,介绍一个排序算法:拓扑排序。准确的说,应该叫“有向图的拓扑排序”。所谓的有向图,就是 A -> B,但不能 B -> A。与无向图的区别是,它的边在邻接矩阵里只有一项(这些东西,我在上面的文章中都有详细的描述)。

有向图的邻接矩阵如下:

所以针对前面讨论的无向图,邻接矩阵的上下三角是对阵的,有一半信息是冗余的。而有向图的邻接矩阵中所有行列值都包含必要的信息,它的上下三角不是对称的。所以对于有向图,增加边的方法只需要一条语句即可:

如果使用链表,那么 A->B表示A在它的链表中有B,但是B的链表中不包含A,这里就不多说了,本文主要通过邻接矩阵实现。

因为图是有向的,假设A->B->C->D这种,那这就隐藏了一种顺序,即要想到D,必须先过C,必须先过B,必须先过A。它们无形中形成了一种顺序,这种顺序在实际中还是用的挺广泛的,比如,要做web开发,必须先学java基础等等,这些都遵循一个顺序,所以拓扑排序的思想也是这样,利用有向图特定的顺序进行排序。但是拓扑排序的结果不是唯一的,比如A->B的同时,C->B,也就是说A和C都能到B,所以用算法生成一个拓扑排序时,使用的方法和代码的细节决定了会产生那种拓扑排序

拓扑排序的思想虽然不寻常,但是却很简单,有两个必要的步骤:

1.找到一个没有后继的顶点;

2.从图中删除这个顶点,在列表中插入顶点的标记。

然后重复1和2,直到所有顶点都从图中删除,这时候列表显示的顶点顺序就是拓扑排序的结果了。但是文末需要考了一种特殊的有向图:那就是。即A->B->C->D->A。这种必然会导致找不着“没有后继的节点”,这样便无法使用拓扑排序了。

下面我们来分析一下拓扑排序的代码:

主要的工作在while循环中进行,这个循环直到顶点数为0才退出:

1.调用找到任意一个没有后继的顶点;

2.如果找到一个这样的顶点,把顶点放到 sortedArray 数组中,并且从图中删除这个顶点;

3.如果不存在这样的顶点,则图必然存在环。

最后 sortedArray 数组中存储的就是排过序的顶点了。下面我们分析下方法和方法:

从上面代码可以看出,删除一个顶点很简单,从 vertexArray 中删除,后面的顶点向前移动填补空位。同样的,顶点的行列从邻接矩阵中删除,下面的行和右面的列移动来填补空位。删除 adjMat 数组中的边比较简单,下面看看moveRowUp和moveColLeft的方法:

这样便介绍完了拓扑排序的所有过程了。

完整代码:

END

●编号766,输入编号直达本文

●输入m获取文章目录

推荐↓↓↓

人工智能与大数据技术

更多推荐《18个技术类公众微信》

涵盖:程序人生、算法与数据结构、黑客技术与网络安全、大数据技术、前端开发、Java、Python、Web开发、安卓开发、iOS开发、C/C++、.NET、Linux、数据库、运维等。

  • 发表于:
  • 原文链接https://kuaibao.qq.com/s/20181015B0LLJU00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。
  • 如有侵权,请联系 yunjia_community@tencent.com 删除。

扫码关注云+社区

领取腾讯云代金券