第六章 图
★ 基本术语
★ 图的存储结构
★ 图的遍历
North China Electric Power University
★ 最小生成树和最短路径问题
★ AOV网与拓扑排序
★ AOE网与关键路径
★ 基本术语
North China Electric Power University
图是由 顶点的非空有穷集合 与 顶点之间关系
(边或弧 )的集合 构成的结构,通常表示为
G = ( V,E)
其中,V 为顶点集合,E 为关系 (边或弧 )的集合,
一,图的定义华电 计算机系
North China Electric Power University
(b),这条边依附于顶点 vi 和 vj。
(vi,vj)
vjvivjvi
vj
vi
vj
vi
关于一条边或弧的表示方法,
(a),顶点 vi 与 vj 是这条边的两个邻接点。
(1),用图形,
(2),用符号,
(3),用语言,
华电计算机系
North China Electric Power University
华电 计算机系
v1
v2 v3
v4
其中
V1 = { v1,v2,v3,v4 }
E1 = { (v1,v2),(v1,v3),
(v1,v4),(v2,v3),
(v2,v4),(v3,v4) }
G1=(V1,E1)
v1
v2 v3
v4
其中
V2 = { v1,v2,v3,v4 }
E2 = { <v1,v2>,<v2,v1>,
<v2,v3>,<v4,v3> }
G2=(V2,E2)
North China Electric Power University
无向图：
有向图：
与边有关的数据称为 权,边上带权的图称为 网络 。
二,图的分类对于 （ vi,vj)?E,必有 （ vj,vi)?E，并且偶对中顶点的前后顺序无关。
若 <vi,vj>?E是顶点的有序偶对。
华电 计算机系网 (络 )：
v1
v2 v3
v4
v1
v2 v3
v4
v1
v2 v3
v4
10
4 17
8
North China Electric Power University
1.顶点的度对于有向图而言,有,
顶点的 出度,
以顶点 vi 为出发点的边的数目,记为 OD(vi).
顶点的 入度,
以顶点 vi 为终止点的边的数目,记为 ID(vi).
TD(vi) = OD(vi) + ID(vi)
三,名词术语依附于顶点 vi的边的数目,记为 TD(vi).
华电 计算机系
v1
v3
v4
v1
v2 v3
v4
v2
North China Electric Power University
边的数目达到最大的图称为完全图,边的数目达到或接近最大的图称为稠密图,否则,称为稀疏图,
具有 n个顶点的有向图最多有 n(n-1) 条边,
具有 n个顶点的无向图最多有 n(n-1)/2 条边,
对于具有 n个顶点,e条边的图,有
2e =?TD(vi)n
i=1
结论 1
结论 2
结论 3
华电 计算机系
North China Electric Power University
2,路径
DC
E
B
A P(A,E),A,B,E
A,C,D,E
出发点与终止点相同的路径称为回路或环；顶点序列中顶点不重复出现的路径称为简单路径。不带权的图的路径长度是指路径上所经过的边的数目，带权的图的路径长度是指路径上经过的边上的权值之和。
顶点 vx到 vy之间有路径 P(vx,vy)的充分必要条件为,存在顶点序列 vx,vi1,vi2,…,v im,vy,并且序列中相邻两个顶点构造的顶点偶对分别为图中的一条边。
华电 计算机系
North China Electric Power University
3.子图
v1
v
2
v3
v4
对于图 G=(V,E) 与 G′=(V′,E′),若有 V′?V,E′?E,
则称 G′为 G的一个子图,
华电 计算机系
v1
v
2
v3
v4
v1
v
2
North China Electric Power University
4.图的连通无向图中顶点 vi 到 vj 有路径,则称顶点 vi 与 vj 是连通的。
若无向图中任意两个顶点都连通,则称该无向图是连通的。
若有向图中顶点 vi 到 vj 有路径,并且顶点 vj 到 vi 也有路径,则称顶点 vi 与 vj 是连通的。
若有向图中任意两个顶点都连通,则称该有向图是强连通的。
(1).无向图的连通
(2).有向图的连通华电 计算机系
North China Electric Power University
5.生成树华电 计算机系包含具有 n 个顶点的连通图 G 的全部 n 个顶点,仅包含其 n-1条边的连通子图称为 G 的一个生成树。
v1
v3
v4
v2
v1
v3
v4
v2
v1
v3
v4
v2
v1
v3
v4
v2
v1
v3
v4
v2
North China Electric Power University
华电 计算机系对于一个图,需要存储的信息应该包括,
(1).所有顶点的数据信息；
(2).顶点之间关系 (边或弧 )的信息 ;
(3).权的信息。
★ 图的存储结构
North China Electric Power University
一,邻接矩阵存储方法核心思想,采用两个数组存储一个图,
1,定义一个一维数组 VERTEX[1:n]存放图中所有顶点的数据信息,
2,定义一个二维数组 A[1:n,1:n]存放图中所有顶点之间关系的信息 (该数组被称为邻接矩阵 ),有
1 当顶点 vi到顶点 vj有边时
A[i,j]=
0 当顶点 vi到顶点 vj无边时
对于带权的图,有
wij 当顶点 vi到顶点 vj有边,且边的权为 wij
A[i,j]=
当顶点 vi到顶点 vj无边时?oo
数组存储方法华电 计算机系
North China Electric Power University
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
A1 =
v1
v2
v3
v4
Vertex1[1:4]
v1
v2
v3
v4
Vertex2[1:4]? 4
6? 7?
8?
A2 =
华电 计算机系
v1
v2 v3
v4
v1
v2 v3
v4
10
4 17
8
North China Electric Power University
(1).无向图的邻接矩阵一定是一个对称矩阵,
(2).不带权的有向图的邻接矩阵一般是一个稀疏矩阵。
(3).无向图的邻接矩阵的第 i 行 (或第 i 列 )非 0 或非?
元素的个数为第 i 个顶点的度数,
(4).有向图的邻接矩阵的第 i 行非 0或非?元素的个数为第 i 个顶点的出度 ;第 i 列非 0或非?元素的个数为第
i 个顶点的入度。
特点,
华电 计算机系
North China Electric Power University
二,邻接表存储方法核心思想,对具有 n个顶点的图建立 n个线性链表存储该图,
1,每一个链表前面设置一个头结点,用来存放一个顶点的数据信息,称之为顶点结点,其结构为,
vertex link
其中,vertex 域存放某个顶点的数据信息 ;
link 域存放某个链表中第一个结点的地址,
2,第 i 个链表中的每一个链结点 (称之为边结点 )表示以第 i
个顶点为出发点的一条边 ;边结点的构造为
nextweightadjvex
其中,next 域为指针域 ;
weight 域为权值域 (若图不带权,则无此域 );
adjvex 域存放以第 i 个顶点为出发点的一条边的另一端点在头结点数组中的位置,
n个头结点之间为一数组结构,
华电 计算机系
North China Electric Power University
1
2
3
4
v1
v2
v3
v4
4
7
8
61
2
3
3
^
^
^
^
(1).无向图的第 i 个链表中边结点的个数是第 i 个顶点度数,
(2).有向图的第 i 个链表中边结点的个数是第 i 个顶点的出度。
特点
^
^
^
^
1
2
3
4
v1
v3
v2
v4
2
3
43
3
2
41
1 4
21
华电计算机系
v1
v2 v3
v4
v1
v2 v3
v4
6
4 7
8
Type edgeptr=?edgenode;
edgenode=record
adjvex:1..n;
weight:real;
next:edgeptr;
end;
vexnode=record
vertex:vertype;
link:edgeptr;
end;
adj_list=Array[1..n] of vexnode;
邻接表的类型定义
North China Electric Power University
North China Electric Power University
1
2
3
4
v1
v2
v3
v4
6
41
2
^
^
72 84 ^
^
三,有向图的十字链表存储方法
(略 )
四,无向图的多重邻接表存储方法
(略 )
关于逆邻接表华电 计算机系
v1
v2 v3
v4
6
4 7
8
North China Electric Power University
A
D
E
F
C
B
A
B
C
D
E
F
^
^
^
^
^
^
1
2
3
4
5
6
2 3 4 6
1 3 4
1 2 4 5
1 2 3 5
3 4 6
1 5
例 已知一具有 n个顶点的无向图 G采用邻接表存储方法,
写一算法,删除图中数据信息为 item 的那个顶点,
需要做的工作,
(1),寻找满足条件的那个顶点 ;
(2),从头结点数组中删除该顶点 ;
(3),删除与该顶点相关的边 ;
(4),修改有关的边结点的 adjvex 域的内容。
华电计算机系
North China Electric Power University
华电 计算机系
A
D
E
F
C
B
A
B
C
D
E
F
^
^
^
^
^
1
2
3
4
5
6
2 3 4 6
1 3 4
1 2 4 5
1 2 3 5
3 4 6
1 5
A
D
E
F
C
B
A
B
D
E
F
F
^
^
1
2
3
4
5
6
2 3 5
1 3
1 2 4
3 5
1 4
^
^
^
North China Electric Power University
procedure Del( g,n,item );
begin
k:=0;
for i:=1 to n do
if(g[i].vertex=item)then
[ k:=i; exit;]
if (k=0) then
return;
p:=g[k].link;
for i:=k+1 to n do
[ g[i-1].vertex:=g[i].vertex;
g[i-1].link:=g[i].link;
]
n:=n–1; // 顶点的个数减 1 //
while(p<>nil) do
[ q:=p;
p:=p?.next; dispose(q);
] 华电计算机系
for i:=1 to n do
[ p:=g[i].link;
while (p<>nil） do
if(p?.adjvex=k) then
[ if(g[i].link=p) then
g[i].link:=p?.next
else
q?.next:=p?.next;
r:=p;p:=p?.next;
dispose(r); ]
else
[ if (p?.adjvex>k) then
p?.adjvex:= p?.adjvex–1;
q:=p;
p:=p?.next;
]
]
end; 北航 计算机系
North China Electric Power University
从图中某个指定的顶点出发,按照某一原则对图中所有顶点都访问一次,得到一个由图中所有顶点组成的序列,这一过程称为图的遍历,
原则,
从图中某个指定的顶点 v出发,先访问顶点 v,然后从顶点 v 未被访问过的一个邻接点出发,继续进行深度优先遍历,直到图中与 v 相通的所有顶点都被访问 ;若此时图中还有未被访问过的顶点,则从另一个未被访问过的顶点出发重复上述过程,直到遍历全图,
一,深度优先搜索华电 计算机系
★ 图的遍历为了标记某一时刻图中哪些顶点是否被访问,定义一维数组 visited[1:n],有
1 表示 第 i个顶点已经被访问
visited[i] =
0 表示 第 i个顶点还未被访问
North China Electric Power University
North China Electric Power University
二,广度优先搜索华电 计算机系原则,
从图中某个指定的顶点 v出发,先访问顶点 v,然后依次访问顶点 v的各个未被访问过的邻接点,然后又从这些邻接点出发,按照同样的规则访问它们的那些未被访问过的邻接点，如此下去，直到图中与 v 相通的所有顶点都被访问 ;
若此时图中还有未被访问过的顶点,则从另一个未被访问过的顶点出发重复上述过程,直到遍历全图,
North China Electric Power University
可以用深度优先搜索或广度优先搜索算法来判断图是否连通。在对无向图进行遍历时，对于连通图，仅需要一次搜索过程，图中的顶点就全部被访问。对于非连通图，则需要多次调用搜索过程，而每次调用得到的顶点访问序列恰好为其各个连通分量中的顶点集。
三,求图的连通分量算法,procedure component(var g);
begin
for i:=1 to vnum do visited[i]:=0;count:=0;
for i:=1 to vnum do
if visited[I]=0 then [count:=count+1;dfs(g,i);]
end;
North China Electric Power University
★ 最小生成树和最短路径问题带权连通图中,总的权值之和最小的带权生成树为最小生成树,最小生成树也称最小代价生成树,或最小花费生成树,
构造网的最小生成树的依据：
1,在网中选择 n-1条边，连接网的 n个顶点；
2,尽可能选取权值为最小的边。
最小生成树的概念：
最小生成树问题
v4
v2
v6
v5
v3
v1 16
11 5
6
9
18
1419 22
20
最小生成树的权值 = 56
Kruskal算法：
1.设 T的初态为空集；
2.当 T中边数小于 n-1时做下列工作
①从 E中选取权值为最小的边 (v,w)，并删除之；
②若 (v,w)不和 T 中的边一起构成回路，则将边
(v,w)加入到 T中去。
1
2 4
65
3
6 5
3
6
2
1
5
4
6
5
1
2 4
65
3
① T为空
North China Electric Power University
1
2 4
65
3
② 选权值最小的边 (1,3)
从 E中将其删去
1
1
2 4
65
3
1
③ 选 E中最小的边 (4,6)从 E
中将其删去
2
1
2 4
65
3
1
2
④ 从 E中选最小的边 (2,5)
从 E中将其删去
3
1
2 4
65
3
1
23
⑤ 从 E中选最小的边 (3,6)从
E中将其删去
4
North China Electric Power University
⑥ 从 E中选最小的边 (3,4)，但加入
T后会使 T中出现回路，所以边 (3,4)
不可取，把边 (3,4)从 E中删除。再看 (1,4)同样会使 T构成回路，仍不可取，从 E中删去 (1,4)，选 (2,3)，
从 E中删去 (2,3),最后已够 5条边了，
这样生成树就是最小生成树。最小生成树可能不唯一，但权的总数相同。
2 4
65
3
1
23
4
1
5
算法的思想明确、也很简单，但具体实现时比较困难，需要解决一些具体的问题，譬如如何使所选的新边没有和已选的边构成回路。
算法讨论：
North China Electric Power University
Prim算法：
1.设 V(T)的初态为空集 (V(T)为落在生成树上的顶点集合 );
2.在连通图上任选一顶点加入到 V(T)集合中去；
3.将下列步骤重复 n-1次：
①在 i属于 V(T),j不属于 V(T)的边中，选权值最小的边
(i,j)；
②将顶点 j加入到 V(T)中去；
③输出 i,j及 Wij。
North China Electric Power University
例：①初态 V(T)=φ
② 选①顶点 =>V(T)=｛ 1｝
③做 n-1次
1)边 (1,2)的权值最小，
∴ 将② =>V(T)=｛ 1,2｝ ;
write(1,2)
weight 16
1 2
4
6
5
3
2)边 (2,3)的权值最小，
∴ 将③ =>V(T)=
｛ 1,2,3｝ ;
write(2,3)
weight 5
3)边 (3,4)的权值最小，
∴ 将④ =>V(T)=
｛ 1,2,3,4｝ ;
write(3,4)
weight 6
16
5
6
18
19
21 11
1433
6
North China Electric Power University
4)边 (2,6)的权值最小，
∴ 将⑥ =>V(T)=｛ 1,2,3,4,6｝ ;
write(2,6) weight 11
5)边 (4,5)的权值最小，
∴ 将⑤ =>V(T)=
｛ 1,2,3,4,5,6｝ ;
write(4,5) weight 18
∑ i=16 Weight = 56
1 2
4
6
5
3
16
5
6
18
19
21 11
1433
6
1 2
4
6
5
3
16
5
6
18
11
North China Electric Power University
最短路径问题一,路径长度的定义
1,不带权的图,路径上所经过的边的数目 。
2,带权的图,路径上所经过的边上的权值之和,
二,问题的提出三,解决问题所需要确定的数据结构
1,图的存储,以 1~n 分别代表 n个顶点,采用邻接矩阵存储该图,有
Wij 当顶点 vi 到顶点 vj 有边,且权为 Wij
A[i,j]=? 当顶点 vi 到顶点 vj无边时
0 当 vi=vj 时?
设出发顶点为 v(通常称为源点 )。
North China Electric Power University
2,设置一个标志数组 S[1:n]记录源点 v 到图中哪些顶点的最短路径已经找到，有：
1 表示源点到顶点 i 的最短路径已经找到
S[i] =
0 表示源点到顶点 i 的最短路径尚未找到初始时,S[v]=1,S[i]=0 i =1,2,?,n i?v
{
3,设置数组 dist[1:n] 分别记录源点 v 到图中各顶点的最短路径的路径长度,其中,dist[i]记录源点到顶点 i 的最短路径的长度；初始时,dist数组的值为邻接矩阵第 v 行的 n个元素值。
4,设置数组 path[1:n] 分别记录源点 v 到图中各顶点的最短路径所经过的顶点序列，其中,path[i]记录源点到顶点 i 的路径，初始时,path[i]=? v?,i =1,2,3,?,n
华电计算机系
0 1
3 52
4
45
50 10
20 10 15
15
20
3
35 30
v0是源点 最短路径
v0→v2 10
v0→v2→v3 10+15=25
v0→v2→v3→v1 10+15+20
v0→v4 45
v0→v5 无路可走从以上可以发现每一条最短路径中间所经过的顶点具有如下特点：下一条最短路径 (设其终点为 x)可能是 <v0,x>,或者
<v0,u,…,v,x>，而 u,…,v都是已求得的最短路径终点。
例假设 S为已求得的最短路径的终点的集合 (S初态为空集 )，则下一条长度次短的最短路径（设终点为 x）：
或者是弧 <v0,x>；
或者是中间经过 S集合中顶点，最后到达顶点 x的路径。
Dijkstra算法思想：
North China Electric Power University
4.算法 (用自然语言表达 )
1,确定 dist,S,path 三个数组的初值。
2,利用 S数组与 dist 数组在那些尚未找到最短路径的顶点中确定一个与源点最近的顶点 u,并置 S[u]为 1，同时将顶点
u加入 path[u].
3,根据顶点 u修改源点到所有尚未找到最短路径的顶点的路径长度。 即
1） 将源点 v到顶点 u的 (最短 )路径长度分别加到源点 v
通过顶点 u可以直接到达、且尚未找到最短路径的那些顶点的路径长度上 ;若加后的长度小于原来 v 到某顶点 r的路径长度，则用加后的长度替代原来的长度，否则不替代。
2）若替代，将源点 v 到顶点 u 的路径 (最短路径 )上经过的所有顶点替换 path[r].
4,重复第 2 至第 3 步 n-1 次。
for i?1 to n do
dist[i]?cost[v,i]
end
S[i]?0
S[v]?1
path[i]?{ v }
北航计算机系
North China Electric Power University
Floyed算法思想：
从 i 到 j的路径上每次增加一个结点 k，看这个增加了一个结点 k的新路径的长度是否比原来的路径长度小，若小,则以新路径代之,否则保持原路径。
A(k)[i,j]=min{A(k-1)[i,j],A(k-1)[i,k]+A(k-1)[k,j]} (1≤k≤n)
算法计算公式：
其中,
A(k)[i,j]表示顶点 i,j之间的中间点的序号不大于 k的最短距离 ;
由于 G中顶点编号不大于 n，所以最后到了 An[i,j]就代表
i到 j的最短路径之长。
North China Electric Power University
算法描述：
procedure all_path(cost);
Begin
for i:=1 to n do
for j:=1 to n do
[ a[i,j]:=cost[i,j];
if(i<>j)and(a[i,j]<max) then
path[i,j]=[i]+[j]
]
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if a[i,k]+a[k,j]<a[i,j] then
[ a[i,j]:=a[i,k]+a[k,j];
path[i,j]:=path[i,k]+path[k,j];
]
End;
North China Electric Power University
cost=
0 4 11
6 0 2
3 ∞ 0
cost:带权邻接矩阵
A：最短路径长度
P：相应的路径例,6
4
11
3 2
A B
C
3
21
初态 K=0时，
A(0) 1 2 3
1
2
3
0 4 11
6 0 2
3 ∞ 0
AB AC
Path(0) 1 2 3
1
2
3
BA BC
CA
North China Electric Power University
K=1时，
A(1) 1 2 3 Path(1) 1 2 3
1 0 4 11 1 AB AC
2 6 0 2 2 BA BC
3 3 7 0 3 CA CAB
K=2时，
A(2) 1 2 3 Path(2) 1 2 3
1 0 4 6 1 AB ABC
2 6 0 2 2 BA BC
3 3 7 0 3 CA CAB
North China Electric Power University
K=3时，
A(3) 1 2 3 Path(3) 1 2 3
1 0 4 6 1 AB ABC
2 5 0 2 2 BCA BC
3 3 7 0 3 CA CAB
North China Electric Power University
★ AOV网与拓扑排序一,什么是 AOV网验收筹备招标备料进驻工地测量 挖地基浇注水泥搭架子
…
例 1
North China Electric Power University
华电 计算机系程序语言数据结构离散数学软件工程操作系统编译原理数据库计算机组成汇编网络数字逻辑计算机导论例 2
North China Electric Power University
华电计算机系二,AOV网的定义在 AOV网中，若顶点 i 到顶点 j 之间有有向路径，
则称顶点 i 为顶点 j 的前驱，顶点 j 为顶点 i的后继；若顶点 i 到顶点 j 之间为一条有向边，则称顶点 i 为顶点 j
的直接前驱，顶点 j 为顶点 i 的直接后继。
以顶点表示活动，以有向边表示活动之间的优先关系的有向图称为 AOV网。
North China Electric Power University
三,拓扑排序检查 AOV网是否存在回路的方法是对 AOV网进行拓扑排序，构造一个序列，使得该序列满足条件：
1,若在 AOV网中，顶点 i 优先于顶点 j,则在该序列中也是顶点 i 优先于顶点 j 。
2,若在 AOV网中,顶点 i 与顶点 j之间不存在优先关系,则在该序列中建立它们的优先关系，即顶点 i
优先于顶点 j，或顶点 j 优先于顶点 i 。
3,若能够构造出拓扑序列，则拓扑序列包含 AOV
网的全部顶点。
North China Electric Power University
四,拓扑排序方法
1,从 AOV网中任选择一个没有前驱 (入度为 0)的顶点 ；
2,从 AOV网中去掉该顶点以及以该顶点为出发点的所有边；
3,重复上述过程，直到网中的所有顶点都被去掉,或者网中还有顶点，但不存在入度为 0 的顶点；
前者说明 AOV网中无回路，
后者说明 AOV网中存在回路。
North China Electric Power University
v1
v4
v3
v2
v6
v5
v7
v1 v5 v7v3v6 v2 v4
例华电计算机系
v4
v3
v2
v6
v7
v4
v3
v2
v6
v5
v7
v4
v3
v2
v7
v4
v3 v7
v4
v7 v7
North China Electric Power University
★ AOE网与关键路径筹备付款签合同做预置件验收施工
…
招标
7天联系材料
8天图纸设计
15天进驻工地
4天运材料
6天搬运
3
天例
North China Electric Power University
一,AOE网的定义
AOE网为一个带权的有向无环图，其中，顶点表示事件，有向边表示活动，边上的权值表示活动持续的时间。
v1
v4
v2
v3
v5
v7
v9
v8
v6
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
6
4
5
1
1
2
9
7
2
4
4
正常情况下,AOE网中只有一个入度为 0 的顶点，称之为 源点 ；有一个出度为 0 的顶点，称之为 终点 。
North China Electric Power University
1.只有在某个顶点所代表的事件发生以后,该顶点引发的活动才能开始。
2.进入某事件的所有边所代表的活动都已完成,该顶点所代表的事件才能发生。
AOE网的特点,
1,关键路径的定义从源点到终点的路径中具有最大路径长度的路径为关键路径 ; 关键路径上的活动称为关键活动。
二,AOE网的存储方法三,关键路径采用邻接矩阵存储方法。
North China Electric Power University
2,关键路径的特点
1) 关键路径的长度 (路径上的边的权值之和 )为完成整个工程所需要的最短时间。
2) 关键路径的长度变化 (即任意关键活动的权值变化 )
将影响整个工程的进度，而其他非关键活动在一定范围内的变化不会影响工期。
求关键活动的思路：
e(i) — 活动 ai 的最早开始时间
l(i) — 活动 ai 的最迟开始时间若 l(i)–a(i)=0，则说明活动 ai 为一个关键活动。
Ve(k) — 事件 k 的最早发生时间 k ai
Vl(k) — 事件 k 的最迟发生时间 ai k
North China Electric Power University
事件 k的最早发生时间 ee(k)
事件 k的最迟发生时间 le(k)
活动的 ai 最早开始时间 e(i)
活动的 ai 最迟开始时间 l(i)
求 e(i) = l(i)
结论
1,计算事件 k的最早发生时间 Ve(k)
所谓事件 k的最早发生时间 Ve(k)是指从源点到顶点 k
的最大路径长度,
计算方法,
Ve(1) = 0
Ve(k) = Max{ Ve(j) + <j,k>的权 }
<j,k>?P( j )
四,求关键路径
k
North China Electric Power University
华电 计算机系
2,计算事件 k的最迟发生时间 Vl(k)
所谓事件 k 的最晚发生时间 Vl(k)是指不影响整个工期的前提下事件 k 必须发生的最晚时间。
计算方法,
Vl(n) = Ve(n)
Vl(k) = Min{ Vl(j) – <k,j>的权 }
<k,j>?S(k)
k
North China Electric Power University
3,计算活动 i的最早开始时间 e(i)
所谓活动 i 的最早开始时间 e(i) 是事件 k发生的最早时间，即只有事件 k 发生了，活动 i 才能开始。
活动 ik j
计算方法,e(i) = Ve(k)
4,计算活动 i 的最迟开始时间 l(i)
所谓活动 i 的最迟开始时间 l(i) 是指不推迟整个工期的前提下活动 i 开始的最晚时间。
计算方法,l(i) = le(j) -<k,j>的权活动 ik j
North China Electric Power University
5,求出关键活动与关键路径计算方法,l(i) = e(i)
1 2 3 4 5 6 7 8 9 10 11
l(i),0 2 3 6 6 8 7 7 10 16 14
1 2 3 4 5 6 7 8 9 10 11
e(i),0 0 0 6 4 5 7 7 7 16 140
0
a1 a7a4 a10a8 a11
6
6 7
7
7
7
16
16 14
v1
v4
v2
v3
v5
v7
v9
v8
v6
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
6
4
5
1
1
2
9
7
2
4
4
关键路径的长度为 18个时间单位 。
North China Electric Power University
★ 基本术语
★ 图的存储结构
★ 图的遍历
North China Electric Power University
★ 最小生成树和最短路径问题
★ AOV网与拓扑排序
★ AOE网与关键路径
★ 基本术语
North China Electric Power University
图是由 顶点的非空有穷集合 与 顶点之间关系
(边或弧 )的集合 构成的结构,通常表示为
G = ( V,E)
其中,V 为顶点集合,E 为关系 (边或弧 )的集合,
一,图的定义华电 计算机系
North China Electric Power University
(b),这条边依附于顶点 vi 和 vj。
(vi,vj)
vjvivjvi
vj
vi
vj
vi
关于一条边或弧的表示方法,
(a),顶点 vi 与 vj 是这条边的两个邻接点。
(1),用图形,
(2),用符号,
(3),用语言,
华电计算机系
North China Electric Power University
华电 计算机系
v1
v2 v3
v4
其中
V1 = { v1,v2,v3,v4 }
E1 = { (v1,v2),(v1,v3),
(v1,v4),(v2,v3),
(v2,v4),(v3,v4) }
G1=(V1,E1)
v1
v2 v3
v4
其中
V2 = { v1,v2,v3,v4 }
E2 = { <v1,v2>,<v2,v1>,
<v2,v3>,<v4,v3> }
G2=(V2,E2)
North China Electric Power University
无向图：
有向图：
与边有关的数据称为 权,边上带权的图称为 网络 。
二,图的分类对于 （ vi,vj)?E,必有 （ vj,vi)?E，并且偶对中顶点的前后顺序无关。
若 <vi,vj>?E是顶点的有序偶对。
华电 计算机系网 (络 )：
v1
v2 v3
v4
v1
v2 v3
v4
v1
v2 v3
v4
10
4 17
8
North China Electric Power University
1.顶点的度对于有向图而言,有,
顶点的 出度,
以顶点 vi 为出发点的边的数目,记为 OD(vi).
顶点的 入度,
以顶点 vi 为终止点的边的数目,记为 ID(vi).
TD(vi) = OD(vi) + ID(vi)
三,名词术语依附于顶点 vi的边的数目,记为 TD(vi).
华电 计算机系
v1
v3
v4
v1
v2 v3
v4
v2
North China Electric Power University
边的数目达到最大的图称为完全图,边的数目达到或接近最大的图称为稠密图,否则,称为稀疏图,
具有 n个顶点的有向图最多有 n(n-1) 条边,
具有 n个顶点的无向图最多有 n(n-1)/2 条边,
对于具有 n个顶点,e条边的图,有
2e =?TD(vi)n
i=1
结论 1
结论 2
结论 3
华电 计算机系
North China Electric Power University
2,路径
DC
E
B
A P(A,E),A,B,E
A,C,D,E
出发点与终止点相同的路径称为回路或环；顶点序列中顶点不重复出现的路径称为简单路径。不带权的图的路径长度是指路径上所经过的边的数目，带权的图的路径长度是指路径上经过的边上的权值之和。
顶点 vx到 vy之间有路径 P(vx,vy)的充分必要条件为,存在顶点序列 vx,vi1,vi2,…,v im,vy,并且序列中相邻两个顶点构造的顶点偶对分别为图中的一条边。
华电 计算机系
North China Electric Power University
3.子图
v1
v
2
v3
v4
对于图 G=(V,E) 与 G′=(V′,E′),若有 V′?V,E′?E,
则称 G′为 G的一个子图,
华电 计算机系
v1
v
2
v3
v4
v1
v
2
North China Electric Power University
4.图的连通无向图中顶点 vi 到 vj 有路径,则称顶点 vi 与 vj 是连通的。
若无向图中任意两个顶点都连通,则称该无向图是连通的。
若有向图中顶点 vi 到 vj 有路径,并且顶点 vj 到 vi 也有路径,则称顶点 vi 与 vj 是连通的。
若有向图中任意两个顶点都连通,则称该有向图是强连通的。
(1).无向图的连通
(2).有向图的连通华电 计算机系
North China Electric Power University
5.生成树华电 计算机系包含具有 n 个顶点的连通图 G 的全部 n 个顶点,仅包含其 n-1条边的连通子图称为 G 的一个生成树。
v1
v3
v4
v2
v1
v3
v4
v2
v1
v3
v4
v2
v1
v3
v4
v2
v1
v3
v4
v2
North China Electric Power University
华电 计算机系对于一个图,需要存储的信息应该包括,
(1).所有顶点的数据信息；
(2).顶点之间关系 (边或弧 )的信息 ;
(3).权的信息。
★ 图的存储结构
North China Electric Power University
一,邻接矩阵存储方法核心思想,采用两个数组存储一个图,
1,定义一个一维数组 VERTEX[1:n]存放图中所有顶点的数据信息,
2,定义一个二维数组 A[1:n,1:n]存放图中所有顶点之间关系的信息 (该数组被称为邻接矩阵 ),有
1 当顶点 vi到顶点 vj有边时
A[i,j]=
0 当顶点 vi到顶点 vj无边时
对于带权的图,有
wij 当顶点 vi到顶点 vj有边,且边的权为 wij
A[i,j]=
当顶点 vi到顶点 vj无边时?oo
数组存储方法华电 计算机系
North China Electric Power University
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
A1 =
v1
v2
v3
v4
Vertex1[1:4]
v1
v2
v3
v4
Vertex2[1:4]? 4
6? 7?
8?
A2 =
华电 计算机系
v1
v2 v3
v4
v1
v2 v3
v4
10
4 17
8
North China Electric Power University
(1).无向图的邻接矩阵一定是一个对称矩阵,
(2).不带权的有向图的邻接矩阵一般是一个稀疏矩阵。
(3).无向图的邻接矩阵的第 i 行 (或第 i 列 )非 0 或非?
元素的个数为第 i 个顶点的度数,
(4).有向图的邻接矩阵的第 i 行非 0或非?元素的个数为第 i 个顶点的出度 ;第 i 列非 0或非?元素的个数为第
i 个顶点的入度。
特点,
华电 计算机系
North China Electric Power University
二,邻接表存储方法核心思想,对具有 n个顶点的图建立 n个线性链表存储该图,
1,每一个链表前面设置一个头结点,用来存放一个顶点的数据信息,称之为顶点结点,其结构为,
vertex link
其中,vertex 域存放某个顶点的数据信息 ;
link 域存放某个链表中第一个结点的地址,
2,第 i 个链表中的每一个链结点 (称之为边结点 )表示以第 i
个顶点为出发点的一条边 ;边结点的构造为
nextweightadjvex
其中,next 域为指针域 ;
weight 域为权值域 (若图不带权,则无此域 );
adjvex 域存放以第 i 个顶点为出发点的一条边的另一端点在头结点数组中的位置,
n个头结点之间为一数组结构,
华电 计算机系
North China Electric Power University
1
2
3
4
v1
v2
v3
v4
4
7
8
61
2
3
3
^
^
^
^
(1).无向图的第 i 个链表中边结点的个数是第 i 个顶点度数,
(2).有向图的第 i 个链表中边结点的个数是第 i 个顶点的出度。
特点
^
^
^
^
1
2
3
4
v1
v3
v2
v4
2
3
43
3
2
41
1 4
21
华电计算机系
v1
v2 v3
v4
v1
v2 v3
v4
6
4 7
8
Type edgeptr=?edgenode;
edgenode=record
adjvex:1..n;
weight:real;
next:edgeptr;
end;
vexnode=record
vertex:vertype;
link:edgeptr;
end;
adj_list=Array[1..n] of vexnode;
邻接表的类型定义
North China Electric Power University
North China Electric Power University
1
2
3
4
v1
v2
v3
v4
6
41
2
^
^
72 84 ^
^
三,有向图的十字链表存储方法
(略 )
四,无向图的多重邻接表存储方法
(略 )
关于逆邻接表华电 计算机系
v1
v2 v3
v4
6
4 7
8
North China Electric Power University
A
D
E
F
C
B
A
B
C
D
E
F
^
^
^
^
^
^
1
2
3
4
5
6
2 3 4 6
1 3 4
1 2 4 5
1 2 3 5
3 4 6
1 5
例 已知一具有 n个顶点的无向图 G采用邻接表存储方法,
写一算法,删除图中数据信息为 item 的那个顶点,
需要做的工作,
(1),寻找满足条件的那个顶点 ;
(2),从头结点数组中删除该顶点 ;
(3),删除与该顶点相关的边 ;
(4),修改有关的边结点的 adjvex 域的内容。
华电计算机系
North China Electric Power University
华电 计算机系
A
D
E
F
C
B
A
B
C
D
E
F
^
^
^
^
^
1
2
3
4
5
6
2 3 4 6
1 3 4
1 2 4 5
1 2 3 5
3 4 6
1 5
A
D
E
F
C
B
A
B
D
E
F
F
^
^
1
2
3
4
5
6
2 3 5
1 3
1 2 4
3 5
1 4
^
^
^
North China Electric Power University
procedure Del( g,n,item );
begin
k:=0;
for i:=1 to n do
if(g[i].vertex=item)then
[ k:=i; exit;]
if (k=0) then
return;
p:=g[k].link;
for i:=k+1 to n do
[ g[i-1].vertex:=g[i].vertex;
g[i-1].link:=g[i].link;
]
n:=n–1; // 顶点的个数减 1 //
while(p<>nil) do
[ q:=p;
p:=p?.next; dispose(q);
] 华电计算机系
for i:=1 to n do
[ p:=g[i].link;
while (p<>nil） do
if(p?.adjvex=k) then
[ if(g[i].link=p) then
g[i].link:=p?.next
else
q?.next:=p?.next;
r:=p;p:=p?.next;
dispose(r); ]
else
[ if (p?.adjvex>k) then
p?.adjvex:= p?.adjvex–1;
q:=p;
p:=p?.next;
]
]
end; 北航 计算机系
North China Electric Power University
从图中某个指定的顶点出发,按照某一原则对图中所有顶点都访问一次,得到一个由图中所有顶点组成的序列,这一过程称为图的遍历,
原则,
从图中某个指定的顶点 v出发,先访问顶点 v,然后从顶点 v 未被访问过的一个邻接点出发,继续进行深度优先遍历,直到图中与 v 相通的所有顶点都被访问 ;若此时图中还有未被访问过的顶点,则从另一个未被访问过的顶点出发重复上述过程,直到遍历全图,
一,深度优先搜索华电 计算机系
★ 图的遍历为了标记某一时刻图中哪些顶点是否被访问,定义一维数组 visited[1:n],有
1 表示 第 i个顶点已经被访问
visited[i] =
0 表示 第 i个顶点还未被访问
North China Electric Power University
North China Electric Power University
二,广度优先搜索华电 计算机系原则,
从图中某个指定的顶点 v出发,先访问顶点 v,然后依次访问顶点 v的各个未被访问过的邻接点,然后又从这些邻接点出发,按照同样的规则访问它们的那些未被访问过的邻接点，如此下去，直到图中与 v 相通的所有顶点都被访问 ;
若此时图中还有未被访问过的顶点,则从另一个未被访问过的顶点出发重复上述过程,直到遍历全图,
North China Electric Power University
可以用深度优先搜索或广度优先搜索算法来判断图是否连通。在对无向图进行遍历时，对于连通图，仅需要一次搜索过程，图中的顶点就全部被访问。对于非连通图，则需要多次调用搜索过程，而每次调用得到的顶点访问序列恰好为其各个连通分量中的顶点集。
三,求图的连通分量算法,procedure component(var g);
begin
for i:=1 to vnum do visited[i]:=0;count:=0;
for i:=1 to vnum do
if visited[I]=0 then [count:=count+1;dfs(g,i);]
end;
North China Electric Power University
★ 最小生成树和最短路径问题带权连通图中,总的权值之和最小的带权生成树为最小生成树,最小生成树也称最小代价生成树,或最小花费生成树,
构造网的最小生成树的依据：
1,在网中选择 n-1条边，连接网的 n个顶点；
2,尽可能选取权值为最小的边。
最小生成树的概念：
最小生成树问题
v4
v2
v6
v5
v3
v1 16
11 5
6
9
18
1419 22
20
最小生成树的权值 = 56
Kruskal算法：
1.设 T的初态为空集；
2.当 T中边数小于 n-1时做下列工作
①从 E中选取权值为最小的边 (v,w)，并删除之；
②若 (v,w)不和 T 中的边一起构成回路，则将边
(v,w)加入到 T中去。
1
2 4
65
3
6 5
3
6
2
1
5
4
6
5
1
2 4
65
3
① T为空
North China Electric Power University
1
2 4
65
3
② 选权值最小的边 (1,3)
从 E中将其删去
1
1
2 4
65
3
1
③ 选 E中最小的边 (4,6)从 E
中将其删去
2
1
2 4
65
3
1
2
④ 从 E中选最小的边 (2,5)
从 E中将其删去
3
1
2 4
65
3
1
23
⑤ 从 E中选最小的边 (3,6)从
E中将其删去
4
North China Electric Power University
⑥ 从 E中选最小的边 (3,4)，但加入
T后会使 T中出现回路，所以边 (3,4)
不可取，把边 (3,4)从 E中删除。再看 (1,4)同样会使 T构成回路，仍不可取，从 E中删去 (1,4)，选 (2,3)，
从 E中删去 (2,3),最后已够 5条边了，
这样生成树就是最小生成树。最小生成树可能不唯一，但权的总数相同。
2 4
65
3
1
23
4
1
5
算法的思想明确、也很简单，但具体实现时比较困难，需要解决一些具体的问题，譬如如何使所选的新边没有和已选的边构成回路。
算法讨论：
North China Electric Power University
Prim算法：
1.设 V(T)的初态为空集 (V(T)为落在生成树上的顶点集合 );
2.在连通图上任选一顶点加入到 V(T)集合中去；
3.将下列步骤重复 n-1次：
①在 i属于 V(T),j不属于 V(T)的边中，选权值最小的边
(i,j)；
②将顶点 j加入到 V(T)中去；
③输出 i,j及 Wij。
North China Electric Power University
例：①初态 V(T)=φ
② 选①顶点 =>V(T)=｛ 1｝
③做 n-1次
1)边 (1,2)的权值最小，
∴ 将② =>V(T)=｛ 1,2｝ ;
write(1,2)
weight 16
1 2
4
6
5
3
2)边 (2,3)的权值最小，
∴ 将③ =>V(T)=
｛ 1,2,3｝ ;
write(2,3)
weight 5
3)边 (3,4)的权值最小，
∴ 将④ =>V(T)=
｛ 1,2,3,4｝ ;
write(3,4)
weight 6
16
5
6
18
19
21 11
1433
6
North China Electric Power University
4)边 (2,6)的权值最小，
∴ 将⑥ =>V(T)=｛ 1,2,3,4,6｝ ;
write(2,6) weight 11
5)边 (4,5)的权值最小，
∴ 将⑤ =>V(T)=
｛ 1,2,3,4,5,6｝ ;
write(4,5) weight 18
∑ i=16 Weight = 56
1 2
4
6
5
3
16
5
6
18
19
21 11
1433
6
1 2
4
6
5
3
16
5
6
18
11
North China Electric Power University
最短路径问题一,路径长度的定义
1,不带权的图,路径上所经过的边的数目 。
2,带权的图,路径上所经过的边上的权值之和,
二,问题的提出三,解决问题所需要确定的数据结构
1,图的存储,以 1~n 分别代表 n个顶点,采用邻接矩阵存储该图,有
Wij 当顶点 vi 到顶点 vj 有边,且权为 Wij
A[i,j]=? 当顶点 vi 到顶点 vj无边时
0 当 vi=vj 时?
设出发顶点为 v(通常称为源点 )。
North China Electric Power University
2,设置一个标志数组 S[1:n]记录源点 v 到图中哪些顶点的最短路径已经找到，有：
1 表示源点到顶点 i 的最短路径已经找到
S[i] =
0 表示源点到顶点 i 的最短路径尚未找到初始时,S[v]=1,S[i]=0 i =1,2,?,n i?v
{
3,设置数组 dist[1:n] 分别记录源点 v 到图中各顶点的最短路径的路径长度,其中,dist[i]记录源点到顶点 i 的最短路径的长度；初始时,dist数组的值为邻接矩阵第 v 行的 n个元素值。
4,设置数组 path[1:n] 分别记录源点 v 到图中各顶点的最短路径所经过的顶点序列，其中,path[i]记录源点到顶点 i 的路径，初始时,path[i]=? v?,i =1,2,3,?,n
华电计算机系
0 1
3 52
4
45
50 10
20 10 15
15
20
3
35 30
v0是源点 最短路径
v0→v2 10
v0→v2→v3 10+15=25
v0→v2→v3→v1 10+15+20
v0→v4 45
v0→v5 无路可走从以上可以发现每一条最短路径中间所经过的顶点具有如下特点：下一条最短路径 (设其终点为 x)可能是 <v0,x>,或者
<v0,u,…,v,x>，而 u,…,v都是已求得的最短路径终点。
例假设 S为已求得的最短路径的终点的集合 (S初态为空集 )，则下一条长度次短的最短路径（设终点为 x）：
或者是弧 <v0,x>；
或者是中间经过 S集合中顶点，最后到达顶点 x的路径。
Dijkstra算法思想：
North China Electric Power University
4.算法 (用自然语言表达 )
1,确定 dist,S,path 三个数组的初值。
2,利用 S数组与 dist 数组在那些尚未找到最短路径的顶点中确定一个与源点最近的顶点 u,并置 S[u]为 1，同时将顶点
u加入 path[u].
3,根据顶点 u修改源点到所有尚未找到最短路径的顶点的路径长度。 即
1） 将源点 v到顶点 u的 (最短 )路径长度分别加到源点 v
通过顶点 u可以直接到达、且尚未找到最短路径的那些顶点的路径长度上 ;若加后的长度小于原来 v 到某顶点 r的路径长度，则用加后的长度替代原来的长度，否则不替代。
2）若替代，将源点 v 到顶点 u 的路径 (最短路径 )上经过的所有顶点替换 path[r].
4,重复第 2 至第 3 步 n-1 次。
for i?1 to n do
dist[i]?cost[v,i]
end
S[i]?0
S[v]?1
path[i]?{ v }
北航计算机系
North China Electric Power University
Floyed算法思想：
从 i 到 j的路径上每次增加一个结点 k，看这个增加了一个结点 k的新路径的长度是否比原来的路径长度小，若小,则以新路径代之,否则保持原路径。
A(k)[i,j]=min{A(k-1)[i,j],A(k-1)[i,k]+A(k-1)[k,j]} (1≤k≤n)
算法计算公式：
其中,
A(k)[i,j]表示顶点 i,j之间的中间点的序号不大于 k的最短距离 ;
由于 G中顶点编号不大于 n，所以最后到了 An[i,j]就代表
i到 j的最短路径之长。
North China Electric Power University
算法描述：
procedure all_path(cost);
Begin
for i:=1 to n do
for j:=1 to n do
[ a[i,j]:=cost[i,j];
if(i<>j)and(a[i,j]<max) then
path[i,j]=[i]+[j]
]
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if a[i,k]+a[k,j]<a[i,j] then
[ a[i,j]:=a[i,k]+a[k,j];
path[i,j]:=path[i,k]+path[k,j];
]
End;
North China Electric Power University
cost=
0 4 11
6 0 2
3 ∞ 0
cost:带权邻接矩阵
A：最短路径长度
P：相应的路径例,6
4
11
3 2
A B
C
3
21
初态 K=0时，
A(0) 1 2 3
1
2
3
0 4 11
6 0 2
3 ∞ 0
AB AC
Path(0) 1 2 3
1
2
3
BA BC
CA
North China Electric Power University
K=1时，
A(1) 1 2 3 Path(1) 1 2 3
1 0 4 11 1 AB AC
2 6 0 2 2 BA BC
3 3 7 0 3 CA CAB
K=2时，
A(2) 1 2 3 Path(2) 1 2 3
1 0 4 6 1 AB ABC
2 6 0 2 2 BA BC
3 3 7 0 3 CA CAB
North China Electric Power University
K=3时，
A(3) 1 2 3 Path(3) 1 2 3
1 0 4 6 1 AB ABC
2 5 0 2 2 BCA BC
3 3 7 0 3 CA CAB
North China Electric Power University
★ AOV网与拓扑排序一,什么是 AOV网验收筹备招标备料进驻工地测量 挖地基浇注水泥搭架子
…
例 1
North China Electric Power University
华电 计算机系程序语言数据结构离散数学软件工程操作系统编译原理数据库计算机组成汇编网络数字逻辑计算机导论例 2
North China Electric Power University
华电计算机系二,AOV网的定义在 AOV网中，若顶点 i 到顶点 j 之间有有向路径，
则称顶点 i 为顶点 j 的前驱，顶点 j 为顶点 i的后继；若顶点 i 到顶点 j 之间为一条有向边，则称顶点 i 为顶点 j
的直接前驱，顶点 j 为顶点 i 的直接后继。
以顶点表示活动，以有向边表示活动之间的优先关系的有向图称为 AOV网。
North China Electric Power University
三,拓扑排序检查 AOV网是否存在回路的方法是对 AOV网进行拓扑排序，构造一个序列，使得该序列满足条件：
1,若在 AOV网中，顶点 i 优先于顶点 j,则在该序列中也是顶点 i 优先于顶点 j 。
2,若在 AOV网中,顶点 i 与顶点 j之间不存在优先关系,则在该序列中建立它们的优先关系，即顶点 i
优先于顶点 j，或顶点 j 优先于顶点 i 。
3,若能够构造出拓扑序列，则拓扑序列包含 AOV
网的全部顶点。
North China Electric Power University
四,拓扑排序方法
1,从 AOV网中任选择一个没有前驱 (入度为 0)的顶点 ；
2,从 AOV网中去掉该顶点以及以该顶点为出发点的所有边；
3,重复上述过程，直到网中的所有顶点都被去掉,或者网中还有顶点，但不存在入度为 0 的顶点；
前者说明 AOV网中无回路，
后者说明 AOV网中存在回路。
North China Electric Power University
v1
v4
v3
v2
v6
v5
v7
v1 v5 v7v3v6 v2 v4
例华电计算机系
v4
v3
v2
v6
v7
v4
v3
v2
v6
v5
v7
v4
v3
v2
v7
v4
v3 v7
v4
v7 v7
North China Electric Power University
★ AOE网与关键路径筹备付款签合同做预置件验收施工
…
招标
7天联系材料
8天图纸设计
15天进驻工地
4天运材料
6天搬运
3
天例
North China Electric Power University
一,AOE网的定义
AOE网为一个带权的有向无环图，其中，顶点表示事件，有向边表示活动，边上的权值表示活动持续的时间。
v1
v4
v2
v3
v5
v7
v9
v8
v6
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
6
4
5
1
1
2
9
7
2
4
4
正常情况下,AOE网中只有一个入度为 0 的顶点，称之为 源点 ；有一个出度为 0 的顶点，称之为 终点 。
North China Electric Power University
1.只有在某个顶点所代表的事件发生以后,该顶点引发的活动才能开始。
2.进入某事件的所有边所代表的活动都已完成,该顶点所代表的事件才能发生。
AOE网的特点,
1,关键路径的定义从源点到终点的路径中具有最大路径长度的路径为关键路径 ; 关键路径上的活动称为关键活动。
二,AOE网的存储方法三,关键路径采用邻接矩阵存储方法。
North China Electric Power University
2,关键路径的特点
1) 关键路径的长度 (路径上的边的权值之和 )为完成整个工程所需要的最短时间。
2) 关键路径的长度变化 (即任意关键活动的权值变化 )
将影响整个工程的进度，而其他非关键活动在一定范围内的变化不会影响工期。
求关键活动的思路：
e(i) — 活动 ai 的最早开始时间
l(i) — 活动 ai 的最迟开始时间若 l(i)–a(i)=0，则说明活动 ai 为一个关键活动。
Ve(k) — 事件 k 的最早发生时间 k ai
Vl(k) — 事件 k 的最迟发生时间 ai k
North China Electric Power University
事件 k的最早发生时间 ee(k)
事件 k的最迟发生时间 le(k)
活动的 ai 最早开始时间 e(i)
活动的 ai 最迟开始时间 l(i)
求 e(i) = l(i)
结论
1,计算事件 k的最早发生时间 Ve(k)
所谓事件 k的最早发生时间 Ve(k)是指从源点到顶点 k
的最大路径长度,
计算方法,
Ve(1) = 0
Ve(k) = Max{ Ve(j) + <j,k>的权 }
<j,k>?P( j )
四,求关键路径
k
North China Electric Power University
华电 计算机系
2,计算事件 k的最迟发生时间 Vl(k)
所谓事件 k 的最晚发生时间 Vl(k)是指不影响整个工期的前提下事件 k 必须发生的最晚时间。
计算方法,
Vl(n) = Ve(n)
Vl(k) = Min{ Vl(j) – <k,j>的权 }
<k,j>?S(k)
k
North China Electric Power University
3,计算活动 i的最早开始时间 e(i)
所谓活动 i 的最早开始时间 e(i) 是事件 k发生的最早时间，即只有事件 k 发生了，活动 i 才能开始。
活动 ik j
计算方法,e(i) = Ve(k)
4,计算活动 i 的最迟开始时间 l(i)
所谓活动 i 的最迟开始时间 l(i) 是指不推迟整个工期的前提下活动 i 开始的最晚时间。
计算方法,l(i) = le(j) -<k,j>的权活动 ik j
North China Electric Power University
5,求出关键活动与关键路径计算方法,l(i) = e(i)
1 2 3 4 5 6 7 8 9 10 11
l(i),0 2 3 6 6 8 7 7 10 16 14
1 2 3 4 5 6 7 8 9 10 11
e(i),0 0 0 6 4 5 7 7 7 16 140
0
a1 a7a4 a10a8 a11
6
6 7
7
7
7
16
16 14
v1
v4
v2
v3
v5
v7
v9
v8
v6
a1
a2
a3
a4
a5
a6
a7
a8
a9
a10
a11
6
4
5
1
1
2
9
7
2
4
4
关键路径的长度为 18个时间单位 。
North China Electric Power University
