图习题讲解.pdf

2010年6月8日星期二1 数据结构 图习题讲解数据结构 图习题讲解 Data Structure 主讲教师 骆嘉伟主讲教师 骆嘉伟 Office number 计通院606计通院606 E mail luojiawei 2010年6月8日星期二2 1 对下面无向带权图1 对下面无向带权图 1 写出它的邻接矩阵 并按普利姆算法求其最小生成树 1 写出它的邻接矩阵 并按普利姆算法求其最小生成树 2 写出它的邻接表 并按克鲁斯卡尔算法求其最小生成 树 2 写出它的邻接表 并按克鲁斯卡尔算法求其最小生成 树 图习题讲解图习题讲解 2010年6月8日星期二3 图习题讲解图习题讲解 答 1 邻接矩阵为 注 在有权图中 除去权值部分 邻接矩阵的其他值 都是 答 1 邻接矩阵为 注 在有权图中 除去权值部分 邻接矩阵的其他值 都是 43 4559 3555 557654 973 632 526 546 2010年6月8日星期二4 图习题讲解图习题讲解 以a为起始点由prim算法求得的最小生成树为 不唯一 以a为起始点由prim算法求得的最小生成树为 不唯一 a h g f e d c b 4 5 4 5 3 2 a h g f e d c b 4 3 2010年6月8日星期二5 图习题讲解图习题讲解 2 邻接表为 2010年6月8日星期二6 图习题讲解图习题讲解 由Kruskal算法求得的最小生成树为 不唯一 由Kruskal算法求得的最小生成树为 不唯一 a h g f e d c b 4 5 4 5 3 3 2 a h g f e d c b 4 4 3 3 2 a h g f e d c b 4 3 3 2 2010年6月8日星期二7 图习题讲解图习题讲解 2 对下图所示的AOE网络 计算各活动弧的e a 2 对下图所示的AOE网络 计算各活动弧的e ai i 和l a 和l aj j 函数值 各事件 顶点 的 ve v 函数值 各事件 顶点 的 ve vi i 和vl v 和vl vj j 的函数值 列出各关键路径 的函数值 列出各关键路径 2010年6月8日星期二8 图习题讲解图习题讲解 各个事件的最早发生时 间和最迟发生时间 各个事件的最早发生时 间和最迟发生时间 VeVl 00 A120 B624 C1726 D319 E3434 F48 G33 H1313 I17 J3131 K2222 4444 2010年6月8日星期二9 图习题讲解图习题讲解 各个活动的最 早发生时间和最 迟开始时间 各个活动的最 早发生时间和最 迟开始时间 e ai l aj l aj e ai A 01919 B 01818 D 01616 F 044 G 000 I 066 C 12019 C 62418 C 31916 E 32623 E 42319 J 32522 2010年6月8日星期二10 图习题讲解图习题讲解 各个活动的最早发生时 间和最迟开始时间 各个活动的最早发生时 间和最迟开始时间 综上可得关键路径为 综上可得关键路径为 G H e ai l aj l aj e ai H 484 G 32320 H 330 C 13229 176 17269 132714 13130 22220 31310 31321 34340 2010年6月8日星期二11 图习题讲解图习题讲解 3 试利用Dijkstra算法求下图中从顶点a 到其他各顶点间 的最短路径 写出执行算法过程中各步的状态 3 试利用Dijkstra算法求下图中从顶点a 到其他各顶点间 的最短路径 写出执行算法过程中各步的状态 2010年6月8日星期二12 图习题讲解图习题讲解 答 i 1i 2i 3i 4i 5i 6 a b15 a b 15 a b 15 a b 15 a b 15 a b 15 a b c2 a c d12 a d 12 a d 11 a c f d 11 a c f d e 10 a c e 10 a c e f 6 a c f g 16 a c f g 16 a c f g 14 a c f d g S a c a c f a c f e a c f e d a c f e d g a c f e d g b 2010年6月8日星期二13 4 试基于图的深度优先搜索策略写一个算法 判别 以邻接表方式存储的有向图中是否存在由顶点 v 4 试基于图的深度优先搜索策略写一个算法 判别 以邻接表方式存储的有向图中是否存在由顶点 vi i 到顶点v到顶点vj j的路径 i j 注意算法中涉及的图 的基本操作必须在此存储结构上实现 的路径 i j 注意算法中涉及的图 的基本操作必须在此存储结构上实现 图习题讲解图习题讲解 2010年6月8日星期二14 图习题讲解图习题讲解 int visited MAXSIZE 指示顶点是否已访问指示顶点是否已访问 int exist path DFS ALGraph G int i int j 深度优先判断有向图深度优先判断有向图G中顶点中顶点i 到顶点到顶点j是否有路径是否有路径 是则返回是则返回1 否则返回否则返回0 if i j return 1 i就是就是j else visited i 1 for p G vertices i firstarc p p p nextarc k p adjvex if visited k i下游的顶点到下游的顶点到j 有路径有路径 for else exist path DFS 2010年6月8日星期二15 图习题讲解图习题讲解 5 以邻接表作存储结构实现求从源点到其余各顶点的最短路径的 Dijkstra 算法 5 以邻接表作存储结构实现求从源点到其余各顶点的最短路径的 Dijkstra 算法 void ALGraph DIJ ALGraph G int v0 Pathmatrix vnextarc D p adjvex p info 给给D数组赋初值数组赋初值 for v 0 v G vexnum v final v 0 for w 0 w G vexnum w P v w 0 设空路径设空路径 if D v INFINITY P v v0 1 P v v 1 for 2010年6月8日星期二16 图习题讲解图习题讲解 D v0 0 final v0 1 初始化初始化 for i 1 i G vexnum i min INFINITY for w 0 w G vexnum w if final w if D w nextarc w p adjvex if final w P w P v P w w 1 构造最短路径构造最短路径 for for ALGraph DIJ 分析 本算法对迪杰斯特拉算法中 直接取任意边长度的语句作了修改 由于在原算法中 每次循环都是对 尾相