数据结构图论部分.ppt

该【数据结构图论部分 】是由【小落意】上传分享，文档一共【192】页，该文档可以免费在线阅读，需要了解更多关于【数据结构图论部分 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。数据结构图论部分
汇报人:
学****目标
领会图的类型定义。
熟悉图的各种存储结构及其构造算法,了解各种存储结构的特点及其选用原则。
熟练掌握图的两种遍历算法。
理解各种图的应用问题的算法。
重点和难点
重点:图的各种应用问题的算法都比较经典,注意理解各种图的算法及其应用场合。
Date
2
知识点
图的类型定义
图的存储表示
图的深度优先搜索遍历和广度优先搜索遍历
无向网的最小生成树
拓扑排序
关键路径
最短路径
Date
3
欧拉1707年出生在瑞士的巴塞尔城,19岁开始发表论文,直到76岁。几乎每一个数学领域都可以看到欧拉的名字,从初等几何的欧拉线,多面体的欧拉定理,立体解析几何的欧拉变换公式,四次方程的欧拉解法到数论中的欧拉函数,微分方程的欧拉方程,级数论的欧拉常数,变分学的欧拉方程,复变函数的欧拉公式等等。据统计他那不倦的一生,共写下了886本书籍和论文,其中分析、代数、数论占40%,几何占18%,物理和力学占28%,天文学占11%,弹道学、航海学、建筑学等占3%。1733年,年仅26岁的欧拉担任了彼得堡科学院数学教授。1741年到柏林担任科学院物理数学所所长,直到1766年,重回彼得堡,没有多久,完全失明。欧拉在数学上的建树很多,对著名的哥尼斯堡七桥问题的解答开创了图论的研究。
图论——欧拉
Date
4
能否从某个地方出发,穿过所有的桥仅一次后再回到出发点?
哥尼斯堡七桥问题
Date
5
C
A
D
B
七桥问题的图模型
欧拉回路的判定规则:
,则不存在欧拉回路;
,可以从这两个地方之一出发,找到欧拉回路;
,则无论从哪里出发,都能找到欧拉回路。
Date
6
图的定义
图是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:
G=(V,E)
其中:G表示一个图,V是图G中顶点的集合,E是图G中顶点之间边的集合。
在线性表中,元素个数可以为零,称为空表;
在树中,结点个数可以为零,称为空树;
在图中,顶点个数不能为零,但可以没有边。

Date
7
线性表
每个数据元素只有一个直接前驱和一个直接后继。
树形结构
每个数据元素只有一个直接前驱,但可能有多个直接后继。
图形结构
每个数据元素可能有多个直接前驱和多个直接后继。
图是比线性表和树复杂的数据结构,广泛应用于语言学、逻辑学、物理、化学等领域。
Date
8
如果图的任意两个顶点之间的边都是无向边,则称该图为无向图。
若顶点vi和vj之间的边没有方向,则称这条边为无向边,表示为(vi,vj)。
若从顶点vi到vj的边有方向,则称这条边为有向边,表示为<vi,vj>。
如果图的任意两个顶点之间的边都是有向边,则称该图为有向图。
V1
V2
V3
V4
V5
V1
V2
V3
V4
图的基本术语
Date
9
稀疏图:称边数很少的图为稀疏图;
稠密图:称边数很多的图为稠密图。
顶点的度:在无向图中,顶点v的度是指依附于该顶点的边数,通常记为TD(v)。
图的基本术语
顶点的入度:在有向图中,顶点v的入度是指以该顶点为弧头的弧的数目,记为ID(v);
顶点的出度:在有向图中,顶点v的出度是指以该顶点为弧尾的弧的数目,记为OD(v)。
Date
15