图零基础学数据结构.ppt

文档介绍：第章图零基础学数据结构
第一页，共57页。
图的定义与相关概念
图是一种非线性的数据结构，图中的数据元素之间的关系是多对多的关系。本节主要介绍图的定义和图的相关概念。
第二页，共57页。
图的定义
图G是由数据元素集合V与边的集合E组成的一种数据结构。数据元素常称为顶点，因此数据元素集合称为顶点集合。其中，顶点集合V不能为空，边表示顶点之间的关系，用连线表示。图G的形式化定义为：G=(V,E)，其中，V={x|x∈数据元素集合}，E={<x,y>|Path(x,y)/\(x∈V,y∈V)}。
第三页，共57页。
图的定义
第四页，共57页。
图的相关概念
1．邻接点
2．顶点的度
3．路径
4．子图
5．连通图和强连通图
6．生成树
7．网
第五页，共57页。
图的相关概念
子图：
第六页，共57页。
图的相关概念
连通图与强连通图：
第七页，共57页。
图的相关概念
生成树：
第八页，共57页。
图的相关概念
网：
第九页，共57页。
图的抽象数据类型
1．数据对象集合
2．基本操作集合
第十页，共57页。