详解Java实现拓扑排序算法

详解Java实现拓扑排序算法

目录一、介绍二、拓扑排序算法分析三、拓扑排序代码实现

一、介绍

百科上这么定义的：

对一个有向无环图(Directed Acyclic Graph简称DAG)G进行拓扑排序，是将G中所有顶点排成一个线性序列，使得图中任意一对顶点u和v，若边∈E(G)，则u在线性序列中出现在v之前。通常，这样的线性序列称为满足拓扑次序(Topological Order)的序列，简称拓扑序列。简单的说，由某个集合上的一个偏序得到该集合上的一个全序，这个操作称之为拓扑排序。

为什么会有拓扑排序？拓扑排序有何作用？

举个例子，学习java系列wtzkoMIa的教程

代号

科目

学前需掌握

A1

javaSE

A2

html

A3

jsp

A1，A2

A4

servlet

A1

A5

ssm

A3,A4

A6

springboot

A5

就比如学习java系类(部分)从java基础，到jsp/servlet，到ssm，到springboot，springcloud等是个循序渐进且有依赖的过程。在jsp学习要首先掌握java基础和html基础。学习框架要掌握jsp/servlet和jdbc之类才行。那么，这个学习过程即构成一个拓扑序列。当然这个序列也不唯一，你可以对不关联的学科随意选择顺序(比如html和java可以随便先开始哪一个。)

那上述序列可以简单表示为：

其中五种均为可以选择的学习方案，对课程安排可以有参考作用，当然，五个都是拓扑序列。只是选择的策略不同！

一些其他注意：

DGA：有向无环图

AOV网：数据在顶点 可以理解为面向对象

AOE网：数据在边上，可以理解为面向过程！

而我们通俗一点的说法，就是按照某种规则将这个图的顶点取出来，这些顶点能够表示什么或者有什么联系。

规则：

图中每个顶点只出现一次。

A在B前面，则不存在B在A前面的路径。(不能成环！！！！)

顶点的顺序是保证所有指向它的下个节点在被指节点前面！(例如A—>B—>C那么A一定在B前面，B一定在C前面)。所以，这个核心规则下只要满足即可，所以拓扑排序序列不一定唯一！

二、拓扑排序算法分析

正常步骤为(方法不一定唯一)：

从DGA图中找到一个没有前驱的顶点输出。(可以遍历，也可以用优先队列维护)

删除以这个点为起点的边。(它的指向的边删除，为了找到下个没有前驱的顶点)

重复上述，直到最后一个顶点被输出。如果还有顶点未被输出，则说明有环！

对于上图的简单序列，可以简单描述步骤为：

1：删除1或2输出

2：删除2或3以及对应边

3：删除3或者4以及对应边

4：重复以上规则步骤

这样就完成一次拓扑排序，得到一个拓扑序列，但是这个序列并不唯一！从过程中也看到有很多选择方案，具体得到结果看你算法的设计了。但只要满足即是拓扑排序序列。

另外观察 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，拆除关联箭头。从父节点角度，它的这次拆除联系，可能导致被指向的入读为0，也可能不为0(还有其他节点指向儿子)

至于具体demo：

package 图论;

import java.util.ArrayDeque;

import java.util.ArrayList;

import java.util.List;

import java.util.Queue;

import java.util.Stack;

public class tuopu {

static class node

{

int value;

List next;

public node(int value) {

this.value=value;

next=new ArrayList();

}

public void setnext(Listlist) {

this.next=list;

}

}

public static void main(String[] args) {

// TODO Auto-generated method stub

node []nodes=new node[9];//储存节点

int a[]=new int[9];//储存入度

Listlist[]=new ArrayList[10];//临时空间，为了存储指向的集合

for(int i=1;i<9;i++)

{

nodes[i]=new node(i);

list[i]=new ArrayList();

}

initmap(nodes,list,a);

//主要流程

//Queueq1=new ArrayDeque();

Stacks1=new Stack();

for(int i=1;i<9;i++)

{

//System.out.print(nodes[i].next.size()+" 55 ");

//System.out.println(a[i]);

if(a[i]==0) {s1.add(nodes[i]);}

}

while(!s1.isEmpty())

{

node n1=s1.pop();//抛出输出

System.out.print(n1.value+" ");

Listnext=n1.next;

for(int i=0;i

{

a[next.get(i)]--;//入度减一

if(a[next.get(i)]==0)//如果入度为0

{

s1.add(nodes[next.get(i)]);

}

}

}

}

private static void initmap(node[] nodes, List[] list, int[] a) {

list[1].add(3);

nodes[1].setnext(list[1]);

a[3]++;

list[2].add(4);list[2].add(6);

nodes[2].setnext(list[2]);

a[4]++;a[6]++;

list[3].add(5);

nodes[3].setnext(list[3]);

a[5]++;

list[4].add(5);list[4].add(6);

nodes[4].setnext(list[4]);

a[5]++;a[6]++;

list[5].add(7);

nodes[5].setnext(list[5]);

a[7]++;

list[6].add(8);

nodes[6].setnext(list[6]);

a[8]++;

list[7].add(8);

nodes[7].setnext(list[7]);

a[8]++;

}

}

输出结果

2 4 6 1 3 5 7 8

当然，上面说过用栈和队列都可以！如果使用队列就会得到1 2 3 4 5 6 7 8 的拓扑序列

以上就是详解Java实现拓扑排序算法的详细内容，更多关于Java实现拓扑排序算法的资料请关注我们其它相关文章！

{

a[next.get(i)]--;//入度减一

if(a[next.get(i)]==0)//如果入度为0

{

s1.add(nodes[next.get(i)]);

}

}

}

}

private static void initmap(node[] nodes, List[] list, int[] a) {

list[1].add(3);

nodes[1].setnext(list[1]);

a[3]++;

list[2].add(4);list[2].add(6);

nodes[2].setnext(list[2]);

a[4]++;a[6]++;

list[3].add(5);

nodes[3].setnext(list[3]);

a[5]++;

list[4].add(5);list[4].add(6);

nodes[4].setnext(list[4]);

a[5]++;a[6]++;

list[5].add(7);

nodes[5].setnext(list[5]);

a[7]++;

list[6].add(8);

nodes[6].setnext(list[6]);

a[8]++;

list[7].add(8);

nodes[7].setnext(list[7]);

a[8]++;

}

}

输出结果

2 4 6 1 3 5 7 8

当然，上面说过用栈和队列都可以！如果使用队列就会得到1 2 3 4 5 6 7 8 的拓扑序列

以上就是详解Java实现拓扑排序算法的详细内容，更多关于Java实现拓扑排序算法的资料请关注我们其它相关文章！

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。