第10章 图 零基础学数据结构.ppt

文档介绍：图的定义与相关概念
图是一种非线性的数据结构，图中的数据元素之间的关系是多对多的关系。本节主要介绍图的定义和图的相关概念。
第一页，共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页。
图的存储结构
图的存储方式有四种：邻接矩阵表示法、邻接表表示法、十字链表表示法和多重链表表示法。本节的主要学习内容是图的这四种存储结构。
第十页，共57页。