減治法在求解拓撲排序問題中的應用

拓撲排序：對于一個有向無環圖來說，如果我們能夠按照次序列出頂點，使得對于每條邊來說，邊的起始頂點總是排在邊的結束頂點之前，那么這個過程就稱為拓撲排序，拓撲排序有解是一個圖是有向無環圖的充要條件?；跍p治法的拓撲排序，基本原理是源刪除，每次尋找一個入度為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) ('a'+i);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（程序評估和檢查技術）

總結

以上是生活随笔為你收集整理的减治法在求解拓扑排序问题中的应用（JAVA）--有向无环图的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。