数据结构课件-第08章.pptx

数据结构计算机领域本科教育教学改革试点工作计划（“101计划”）研究成果101俞勇、张铭、陈越、韩文弢上海交通大学、北京大学、浙江大学、清华大学

图应用第8章李荣华北京理工大学

8.1问题引入8.2最短路径问题8.3最小生成树8.4拓扑排序和关键路径8.5拓展延伸8.6应用场景：图计算

8.1问题引入：魔方问题8.1问题引入数据结构问题：在一个3阶魔方中，魔方的每一个面都由9个方块（3×3）构成。魔方处在初始形态时，每个面的方块都是同一种颜色，魔方的六个面一共包含蓝、红、橙、绿、黄、白六种颜色。将魔方的各面随机旋转几次，如何它通过最少的旋转还原到魔方的初始形态，即各个面的方块颜色一样呢？关键：如何将该问题转化为一个图问题？核心思想：将魔方的任意一个形态建模为图中的一个顶点。如果魔方的两个形态可以通过魔方一个面的一次旋转相互转化，那么就将相应的两个顶点连成一条边。这样可以得到一个魔方形态的转移图。从一个打乱的魔方还原至初始形态可以转化为在该转移图上寻找一条从打乱状态所对应顶点到初始形态所对应顶点的路径问题。而这两个顶点之间的最短路径即为最优的旋转方案。

8.2最短路径问题8.2最短路径问题数据结构?交通网络示意图

8.2最短路径问题数据结构?最短路径最优子结构示意图

8.2最短路径问题数据结构?权值为负的环路

8.2最短路径问题数据结构?

Dijkstra算法8.2最短路径问题数据结构?有向加权图G源点终点最短路径路径长度v1v2v1,v21v1v3v1,v2,v4,v38v1v4v1,v2,v44v1v5v1,v2,v4,v3,v513v1v6v1,v2,v4,v3,v5,v617

8.2最短路径问题数据结构有向加权图G源点终点最短路径路径长度v1v2v1,v21v1v3v1,v312v1v4/maxv1v5/maxv1v6/max

8.2最短路径问题数据结构源点终点最短路径路径长度v1v2v1,v21v1v3v1,v2,v310v1v4v1,v2,v44v1v5/maxv1v6/max有向加权图G

8.2最短路径问题数据结构源点终点最短路径路径长度v1v2v1,v21v1v3v1,v2,v4,v38v1v4v1,v2,v44v1v5v1,v2,v4,v517v1v6v1,v2,v4,v619有向加权图G

8.2最短路径问题数据结构源点终点最短路径路径长度v1v2v1,v21v1v3v1,v2,v4,v38v1v4v1,v2,v44v1v5v1,v2,v4,v3,v513v1v6v1,v2,v4,v619有向加权图G

8.2最短路径问题数据结构源点终点最短路径路径长度v1v2v1,v21v1v3v1,v2,v4,v38v1v4v1,v2,v44v1v5v1,v2,v4,v3,v513v1v6v1,v2,v4,v3,v5,v617有向加权图G

8.2最短路径问题数据结构?

Bellman-Ford算法8.2最短路径问题数据结构?

Bellman-Ford算法8.2最短路径问题数据结构?

8.2最短路径问题数据结构Bellman-Ford算法的执行过程示意图

Floyd-Warshall算法8.2最短路径问题数据结构?

8.2最短路径问题数据结构DD(-1)D(0)D(1)D(2)012012012012006220622061806181∞012∞012∞0121701225170511051105110PP(-1)P(0)P(1)P(2)0120120120120v0v1v0v2v0v1v0v2v0v1v0v1v2v0v1v0v1v21v1v2v1v2v1v2v1v2v0v1v22v2v0v2v1v2v0v2v0v1v2v0v2v0v1v2v0v2v0v1

8.2最短路径问题数据结构

8.3最小生成树8.3最小生成树数据结构?

Prim算法8.3最小生成树数据结构?最小生成树包含最短跨域边示意图

8.3最小生成树数据结构Prim算法执行过程

8.3最小生成树数据结构?

Kruskal算法8.3最小生成树数据结构?

8.3最小生成树数据结构Kruskal算法执行过程

8.4.1拓扑排序：问题引入8.4拓扑排序和关键路径数据结构问题：普通高等学校计算机专业本科生的课程安排，某些课程存在先修课，如何确定一个合理的课程学习顺序？关键：课程学习顺序需要遵循课程之间的先修关系课程先修关系：课程名称课程代码先修课程微积分C0无线性代数C1无概率论与数理统计C2C0，C1程序设计基础C3无数据结构C4C0，C1，C3计算机组成原理C5C4操作系统C6C4计算机体系结构C7C5

问题建模8.4拓扑排