Java实现拓扑排序的示例代码（拓扑排序c语言代码）

目录铺垫简介工作过程数据结构拓扑排序测试样例1测试样例2总结

铺垫

有向图：我们这节要讲的算法涉及到有向图，所以我先把有向图的一http://些概念说一下，文章后面就不做解释啦。首先有向图节点与节点之间是用带箭头的线连接起来的。节点有出度和入度的概念，连线尾部指向的节点出度加1，连线头部，也就是箭头指向的节点入度加1。看下面这个例子，A的入度为0，出度为2，B的入度为1，出度为1，C的入度为1，出度为1，D的入度为2，出度为0。

邻接表：邻接表是存储图结构的一种有效方式，如下图所示，左边节点数组存储图中所有节点，右侧邻接表存储节点的相邻节点。

简介

这篇文章我们要讲的是拓扑排序，这是一个针对有向无环图的算法，主要是为了解决前驱后继的关系，即我们在完成当前事项的时候需要先完成什么事项，其实这在我们流程控制里面用的挺多的。看下面这个图，我们需要先完成A事项，然后才能去完成B，C事项，B，C事项的属于并列的，没有先后顺序，但是对于D事项需要在B，C事项完成之后才能进行。而拓扑排序能够帮助我们找到这个完成事项的合LMvENYZuF理顺序，同时我们看上面这个例子，A事项完成之后，B，C事项是没有先后顺序的，不管是先完成B还是C都符合条件，所以拓扑排序的顺序序列不是完全一定的。

工作过程

首先拓扑排序对应操作的是一个有向无环图。无环图，则肯定存在至少一个结点入度为0。在当前情况下，我们需要查找入度为0的节点进行操作，入度为0，表示当前节点没有前驱节点，或者前驱节点已经处理，可以直接操作。操作完毕之后，将当前节点的后继节点入度全部减1，再次查找入度节点为0的节点进行操作，此后就是一个递归过程，不断处理当前情况下入度为0的节点，直至所有节点处理完毕。

数据结构

有向图结构如下，其中node存储当前图中包含的所有节点，adj存储对应下标节点的邻接点。初始化图时候，我们需要初始化图中节点个数，存储节点的数组以及节点对应邻接数组。同时提供一个addEdge方法，用于在两个节点直接加边，其实就是将后继节点放入前驱节点的邻接表中。

publicstaticclassGraph{

/**

* 节点个数

*/

privateIntegernodeSize;

/**

* 节点

*/

privatechar[]node;

/**

* 邻接表

*/

privateLinkedList[]adj;

publicGraph(char[]node) {

this.nodeSize=node.length;

this.node=node;

this.adj=newLinkedList[nodeSize];

for(inti=0;i

adj[i]=newLinkedList();

}

}

/**

* 在节点之间加边，前驱节点指向后继节点

* @paraLMvENYZuFm front 前驱节点所在下标

* @param end 后继节点所在下标

*/

publicvoidaddEdge(intfront,intend) {

adj[front].add(end);

}

}

拓扑排序

拓扑排序首先初始化了两个临时数组，一个队列，一个inDegree数组存储对应下标节点的入度，因为每次访问的节点需要前驱节点已经完成，即入度为0，有了这个数组我们就可以比较快速的找到这些节点；另一个是visited数组，标志当前节点是否已经访问过，防止多次访问；一个nodes队列则保存在目前情况下所有入度为0的节点。（注意，为了存取方便，我们都是存储的节点下标 step1:初始化inDegree数组，visited数组； step2:遍历inDegree数组，将所有入度为0的节点入nodes队列； step3:依次将节点node出队； 根据visited判断当前node是否已经被访问，是，返回step3，否，进行下一步； 将当前节点的邻接节点入度-1，判断邻接节点入度是否为0，为0直接放入nodes队列，不为0返回step3；

/**

* @param graph 有向无环图

* @return 拓扑排序结果

*/

publicListtoPoLogicalSort(Graphgraph) {

//用一个数组标志所有节点入度

int[]inDegree=newint[graph.nodeSize];

for(LinkedListlist:graph.adj) {

for(Objectindex:list) {

++inDegree[(int)index];

}

}

//用一个数组标志所有节点是否已经被访问

boolean[]visited=newboolean[graph.nodeSize];

//开始进行遍历

Dequenodes=newLinkedList<>();

//将入度为0节点入队

for(inti=0;i

if(inDegree[i]==0) {

nodes.offer(i);

}

}

Listresult=newArrayList<>();

//将入度为0节点一次出队处理

while(!nodes.isEmpty()) {

intnode=nodes.poll();

if(visited[node]) {

continue;

}

visited[node]=true;

result.add(graph.node[node]);

//将当前node的邻接节点入度-1；

for(Objectlist:graph.adj[node]) {

--inDegree[(int)list];

if(inDegree[(int)list]==0) {

//前驱节点全部访问完毕，入度为0

nodes.offer((int)list);

}

}

}

returnresult;

}

测试样例1

publicstaticvoidmain(String[]args) {

ToPoLogicalSorttoPoLogicalSort=newToPoLogicalSort();

//初始化一个图

Graphgraph=newGraph(newchar[]{'A','B','C','D'});

graph.addEdge(0,1);

graph.addEdge(0,2);

graph.addEdge(1,3);

graph.addEdge(2,3);

Listresult=toPoLogicalSort.toPoLogicalSort(graph);

}

执行结果

测试样例2

publicstaticvoidmain(String[]args) {

ToPoLogicalSorttoPoLogicalSort=newToPoLogicalSort();

//初始化一个图

Graphgraph=newGraph(newchar[]{'A','B','C','D','E','F','G','H'});

graph.addEdge(0,1);

graph.addEdge(0,2);

graph.addEdge(0,3);

graph.addEdge(1,4);

graph.addEdge(2,4);

graph.addEdge(3,4);

graph.addEdge(4,7);

graph.addEdge(4,6);

graph.addEdge(7,5);

graph.addEdge(6,7);

Listresult=toPoLogicalSort.toPoLogicalSort(graph);

}

执行结果

总结

我在上面有说到，拓扑排序可以用来判断图是否存在环，其实判断方式很简单，实现步骤与上面一致，只是我们最后判断一下出队的元素个数是否等于图的节点个数，如果等于，证明图无环，如果不等于则证明存在环。

adj[i]=newLinkedList();

}

}

/**

* 在节点之间加边，前驱节点指向后继节点

* @paraLMvENYZuFm front 前驱节点所在下标

* @param end 后继节点所在下标

*/

publicvoidaddEdge(intfront,intend) {

adj[front].add(end);

}

}

拓扑排序

拓扑排序首先初始化了两个临时数组，一个队列，一个inDegree数组存储对应下标节点的入度，因为每次访问的节点需要前驱节点已经完成，即入度为0，有了这个数组我们就可以比较快速的找到这些节点；另一个是visited数组，标志当前节点是否已经访问过，防止多次访问；一个nodes队列则保存在目前情况下所有入度为0的节点。（注意，为了存取方便，我们都是存储的节点下标 step1:初始化inDegree数组，visited数组； step2:遍历inDegree数组，将所有入度为0的节点入nodes队列； step3:依次将节点node出队； 根据visited判断当前node是否已经被访问，是，返回step3，否，进行下一步； 将当前节点的邻接节点入度-1，判断邻接节点入度是否为0，为0直接放入nodes队列，不为0返回step3；

/**

* @param graph 有向无环图

* @return 拓扑排序结果

*/

publicListtoPoLogicalSort(Graphgraph) {

//用一个数组标志所有节点入度

int[]inDegree=newint[graph.nodeSize];

for(LinkedListlist:graph.adj) {

for(Objectindex:list) {

++inDegree[(int)index];

}

}

//用一个数组标志所有节点是否已经被访问

boolean[]visited=newboolean[graph.nodeSize];

//开始进行遍历

Dequenodes=newLinkedList<>();

//将入度为0节点入队

for(inti=0;i

if(inDegree[i]==0) {

nodes.offer(i);

}

}

Listresult=newArrayList<>();

//将入度为0节点一次出队处理

while(!nodes.isEmpty()) {

intnode=nodes.poll();

if(visited[node]) {

continue;

}

visited[node]=true;

result.add(graph.node[node]);

//将当前node的邻接节点入度-1；

for(Objectlist:graph.adj[node]) {

--inDegree[(int)list];

if(inDegree[(int)list]==0) {

//前驱节点全部访问完毕，入度为0

nodes.offer((int)list);

}

}

}

returnresult;

}

测试样例1

publicstaticvoidmain(String[]args) {

ToPoLogicalSorttoPoLogicalSort=newToPoLogicalSort();

//初始化一个图

Graphgraph=newGraph(newchar[]{'A','B','C','D'});

graph.addEdge(0,1);

graph.addEdge(0,2);

graph.addEdge(1,3);

graph.addEdge(2,3);

Listresult=toPoLogicalSort.toPoLogicalSort(graph);

}

执行结果

测试样例2

publicstaticvoidmain(String[]args) {

ToPoLogicalSorttoPoLogicalSort=newToPoLogicalSort();

//初始化一个图

Graphgraph=newGraph(newchar[]{'A','B','C','D','E','F','G','H'});

graph.addEdge(0,1);

graph.addEdge(0,2);

graph.addEdge(0,3);

graph.addEdge(1,4);

graph.addEdge(2,4);

graph.addEdge(3,4);

graph.addEdge(4,7);

graph.addEdge(4,6);

graph.addEdge(7,5);

graph.addEdge(6,7);

Listresult=toPoLogicalSort.toPoLogicalSort(graph);

}

执行结果

总结

我在上面有说到，拓扑排序可以用来判断图是否存在环，其实判断方式很简单，实现步骤与上面一致，只是我们最后判断一下出队的元素个数是否等于图的节点个数，如果等于，证明图无环，如果不等于则证明存在环。

if(inDegree[i]==0) {

nodes.offer(i);

}

}

Listresult=newArrayList<>();

//将入度为0节点一次出队处理

while(!nodes.isEmpty()) {

intnode=nodes.poll();

if(visited[node]) {

continue;

}

visited[node]=true;

result.add(graph.node[node]);

//将当前node的邻接节点入度-1；

for(Objectlist:graph.adj[node]) {

--inDegree[(int)list];

if(inDegree[(int)list]==0) {

//前驱节点全部访问完毕，入度为0

nodes.offer((int)list);

}

}

}

returnresult;

}

测试样例1

publicstaticvoidmain(String[]args) {

ToPoLogicalSorttoPoLogicalSort=newToPoLogicalSort();

//初始化一个图

Graphgraph=newGraph(newchar[]{'A','B','C','D'});

graph.addEdge(0,1);

graph.addEdge(0,2);

graph.addEdge(1,3);

graph.addEdge(2,3);

Listresult=toPoLogicalSort.toPoLogicalSort(graph);

}

执行结果

测试样例2

publicstaticvoidmain(String[]args) {

ToPoLogicalSorttoPoLogicalSort=newToPoLogicalSort();

//初始化一个图

Graphgraph=newGraph(newchar[]{'A','B','C','D','E','F','G','H'});

graph.addEdge(0,1);

graph.addEdge(0,2);

graph.addEdge(0,3);

graph.addEdge(1,4);

graph.addEdge(2,4);

graph.addEdge(3,4);

graph.addEdge(4,7);

graph.addEdge(4,6);

graph.addEdge(7,5);

graph.addEdge(6,7);

Listresult=toPoLogicalSort.toPoLogicalSort(graph);

}

执行结果

总结

我在上面有说到，拓扑排序可以用来判断图是否存在环，其实判断方式很简单，实现步骤与上面一致，只是我们最后判断一下出队的元素个数是否等于图的节点个数，如果等于，证明图无环，如果不等于则证明存在环。

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