铺垫我们本节将介绍与有向图相关的算法，因此先对有向图的一些概念进行解释；之后的文章将不再对这些概念做具体解释。首先有向图节点与节点之间是用带箭头的线连接起来的。节点的出度和入度可用来描述，当一条连线的尾部指向该节点时，其出度会增加1；而当一条连线的箭头指向该节点时，其入度会增加1。看下面这个例子，a的入度为0，出度为2，b的入度为1，出度为1，c的入度为1，出度为1，d的入度为2，出度为0。
邻接表：邻接表是存储图结构的一种有效方式，如下图所示，左边节点数组存储图中所有节点，右侧邻接表存储节点的相邻节点。
简介这篇文章我们要讲的是拓扑排序，这是一个针对有向无环图的算法，主要是为了解决前驱后继的关系，即我们在完成当前事项的时候需要先完成什么事项，其实这在我们流程控制里面用的挺多的。看下面这个图，我们需要先完成a事项，然后才能去完成b，c事项，b，c事项的属于并列的，没有先后顺序，但是对于d事项需要在b，c事项完成之后才能进行。而拓扑排序能够帮助我们找到这个完成事项的合理顺序，同时我们看上面这个例子，a事项完成之后，b，c事项是没有先后顺序的，不管是先完成b还是c都符合条件，所以拓扑排序的顺序序列不是完全一定的。
工作过程首先拓扑排序对应操作的是一个有向无环图。无环图，则肯定存在至少一个结点入度为0。在当前情况下，我们需要查找入度为0的节点进行操作，入度为0，表示当前节点没有前驱节点，或者前驱节点已经处理，可以直接操作。操作完毕之后，将当前节点的后继节点入度全部减1，再次查找入度节点为0的节点进行操作，此后就是一个递归过程，不断处理当前情况下入度为0的节点，直至所有节点处理完毕。
数据结构以下是有向图的结构，其中node存储着当前图中的所有节点，adj则存储着对应下标节点的邻接点。在初始化图时，需指定节点数量、建立节点数组和邻接数组。提供一个名为addedge的方法，用于将两个节点之间建立一条边，即将后继节点添加到前驱节点的邻接表中。
public static class graph{ /** * 节点个数 */ private integer nodesize; /** * 节点 */ private char[] node; /** * 邻接表 */ private linkedlist[] adj; public graph(char[] node) { this.nodesize = node.length; this.node = node; this.adj = new linkedlist[nodesize]; for (int i = 0 ; i < adj.length ; i++) { adj[i] = new linkedlist(); } } /** * 在节点之间加边，前驱节点指向后继节点 * @param front 前驱节点所在下标 * @param end 后继节点所在下标 */ public void addedge(int front, int end) { 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 拓扑排序结果 */ public list<character> topologicalsort(graph graph) { //用一个数组标志所有节点入度 int[] indegree = new int[graph.nodesize]; for (linkedlist list : graph.adj) { for (object index : list) { ++ indegree[(int)index]; } } //用一个数组标志所有节点是否已经被访问 boolean[] visited = new boolean[graph.nodesize]; //开始进行遍历 deque<integer> nodes = new linkedlist<>(); //将入度为0节点入队 for (int i = 0 ; i < graph.nodesize; i++) { if (indegree[i] == 0) { nodes.offer(i); } } list<character> result = new arraylist<>(); //将入度为0节点一次出队处理 while (!nodes.isempty()) { int node = nodes.poll(); if (visited[node]) { continue; } visited[node] = true; result.add(graph.node[node]); //将当前node的邻接节点入度-1； for (object list : graph.adj[node]) { -- indegree[(int)list]; if (indegree[(int)list] == 0) { //前驱节点全部访问完毕，入度为0 nodes.offer((int) list); } } } return result; }
测试样例1public static void main(string[] args) { topologicalsort topologicalsort = new topologicalsort(); //初始化一个图 graph graph = new graph(new char[]{'a', 'b', 'c', 'd'}); graph.addedge(0, 1); graph.addedge(0,2); graph.addedge(1,3); graph.addedge(2,3); list<character> result = topologicalsort.topologicalsort(graph); }
执行结果
测试样例2public static void main(string[] args) { topologicalsort topologicalsort = new topologicalsort(); //初始化一个图 graph graph = new graph(new char[]{'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); list<character> result = topologicalsort.topologicalsort(graph); }
执行结果
以上就是java如何实现拓扑排序的详细内容。