内容发布更新时间 : 2024/12/25 14:49:58星期一 下面是文章的全部内容请认真阅读。
数据结构教案
第七章 图
数据结构教案 第7章 图
第7章 图
【学习目标】
1．领会图的类型定义。
2．熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。 3．熟练掌握图的两种遍历算法。 4．理解各种图的应用问题的算法。 【重点和难点】
图的应用极为广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于理解各种图的算法及其应用场合。 【知识点】
图的类型定义、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍历、无向网的最小生成树、最短路径、拓扑排序、关键路径 【学习指南】
离散数学中的图论是专门研究图性质的一个数学分支，但图论注重研究图的纯数学性质，而数据结构中对图的讨论则侧重于在计算机中如何表示图以及如何实现图的操作和应用等。图是较线性表和树更为复杂的数据结构，因此和线性表、树不同，虽然在遍历图的同时可以对顶点或弧进行各种操作，但更多图的应用问题如求最小生成树和最短路径等在图论的研究中都早已有了特定算法，在本章中主要是介绍它们在计算机中的具体实现。这些算法乍一看都比较难，应多对照具体图例的存储结构进行学习。而图遍历的两种搜索路径和树遍历的两种搜索路径极为相似，应将两者的算法对照学习以便提高学习的效益。 【课前思考】
1. 你有没有发现现在的十字路口的交通灯已从过去的一对改为三对，即每个方向的直行、左拐和右拐能否通行都有相应的交通灯指明。你能否对某个丁字路口的6条通路画出和第一章绪论中介绍的\五叉路口交通管理示意图\相类似的图？
2. 如果每次让三条路同时通行，那么从图看出哪些路可以同时通行？ 同时可通行的路为：(AB,BC,CA),(AB,BC,BA),(AB,AC,CA),(CB,CA,BC)
数据结构教案 第7章 图
目 录
第7章 图 .............................................................................................................................................. 1
7.1 图的定义和基本术语 ............................................................................................................. 1 7.2 图的存储和创建 ..................................................................................................................... 2
7.2.1 图的存储表示 .............................................................................................................. 2 7.2.2 图的创建 ...................................................................................................................... 4 7.3 图的遍历 ................................................................................................................................. 5
7.3.1 深度优先搜索 .............................................................................................................. 5 7.3.2 广度优先搜索 .............................................................................................................. 6 7.4 遍历算法的应用 ..................................................................................................................... 7
7.4.1 应用问题概述 .............................................................................................................. 7 7.4.2 求一条包含图中所有顶点的简单路径....................................................................... 8 7.4.3 求距v0的各顶点中最短路径长度最长的一个顶点 ................................................. 9 7.5 图的连通性问题 ................................................................................................................... 10
7.5.1 无向图的连通分量和生成树 .................................................................................... 10 7.5.2 最小生成树 ................................................................................................................ 12 7.6 有向无环图及其应用 ........................................................................................................... 12