1、 e（i）=ve（j） l（i）=vl（k）-dut（）求ve（i）和vl（j）分两步： （1）.从ve（1）=0开始向前递推ve（j）=Maxve（i）+dut（）T, 2=j=n ，其中，T是所有以j为弧头的弧的集合。（2）.从vl（n）=ve（n）开始向后递推vl（i）=Minvl（j）-dut（） S,1=i=n-1，其中，S是所有以i为弧尾的弧的集合。求关键路径的算法： 、输入e条弧，建立AOE网的存储结构； 、从起始点出发，令ve0=0，按拓扑顺序求其余各顶点的最早发生时间vei（1=i=0）； 、根据各顶点的ve和vl值，求每条弧s的最早开始时间e（s）和最迟开始时间l（s）。若
2、某弧满足条件e（s）=l（s），则为关键活动。三、操作步骤：Test1代码：Graph1.javapackage Frist;public class Graph1 public static void main（String args） String vertices = A, BCDE ;Edge edges = new Edge（0, 1, 5）, new Edge（0, 3, 2）,new Edge（1, 0, 5）, new Edge（1, 2, 7）, new Edge（1, 3, 6）,new Edge（2, 1, 7）, new Edge（2, 3, 8）, new Edge（
3、2, 4, 3）,new Edge（3, 0, 2）, new Edge（3, 1, 6）, new Edge（3, 2, 8）,new Edge（3, 4, 9）, new Edge（4, 2, 3）, new Edge（4, 3, 9） ;AdjMatrixGraph graph = new AdjMatrixGraph（vertices,edges）;System.out.println（带权无向图, + graph.toString（）;插入顶点F,插入边（A,F,20）,删除顶点C,删除边（D,E）;int i = graph.insertVertex（Fgraph.insertEd
4、ge（0, i, 20）;graph.insertEdge（i, 0, 20）;graph.removeVertex（2）;graph.removeEdge（2, 3）;graph.removeEdge（3, 2）;System.out.println（graph.toString（）; graph1 = new AdjMatrixGraphSystem.out.print（深度优先遍历序列为：graph1.DFSTraverse（0）;广度优先遍历序列为：graph1.BFSTraverse（0）; graph2 = new AdjMatrixGraph + graph2.toString（
5、）;graph2.minSpanTree_prim（）;LList.javapublic interface LList boolean isEmpty（）;int length（）;T get（int i）;void set（int i, T x）;void insert（int i, T x）;T remove（int i）;void removeAll（）;QQueue.javapublic interface QQueuevoid enqueue（T x）;T dequeue（）;SeqList.javapublic class SeqList implements LList= 0
6、& i 0）str += this.element0.toString（）;for （int i = 1; this.len; i+）str += , + this.elementi.toString（）;return str + ）public void insert（int i, T x） if （this.len = element.length） Object temp = this.element;this.element = new Objecttemp.length * 2;for （int j = 0; j temp.length;this.elementi = tempj;i
7、f （i = i; j-）this.elementj + 1 = this.elementj;this.elementi = x;this.len+;public void append（T x） insert（this.len, x）;public T remove（int i） if （this.len = 0 | i = this.len）return null;T old = （T） this.elementi;for （int j = i; this.len - 1; j+）this.elementj = this.elementj + 1;this.elementthis.len
8、- 1 = null;this.len-;return old;public void removeAll（） SeqQueue.javapublic class SeqQueue implements QQueueprivate Object element;private int front, rear;public SeqQueue（int length） if （length 64）length = 64;this.element = new ObjectMath.abs（length）;this.front = this.rear = 0;public SeqQueue（） retu
9、rn this.front = this.rear;public void enqueue（T x） if （this.front = （this.rear + 1） % this.element.length） int i = this.front, j = 0;while （i != this.rear） this.elementj = tempi;i = （i + 1） % temp.length;j+;this.front = 0;this.rear = j;this.elementthis.rear = x;this.rear = （this.rear + 1） % this.ele
10、ment.length;public T dequeue（） if （isEmpty（）T temp = （T） this.elementthis.front;this.front = （this.front + 1） % this.element.length;return temp;if （!isEmpty（） str += this.elementthis.front.toString（）;int i = （this.front + 1） % this.element.length;str += + this.element.length;GGraph.javapublic interf
11、ace GGraphpublic static final int MAX_WEIGHT = 99999;int vertexCount（）;int getWeight（int i, int j）;int insertVertex（T x）;void insertEdge（int i, int j, int weight）;void removeEdge（int i, int j）;void removeVertex（int i）;int getNextNeighbor（int i, int j）;void DFSTraverse（int i）;void BFSTraverse（int i）;
12、AbstractGraph.javapublic abstract class AbstractGraph implements GGraphpublic abstract int vertexCount（）;public abstract T get（int i）;public abstract int getNextNeighbor（int i, int j）;public void DFSTraverse（int i） boolean visited = new booleanthis.vertexCount（）;int j = i;do if （!visitedj） System.ou
13、t.print（this.depthfs（j, visited）;j = （j + 1） % this.vertexCount（）; while （j != i）;System.out.println（）;private void depthfs（int i, boolean visited） System.out.print（this.get（i） + visitedi = true;int j = this.getNextNeighbor（i, -1）;while （j != -1） visitedj）depthfs（j, visited）;j = this.getNextNeighbor
14、（i, j）;public void BFSTraverse（int i） breadthfs（j, visited）;private void breadthfs（int i, boolean visited） SeqQueue que = new SeqQueue（this.vertexCount（）;que.enqueue（new Integer（i）;while （!que.isEmpty（） i = que.dequeue（）.intValue（）;int j = this.getNextNeighbor（i, -1）;while （j !if （!System.out.print（
15、this.get（j） + visitedj = true;que.enqueue（new Integer（j）;j = this.getNextNeighbor（i, j）;public abstract int getWeight（int i, int j）;public void minSpanTree_prim（） Edge mst = new EdgevertexCount（） - 1;for （int i = 0; mst.length;msti = new Edge（0, i + 1, this.getWeight（0, i + 1）; i+） int minweight = M
16、AX_WEIGHT;int min = i;for （int j = i;if （mstj.weight minweight） minweight = mstj.weight;min = j;Edge temp = msti;msti = mstmin;mstmin = temp;int tv = msti.dest;for （int j = i + 1; j+） int v = mstj.dest;if （this.getWeight（tv, v） mstj.weight） msti.weight = this.getWeight（tv, v）;mstj.start = tv;n最小生成树边
17、的集合:int mincost = 0; mst.length - 1;System.out.print（msti + mincost += msti.weight;,最小代价为 + mincost）;AdjMatrixGraph.javapublic class AdjMatrixGraph extends AbstractGraphprotected SeqList vertexlist;protected int adjmatrix;private final int MAX_WEIGHT = 99999;public AdjMatrixGraph（int size） size = si
18、ze 10 ? 10 : size;this.vertexlist = new SeqList（size）;this.adjmatrix = new intsizesize;this.adjmatrixij = （i = j） ? 0 : MAX_WEIGHT;public AdjMatrixGraph（T vertices, Edge edges） this（vertices.length）;if （vertices = null） vertices.length;insertVertex（verticesi）;if （edges != null） edges.length;insertEdge（edgesj）;public void insertEdge（int i, int j, int weight） int n = this.vertexCount（）; 0 & n & i != j& this.adjmatrixij = MAX_WEIGHT）this.adjmatrixij = weight;pu
