数据结构PPT教学课件-第七章 图.ppt

数据结构
------图
欧拉1707年出生在瑞士,19岁开始发表论文,直到76岁。几乎每一个数学领域都可以看到欧拉的名字,从初等几何的欧拉线,多面体的欧拉定理,立体解析几何的欧拉变换公式,四次方程的欧拉解法到数论中的欧拉函数,微分方程的欧拉方程,级数论的欧拉常数,变分学的欧拉方程,复变函数的欧拉公式等等。据统计他的一生,共写下了886本书籍和论文,其中分析、代数、数论占40%,几何占18%,物理和力学占28%,天文学占11%,弹道学、航海学、建筑学等占3%。 1733年,年仅26岁的欧拉担任了彼得堡科学院数学教授。1741年到柏林担任科学院物理数学所所长,直到1766年,重回彼得堡,没有多久,完全失明。欧拉在数学上的建术很多,对著名的哥尼斯堡七桥问题的解答开创了图论的研究。
图论——欧拉
能否从某个地方出发,穿过所有的桥仅一次后再回到出发点?
哥尼斯堡七桥问题
C
A
D
B
七桥问题的图模型
哥尼斯堡七桥问题
欧拉回路的判定规则:
,则不存在欧拉回路;
,可以从这两个地方之一出发,找到欧拉回路;
,则无论从哪里出发,都能找到欧拉回路。
1 图的定义和术语
3 图的遍历
2 图的存储结构
4 图的连通性问题
5 有向无环图及其应用
6 最短路径
图的定义
1 图的定义和术语
图是由顶点的有穷非空集合和顶点之间边的集合组成,通常表示为:
G=(V,E)
其中:G表示一个图,V是图G中顶点的集合,E是图G中顶点之间边的集合。
在线性表中,元素个数可以为零,称为空表;
在树中,结点个数可以为零,称为空树;
在图中,顶点个数不能为零,但可以没有边。
如果图的任意两个顶点之间的边都是无向边,则称该图为无向图。
若顶点vi和vj之间的边没有方向,则称这条边为无向边,表示为(vi,vj)。
若从顶点vi到vj的边有方向,则称这条边为有向边,表示为<vi,vj>。
如果图的任意两个顶点之间的边都是有向边,则称该图为有向图。
V1
V2
V3
V4
V5
V1
V2
V3
V4
1 图的定义和术语
简单图:在图中,若不存在顶点到其自身的边,且同一条边不重复出现。
V3
V4
V5
V1
V2
V3
V4
V5
V1
V2
非简单图非简单图简单图
V1
V2
V3
V4
V5
数据结构中讨论的都是简单图。
1 图的定义和术语
邻接、依附
无向图中,对于任意两个顶点vi和顶点vj,若存在边(vi,vj),则称顶点vi和顶点vj互为邻接点,同时称边(vi,vj)依附于顶点vi和顶点vj。
V1
V2
V3
V4
V5
V1的邻接点: V2 、V4
V2的邻接点: V1 、V3 、V5
1 图的定义和术语
邻接、依附
有向图中,对于任意两个顶点vi和顶点vj,若存在弧<vi,vj>,则称顶点vi邻接到顶点vj,顶点vj邻接自顶点vi,同时称弧<vi,vj>依附于顶点vi和顶点vj 。
V1
V2
V3
V4
V1的邻接点: V2 、V3
V3的邻接点: V4
1 图的定义和术语