数据结构之图-精.ppt

第六章回顾
树的定义和基本术语
子树孩子叶子兄弟度……
二叉树的性质
2k-1 2k-1 n0=n2+1 [log2n]+1
i的双亲[i/2]; 2i>n, i无左孩子;2i+1>n, i无右孩子
二叉树的存储结构
二叉链表、三叉链表
二叉树的遍历
先序遍历、中序遍历、后序遍历
线索二叉树
在二叉链表的基础上增加两个标志域,表示按某种次序遍历时的前驱和后继
树的三种存储结构
双亲表示法
孩子链表表示法
孩子兄弟表示法
森林和二叉树的转换
由森林转换为二叉树
由二叉树转换为森林
树和森林的遍历
树的先根遍历(= 二叉树的先序遍历)
树的后根遍历(= 二叉树的中序遍历)
森林的先序遍历(= 二叉树的先序遍历)
森林的中序遍历(= 二叉树的中序遍历)
赫夫曼树和赫夫曼编码
课前思考
1、如何确定一项工程的工期?最佳工期如何计算?(关键路径问题)
2、如何以最低造价架构城市之间的通信网?几个小区之间要建一个供水站,建在什么位置最合适?(最小生成树问题)
3、如何合理安排大一到大四的教学计划?(拓扑排序问题)
4、从上海到北京怎么走最省时间或金钱?如何花费最少周游所有城市? (最短路径问题)
课前导学
图的定义和术语
图的存储结构
图的遍历
图的连通性问题
有向无环图及其应用
最短路径
知识点小结
第七章图
例
北京
上海
南京
济南
徐州
280
500
320
180
160
600
260
200
青岛
连
200
【学****目标】
。 ,
了解各种存储结构的特点及其选用原则。 。 。
【重点和难点】
理解各种图的算法及其应用场合。 
【知识点】 图的类型定义、图的存储表示、图的深度优先搜索遍历和广度优先搜索遍历、无向网的最小生成树、最短路径、拓扑排序、关键路径
【学****指南】
数据结构中对图的讨论侧重于在计算机中如何表示图以及如何实现图的操作和应用等。图是较线性表和树更为复杂的数据结构,因此和线性表、树不同,虽然在遍历图的同时可以对顶点或弧进行各种操作,但更多图的应用问题如求最小生成树和最短路径等在图论的研究中都早已有了特定算法,在本章中主要是介绍它们在计算机中的具体实现,应多对照具体图例的存储结构进行学****而图遍历的两种搜索路径和树遍历的两种搜索路径极为相似,应将两者的算法对照学****br/> 图的定义和术语
1. 基本定义和术语
图(Graph)——图G是由两个集合V(G)和E(G)组成的,记为G=(V,E),其中:V(G)是顶点(Vertex)的非空有限集E(G)是边(Edge)的有限集合,边是顶点的无序对(即:无方向的,(v0,v2))或有序对(即:有方向的,<v0,v2>)。
V0
0
0
1
V1
1
V2
2
2
4
3
V3
V0
V2
V1
V3
有向图(Digraph)——
有向图G是由两个集合V(G)和E(G)组成的,其中:V(G)是顶点的非空有限集,E(G)是有向边(也称弧)的有限集合,弧是顶点的有序对,记为<v,w>,v,w是顶点,v为弧尾,w为弧头
例
2
4
5
1
3
6
G1
图G1中:V(G1)={1,2,3,4,5,6}
E(G1)={<1,2>, <2,1>, <2,3>, <2,4>, <3,5>, <5,6>, <6,3>}