文章目錄

• 1.AOE圖：
• 2.AOE圖鄰接鏈表存儲結(jié)構(gòu)：
• 3.代碼實現(xiàn)
• • 3.1.實體及參數(shù)初始化
  • 3.2.代碼實現(xiàn)
  • 3.3.輸出

1.AOE圖：

2.AOE圖鄰接鏈表存儲結(jié)構(gòu)：

3.代碼實現(xiàn)

3.1.實體及參數(shù)初始化

//鄰接表的鏈表節(jié)點 @Data public class LinkedNode {//鄰接鏈表頂點編號private int nodeNum;//頭節(jié)點到當(dāng)前鏈表節(jié)點的 弧上的權(quán)值private int weight;//當(dāng)前鏈表節(jié)點指向的下一個鏈表節(jié)點private LinkedNode nextLinkedNode;} //鄰接表中頭節(jié)點 @Data public class HeadNode {//節(jié)點編號private int nodeNum;//指向的下一個鏈表節(jié)點private LinkedNode nextLinkedNode;} //AOE網(wǎng)絡(luò) 圖 @Data public class AoeGraph {//頂點數(shù)量private int verticesNum ;//邊數(shù)量private int edgeNum;//圖的鄰接表的 頭結(jié)點集合private HeadNode[] headNode;}

將AOE圖及其鄰接鏈表的關(guān)系轉(zhuǎn)化成實體：

//AOE圖的鄰接鏈表的初始化static LinkedNode v0_2 = new LinkedNode(2,30,null);static LinkedNode v0_1 = new LinkedNode(1,10,v0_2);static HeadNode v0 = new HeadNode(0,v0_1);static LinkedNode v1_5 = new LinkedNode(5,50,null);static LinkedNode v1_3 = new LinkedNode(3,30,v1_5);static HeadNode v1 = new HeadNode(1,v1_3);static LinkedNode v2_5 = new LinkedNode(5,20,null);static LinkedNode v2_4 = new LinkedNode(4,30,v2_5);static HeadNode v2 = new HeadNode(2,v2_4);static HeadNode v3= new HeadNode(3,null);static LinkedNode v4_3 = new LinkedNode(3,10,null);static HeadNode v4 = new HeadNode(4,v4_3);static LinkedNode v5_3 = new LinkedNode(3,20,null);static HeadNode v5 = new HeadNode(5,v5_3);//鄰接鏈表的頭節(jié)點集合static HeadNode[] headNodeArr = new HeadNode[]{v0,v1,v2,v3,v4,v5};//AOE圖static AoeGraph aoeGraph = new AoeGraph(6,8,headNodeArr);

3.2.代碼實現(xiàn)

public static void main(String[] args) {int length = criticalPathCalc(aoeGraph);System.out.println("length : "+length);}public static int criticalPathCalc(AoeGraph aoeGraph){int verticesNum = aoeGraph.getVerticesNum();//圖的 頂點數(shù)量HeadNode[] headNodeArr = aoeGraph.getHeadNode(); //圖的鄰接表的 頭結(jié)點集合int [] inDegree = new int[verticesNum]; //記錄每個頂點的 實時入度 (初始化后，默認(rèn)每位都是0)int [] weightSum = new int[verticesNum];//記錄從開始頂點到 當(dāng)前頂點的 實時最大權(quán)值 (初始化后，默認(rèn)每位都是0)ConcurrentLinkedQueue<HeadNode> inDegreeZero = new ConcurrentLinkedQueue<>();//記錄入度為0 的頂點 int nodeNum =0 ; //節(jié)點的編號//計算每個節(jié)點的入度for (int i = 0; i < headNodeArr.length; i++) {HeadNode headNode = headNodeArr[i];//當(dāng)前操作的鄰接鄰接鏈表頭節(jié)點LinkedNode linkedNode = headNode.getNextLinkedNode();//當(dāng)前頭節(jié)點的指向的 鄰接節(jié)點；while (null!=linkedNode){inDegree[linkedNode.getNodeNum()]++;//指向的 鄰接節(jié)點的 入度加1linkedNode = linkedNode.getNextLinkedNode();//指針指向 頭節(jié)點的下一個鄰接節(jié)點}}//將入度為0 的節(jié)點 放入隊列for (int i = 0; i < inDegree.length; i++) {if(0==inDegree[i]){inDegreeZero.add(headNodeArr[i]);//將入度為0 的節(jié)點放入隊列}}//只要隊列不為空，就不斷彈出入度為0的節(jié)點。相當(dāng)于在圖中擦去入度為0的節(jié)點及其相關(guān)邊while (!inDegreeZero.isEmpty()){HeadNode headNode = inDegreeZero.poll();//彈出 入度為0的 節(jié)點 作為 =》頭節(jié)點(相當(dāng)于擦去入度為0的節(jié)點)System.out.println(headNode.getNodeNum());//輸出拓?fù)湫蛄?/span>LinkedNode nextLinkedNode = headNode.getNextLinkedNode();//頭節(jié)點指向的 =》 鏈表節(jié)點while (null!=nextLinkedNode){nodeNum = nextLinkedNode.getNodeNum();//當(dāng)前頭節(jié)點指向的 鏈表節(jié)點的 編號inDegree[nodeNum]--;//鏈表節(jié)點入度減1 (相當(dāng)于擦去入度為0的節(jié)點到其指向的鏈表節(jié)點之前的弧)if(0==inDegree[nodeNum]){inDegreeZero.add(headNodeArr[nodeNum]);//如果當(dāng)前鏈表節(jié)點入度=0，放入隊列（準(zhǔn)備循環(huán)把入度為0的它也擦掉）}//開始節(jié)點到當(dāng)前鏈表節(jié)點的累加權(quán)值 < 當(dāng)前頭節(jié)點到當(dāng)前鏈表節(jié)點的弧線權(quán)值 + 開始節(jié)點到當(dāng)前頭節(jié)點的累加權(quán)值if(weightSum[nodeNum] < nextLinkedNode.getWeight()+ weightSum[headNode.getNodeNum()]){//開始節(jié)點到當(dāng)前鏈表節(jié)點的最大權(quán)值 = 上訴比較的最大值weightSum[nodeNum] = nextLinkedNode.getWeight() + weightSum[headNode.getNodeNum()];}nextLinkedNode = nextLinkedNode.getNextLinkedNode();//獲取頭節(jié)點的下一個鏈表節(jié)點}}return weightSum[nodeNum];//}

3.3.輸出

0 1 2 4 5 3 length : 80

總結(jié)

以上是生活随笔為你收集整理的求AOE图的 拓扑排序 及关键路径长度（java实现）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。