展示型网站建设模板,网店托管服务,wordpress 改成 中文,网站多大够用减治法在求解拓扑排序问题中的应用
拓扑排序#xff1a;对于一个有向无环图来说#xff0c;如果我们能够按照次序列出顶点#xff0c;使得对于每条边来说#xff0c;边的起始顶点总是排在边的结束顶点之前#xff0c;那么这个过程就称为拓扑排序#xff0c;拓扑排序有解…减治法在求解拓扑排序问题中的应用
拓扑排序对于一个有向无环图来说如果我们能够按照次序列出顶点使得对于每条边来说边的起始顶点总是排在边的结束顶点之前那么这个过程就称为拓扑排序拓扑排序有解是一个图是有向无环图的充要条件。基于减治法的拓扑排序基本原理是源删除每次寻找一个入度为0的点根据这个点的出度找到下一个点然后删除这个点和所有的所有出度再继续迭代操作。 public class Main {public static void main(String[] args) {int[][] e {{0, 0, 1, 0, 0},{0, 0, 1, 0, 0},{0, 0, 0, 1, 1},{0, 0, 0, 0, 1},{0, 0, 0, 0, 0},};char[] result f(e);for(int i 0;i result.length;i)System.out.print(result[i] );}public static char[] f(int[][] e){int[] source get(e);char[] result new char[source.length];int cnt 0;int flag 1;while(flag 1){for(int i 0;i source.length;i){/*** 寻找入度为0的点进入排序队列入度值设为-1* */if(source[i] 0) {result[cnt] (char) (ai);source[i] -1;for(int j 0;j e[i].length;j) {if(e[i][j] 1) {source[j] - 1; //第j个顶点的入度减1}}}}if(cnt source.length)flag 0;}return result;}/*** 返回给出图每个顶点的入度值*/public static int[] get(int[][] e){int len e[0].length;int[] source new int[len];for(int i 0;i len;i){int count 0;for(int j 0;j len;j){/*** 列对应入读* */if(e[j][i] 1)count;}source[i] count;}return source;}
} 发现问题拓扑排序的解通常不止一个如果是数据量庞大的工程那么在进行算法之前一定要检查集合是否满足有向无环图而且大数据量的情况下这种基于减治的算法和基于搜索算法DFS效率都是不高的。
优化思路CPM关键路径法和PERT程序评估和检查技术
