数据结构教学课件.ppt

5、二叉树是结构最简单的一种树结构，可以和树、森林进行相互转换。7、二叉排序树是左子树上所有结点的值均小于根结点的值，右子树上所有结点的值均大于根结点的值。中序遍历二叉排序树可得到一个关键字的有序序列。6、哈夫曼（Haffman）树，也称最优二叉树，是指对于一组带有确定权值的叶子结点，构造的具有最小带权路径长度的二叉树。要掌握其构造方法。第六章图数据结构目录4123图的定义及其常用术语图的存储结构图的遍历生成树和最小生成树5图的应用第六章图总体要求了解图的定义和术语掌握图的两种存储结构极其构造算法；重点掌握图的两种遍历算法；了解图的连通性问题极其判断；了解有向无环图极其应用（拓扑排序和关键路径）了解最短路径问题的解决方法。6.1图的定义及其常用术语6.1.1图的定义在图中的数据元素通常称为顶点，图（Graph）是由顶点集合（Vertex）及顶点之间的关系集合（Edge）组成的一种数据结构。记为G=（V，E）。无向图有向图G1=(V1,E1)其中V1=｛A,B,C,D,E｝E1=｛(A,D),(B,C),(B,D),(B,E),(D,E)｝G2=(V2,E2)其中V2=｛A,B,C,D｝E2=｛A,B,A,C,D,A,D,B｝6.1.2图的常用术语及含义1．有向图和无向图在图中，根据顶点之间的关系是否有方向性可将图分为有向图和无向图。对于无向图，顶点的关系为无向边，用圆括号表示，如（x，y）。对于有向图来说，顶点间的关系称为有向边，用尖括号表示，如x，y。没有方向性，（x，y）和（y，x）是等价的，是同一条边。表示从顶点x发向顶点y的边，x为始点，y为终点。2．完全图、稠密图、稀疏图、网无向图中边的取值范围：0≤e≤n(n-1)/2。（用n表示图中顶点数目，用e表示边的数目。且不考虑顶点到其自身的边。）完全图：有n(n-1)/2条边的无向图（即：每两个顶点之间都存在着一条边)称为完全图。v2v1v3v4v5有向图中弧的取值范围：0≤e≤n(n-1)。（用n表示图中顶点数目，用e表示弧的数目。且不考虑顶点到其自身的弧。）有向完全图：有n(n-1)条弧的有向图（即：每两个顶点之间都存在着方向相反的两条弧）称为有向完全图。v2v1v3v4稀疏图：含有很少条边或弧的图。稠密图：含有很多条边或弧的接近完全图的图。权：与图的边或弧相关的数，权值可以是距离，时间，价格等。网：带权的图。成都12000（流动人口）15000（流动人口成都2039（距离）北京北京3．子图若有两个图G1和G2，其中G1=(V1，E1)，G2=(V2，E2)，且满足如下条件：V2?V1,E2?E1即V2为V1的子集，E2为E1的子集，则称图G2为图G1的子图。（a）图G（b）图G的两个子图4．邻接点和度对于无向图，假若顶点v和顶点w之间存在一条边，则称顶点v和w互为邻接点。和顶点v关联的边的数目定义为v的度。记为TD(V)。TD（A）=2TD（B）=3TD（D）=?TD（E）=?对于有向图，由于弧有方向性，则有入度和出度之分。顶点的出度是以顶点v为弧尾的弧的数目，记为OD(V)。顶点的入度是以顶点v为弧头的弧的数目，记为ID(V)。OD(B)=1，ID(B)=2TD(B)=OD(B)+ID(B)=3试求顶点A的入度、出度和度。5．路径、简单路径、简单回路路径长度：图中两个顶点之间的路径为两个顶点之间的顶点序列，路径上所含边的数目。简单路径：若序列中第一个顶点和最后一个顶点相同的路径称为回路或环，序列中顶点不重复出现的路径。简单回路：若序列中除第一个顶点和最后一个顶点相同外，其余顶点不重复的回路。6．连通图、连通分量、强连通图和强连通分量连通：从顶点v到v′有路径，则说v和v′是连通的。连通图：图中任意两个顶点都是连通的。非连通图：图中并非任意两个顶点都是连通的。连通分量：无向图的极大连通子图。(a)连通图G1(b)非连通图G2(c)G2两个连通分量强连通图：有向图的任意两个顶点之间都存在一条有向路径。强连通分量：有向图中极大的强连通子图(a)强连通图G1(b)非强连通图G2(c)G2三个强连通分量6.2图的存储结构6.2.1邻接矩阵（AdjacencyMatrix）