拓扑排序,拓扑排序简单的例子
找百科:专业的百科知识平台 QQ:7384656 |
拓扑排序
网络拓扑(Network Topology)结构是指用传输介质互连各种设备的物理布局。指构成网络的成员间特定的物理的即真实的、或者逻辑的即虚拟的排列方式。如果两个网络的连接结构相同我们就说它们的网络拓扑相同,尽管它们各自内部的物理接线、节点间距离可能会有不同。
拓扑排序简单的例子
目录介绍拓扑排序算法分析拓扑排序代码实现
介绍拓扑排序,很多人都可能听说但是不了解的一种算法。
或许很多人只知道它是图论的一种排序,至于干什么的不清楚。
又或许很多人可能还会认为它是一种啥排序。
而实质上它是对有向图的顶点排成一个线性序列。
至于定义,百科上是这么说的:对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序,是将G中所有顶点排成一个线性序列,使得图中任意一对顶点u和v,若边<u,v>∈E(G),则u在线性序列中出现在v之前。
通常,这样的线性序列称为满足拓扑次序(Topological Order)的序列,简称拓扑序列。
简单的说,由某个集合上的一个偏序得到该集合上的一个全序,这个操作称之为拓扑排序。
学习框架要掌握jsp/servlet和jdbc之类才行。
那么,这个学习过程即构成一个拓扑序列。
规则:图中每个顶点只出现一次。
A在B前面,则不存在B在A前面的路径。
(不能成环!!!!)顶点的顺序是保证所有指向它的下个节点在被指节点前面!(例如A—>B—>C那么A一定在B前面,B一定在C前面)。
所以,这个核心规则下只要满足即可,所以拓扑排序序列不一定唯一!拓扑排序算法分析正常步骤为(方法不一定唯一):从DGA图中找到一个没有前驱的顶点输出。
(可以遍历,也可以用优先队列维护)删除以这个点为起点的边。
(它的指向的边删除,为了找到下个没有前驱的顶点)重复上述,直到最后一个顶点被输出。
如果还有顶点未被输出,则说明有环!对于上图的简单序列,可以简单描述步骤为:1:删除1或2输出2:删除2或3以及对应边3:删除3或者4以及对应边3:重复以上规则步骤这样就完成一次拓扑排序,得到一个拓扑序列,但是这个序列并不唯一!从过程中也看到有很多选择方案,具体得到结果看你算法的设计了。
但只要满足即是拓扑排序序列。
另外观察 1 2 4 3 6 5 7 9这个序列满足我们所说的有关系的节点指向的在前面,被指向的在后面。
如果完全没关系那不一定前后(例如1,2)拓扑排序代码实现对于拓扑排序,如何用代码实现呢?对于拓扑排序,虽然在上面详细介绍了思路和流程,也很通俗易懂。
但是实际上代码的实现还是很需要斟酌的,如何在空间和时间上能够得到较好的平衡且取得较好的效率?首先要考虑存储。
对于节点,首先他有联通点这么多属性。
遇到稀疏矩阵还是用邻接表比较好。
因为一个节点的指向节点较少,用邻接矩阵较浪费资源。
另外,如果是1,2,3,4,5,6这样的序列求拓扑排序,我们可以考虑用数组,但是如果遇到1,2,88,9999类似数据,可以考虑用map中转一下。
那么,我们具体的代码思想为:新建node类,包含节点数值和它的指向(这里直接用list集合替代链表了)一个数组包含node(这里默认编号较集中)。
初始化,添加每个节点指向的时候同时被指的节点入度+1!(A—>C)那么C的入度+1;扫描一遍所有node。
将所有入度为0的点加入一个栈(队列)。
当栈(队列)不空的时候,抛出其中任意一个node(栈就是尾,队就是头,顺序无所谓,上面分析了只要同时入度为零可以随便选择顺序)。
将node输出,并且node指向的所有元素入度减一。
如果某个点的入度被减为0,那么就将它加入栈(队列)。
重复上述操作,直到栈为空。
这里主要是利用栈或者队列储存入度只为0的节点,只需要初次扫描表将入度为0的放入栈(队列)中。
这里你或许会问为什么。
因为节点之间是有相关性的,一个节点若想入度为零,那么它的父节点(指向节点)肯定在它为0前入度为0,拆除关联箭头。
找百科:专业的百科知识平台 QQ:7384656 |
版权声明
本文仅代表作者观点,不代表找百科立场。
本文系作者授权找百科发表,未经许可,不得转载。