Document

Report
预习内容和重点



拓扑排序(能说出拓扑排序的算法思想、
能根据要求写出拓扑排序的序列、理解
拓扑排序的算法实现)
关键路径(相关概念、掌握关键路径的
算法思想、能求出关键路径)
最短路径(能说出Dijkstra求解最短路
径的算法思想、理解Dijkstra求解最短
路径的算法实现)
回答问题1
什么是有向无环图(DAG)?下图是不是
DAG?有向无环图有何用途?
A
B
C
D
G1
回答问题2
假设以有向图表示一个工程的施工图或程
序的流程图,则程序中能否出现回路?
回答问题3
如何检查有向图中是否存在回路?
A
B
C8
C9
C1
C7
C3
C4
C
D
G1
C2
C6
C5
回答问题4
何谓拓扑排序?
V2
V1
V4
V1
V2 V3
V4
V3
换句话说:对有向图进行如下操作,按照
有向图给出的次序关系,将图中的顶点排成一
个线性序列,对于没有限定次序关系的顶点,
则可以人为加上任意的次序关系。
回答问题5
如何进行拓扑排序?
A
B
C8
C9
C1
C7
C3
C4
C2
C
D
C6
C5
G1
检测一个有向图是否存在回路的方法:对有向图构
造其顶点的拓扑有序序列,若图中所有顶点都在它的拓
扑有序序列中,则该图中必定不存在环。
回答问题6
有向图的拓扑有序序列是否唯一?
C8
C9
C1
C7
C3
C4
C2
C6
C5
回答问题7
如何在计算机内实现有向图的拓扑排序?
分析:
(1)拓扑排序最关键的操作是什么?
(2)图的存储结构?
(3)如何处理多个入度为0的顶点?
拓扑排序算法实现
实现拓扑排序的算法基础
存贮结构:假设有向图以邻接表的形式存储
操作过程:
将所有入度为0的顶点入栈;
当栈非空时重复执行下列操作:
从栈中退出顶点k;
(1)将k顶点的信息输出;
(2)将与k邻接的所有顶点的入度减1。
回答问题8
对课本中的拓扑排序实现算法还可怎么改
变?
回答问题9
按照课本中的拓扑排序实现算法,写出下图的拓
扑有序序列。
degree data adj vex link
C0
1
3 0
1
C1
5
3
C2
1
5 0
0
C3 0
1
0
1
5 0
C4
0
C5 0
C0
C1
C2
3
C3
C4
C5
回答问题10
拓扑排序算法的时间复杂度是多少?
如果给定的有向图有n个顶点和e条边,那
么求各顶点入度的时间为O(e),在拓
扑排序的过程中,查找入度为零的顶点
的时间为O(n),顶点进栈及退栈输出
共执行n次,入度减1的操作执行e次,
所以,总的执行时间为O(n+e)。
回答问题11
什么是AOV网?
C8
C9
C1
C7
C3
C4
C2
C6
C5
回答问题12
什么是AOE网? 有什么用?
回答问题13
什么是源点、 汇点、 关键路径、
关键活动?
v1
6
v0
源点
1
4
5
v3
1
8
v4
v6
4
v7
2
4
v5
2
v8
7
v2
汇点
回答问题14
如何求关键路径?如何求关键活动?
2
a1=3
5
a8=1
a3=2
1
a2=2
a4=3
4
a7=2
a5=4
a6=3
3
6
顶点 Ve
V1
活动
e
l
1-e
V1
0
0
a1
0
1
1
V2
3
4
a2
0
0
0
V3
2
2
a3
3
4
1
V4
6
6
a4
3
4
1
V5
6
7
a5
2
2
0
V6
8
8
a6
2
5
3
a7
6
6
0
a8
6
7
1
正推 倒推
根据上表,l[s]-e[s]等于0的活动有
a2,a5,a7,因此a2,a5,a7为关键活动。
回答问题15
如何做才能真正缩短工期?
用AOE网来估算某些工程的时间是非常有用的,关
键活动的速度的提高是有限的,只有在不改变网
的关键路径的前提下,提高关键活动的效率才有
效,关键活动受诸多方面的影响,如果某个条件
改变可,可能会改变关键活动.
如果网中有多条关键路径,要提高整个工期的速
度,则要同时提高在几条关键路径上的活动的效
率.
回答问题16
如果从图中某一顶点(称为源点)到达另一
顶点(称为终点)的路径可能不止一条,如何找到
一条路径使得沿此路径上各边上的权值总和达到
最小?如下图从顶点V1到V7的最短路径是?
15
9
v1
4
v3
6
12
v2
5
v4
8
v5
3
11
v6
2
v7
回答问题17

迪杰斯特拉算法的算法思想是什么?
可求出从某个源点到其余各顶点的最短路径
按路径长度递增的次序产生最短路径.即
首先求出长度最短的一条最短路径,再参照
它求出长度次短的一条最短路径,依次类推,
直到从顶点v到其它各顶点的最短路径全部
求出为止.
回答问题18
按照迪杰斯特拉算法求出从顶点V0到其他各顶点的
最短路径?
V0
8
30
32
13
V1
V2
5
V3
6
V4
9
2
V5
7
V6
17
最短路径
<V0,V2>
<V0,V1>
<V0,V2,V3>
<V0,V2,V3,V4>
<V0,V1,V6>
长度
8
13
13
19
20
<V0,V2,V3,V4,V5> 21
回答问题18
如何实现迪杰斯特拉算法?
首先引入一个辅助向量D,它的分量D[i]表示当前
所有找到的从始点V到每个终点Vi的最短路径的长度。
其初态为:若从V到Vi有弧,则D[i]为弧上的权值,否
则为无穷大;显然,长度为
D[j]=Min{D[i]| Vi V}
的路径是从V出发的最短一条路径,此路径为(V, Vj )。
下一条次短的路径可通过下面的算法求得:
设次短路径的终点是Vk ,则这条路径或者是(V,
Vk ) ,或者是(V, Vj, Vk ) 。其长度或者是从V到Vk的
弧上的权值,或者是D(j)和从Vj到Vk的弧上的权值之
和。
二、算法描述:
1、用邻接矩阵arcs表示带权有向图,
arcs[i][j]表示弧< Vi ,Vj>上的权值。若弧不
存在,则置为无穷大。S为已找到从V出发的
最短路径的终点的集合,它的初始状态为空集。
那么,从V出发到图上其余各顶点(终点)Vi
可能达到的最短路径长度的初值为:
D[i]=arcs[V的序号,i]
Vi V
2、选择Vj使得,
D(j)=Min{D[i] | ViV- S}
Vj就是当前求得得一条从V出发得的最短路径
的终点。令
S=S{j}
3、修改从V出发到到集合V-S上任一顶点Vk 可达
到的最短路径长度。如果:
D(j)+ arcs[j][k]< D[k]
则修改D[k]为
D[k]= D[j]+ arcs[j][k]
4、重复2,3步共n-1次。由此求得从V到图上其余
顶点得最短路径是依路径长度递增的序列。
例:有向图如下图,求V0到其它各顶点的最短路径。
解: 根据上面的算法,其求解过程如下表所示。
终点
5
60
100
0
30
10
4
10 20
1
3
5
50
2
从V0到各终点的弧值和最短路径
V1

V2
10
(V0,V2)



60
50
(V0,V2,V3)(V0,V4,V3)
30
30
V4
(V0,V4) (V0,V4)
100
100
90
60
V5
(V0,V5) (V0,V5) (V0,V4,V5)(V0,V4,V3 ,V5)
V3

Vj
V2
V4
V3
V5
第八章
最短路径
有向图的应用
应用
小结
Dijkstra算法
Floyd算法
拓扑排序
DAG图
关键路径
存储结构
图
遍
历
邻接矩阵
邻 接 表
十字链表
邻接多重表
深度优先搜索
广度优先搜索
图的连通分量 (利用DFS)
无向图的应用
图的生成树
最小生成树
Prim算法
Kruskal算法
下节课学习内容和重点

查找(相关概念、理解各种静态查找表
查找方法、掌握顺序表查找、折半查找
的实现算法及其性能分析)

similar documents