1
山东大学软件学院
数据结构课程设计报告
设计题目: 关键路径
学 号 201100300162
姓 名 马月昕
年 级 2011
专 业 软件工程
班 级 3
班
学 期 12-13
学年第二学期
日期: 2013 年 2 月 15 日
2
1. 需求描述
若在带权的有向图中，以顶点表示事件，以有向边表示活动，边上的权值表
示活动的开销（如该活动持续的时间），则此带权的有向图称为 AOE 网。
AOE 网在某些工程估算方面非常有用。它可以使人们了解：（ 1）研究某个
工程至少需要多少时间？（2）哪些活动是影响工程进度的关键 ，而加速这些
活动是否会提高整个工程的效率？因此，通常在 AOE 网中列出完成预定工程计
划所需要进行的活动，每个活动计划完成的时间，要发生哪些事件以及这些事
件与活动之间的关系，从而可以确定该项工程是否可行，估算工程完成的时间
以及确定哪些活动是影响工程进度的关键。
在 AOE 网络中，从源点到汇点的有向路径可能不止一条，但只有各条路径上
所有活动都完成了，这个工程才算完成。因此，完成整个工程所需的时间取决
于从源点到汇点的最长路径长度，即在这条路径上所有活动的持续时间之和，
这条路径就叫做关键路径（Critical Path）。
在设计过程中，可以用户自己输入事件个数和权值创建加权有向图，或者自
己直接画出事件与活动，或者选择程序自动生成的许多内置图，并判断此图是
否为 AOE 网络，是则找出关键路径。除此之外，程序能够允许自动执行，单步
执行，设置休眠时间，查看信息等功能。
2. 实现思想
1）判断用户自定义的有向图是否含有回路：
拓扑排序 先计算图中各顶点的入度，将入度为零的点存入队列，入队列不空
则删除队列中的元素，将其放入数组中接至的顶点的入度减一，若减一后该点
入度为零，则加入队列。重复直到队列为空。比较有向图中节点总数与拓扑序
列中节点数的相对大小，若相等则不含回路，否则，含回路，不是 AOE 网。
2）关键路径的确定：
① 事件的最早发生时间
3
求出各点入度，找到入度为零的事件（若不唯一，则不是 AOE 网）作为起
始事件。
ve[l]=0 入度为 0
ve[k]=Max{ve[j]+graph[j,k]} 入度不为 0
graph[j,k]为事件 j 与事件 k 之间活动的持续时间，即有向边的权重。
② 事件的最晚发生时间
求出各点出度，找到出度为零的事件（若不唯一，则不是 AOE 网）作为起
始事件。
vl[n]=ve[n] 出度为 0
vl[k]=Min{vl[j]-graph[k,j]} 出度不为 0
③ 活动 kj 的最早开始时间
e[kj]=ve[k] （k,j）
④ 活动 kj 的最晚发生时间
l[kj]=vl[j]-graph[k.j]
⑤ 若 e[kj]=l[kj],则活动 kj 为关键活动
⑥ 利用入度为零的起始点、关键活动，通过递归思想打印出所有的关键路径。
3. 数据结构设计
1）带权有向图的存储采用邻接矩阵。
2）用到链表、队列、拓扑序列等数据结构
核心算法代码：
① 检查是否有回路
/**
* check if the directed graph has circuits
* @param a
4
* @param b
* @return boolean
*/
private boolean isAround(int a, int b) {
//assuming add the activity from a to b
graph[a][b] = 10;
boolean result = hasCircuit();
//restore the graph
graph[a][b]=0;
return result;
}
/**
* @see whether the graph have a circuit
* @method use topological sorting
* @return boolean
*/
public boolean hasCircuit() {
int length = graph.length;
int[] InDegree = new int[length];
5
Arrays.fill(InDegree, -1);
LinkedBlockingQueue<Integer> queue = new
LinkedBlockingQueue<Integer>();
ArrayList<Integer> container = new
ArrayList<Integer>();
for(int i=0;i<length;i++)
InDegree[i] = getIn(i);
//the total number of nodes which are linked by
at least one activity
int sum = length;
for(int i=0;i<length;i++){
if(InDegree[i]==0&&getOut(i)!=0)
queue.add(i);
if(InDegree[i]==0&&getOut(i)==0)
sum--;
}
while(!queue.isEmpty()){
int p = queue.poll();
container.add(p);
for(int i=0;i<length;i++){
