第10章 图 零基础学数据结构-课件（PPT·精·选）.ppt

文档介绍：第10章图图是另一种非线性数据结构,是一种更为复杂的数据结构。在图中,数据元素之间是多对多的关系,即一个数据元素对应多个直接前驱元素和多个直接后继元素。图的应用领域十分广泛,如化学分析、工程设计、遗传学、人工智能等。本章的主要学习内容包括图的定义、图的存储结构、图的遍历、图的最小生成树、关键路径和最短路径. 图的定义与相关概念图是一种非线性的数据结构,图中的数据元素之间的关系是多对多的关系。本节主要介绍图的定义和图的相关概念。 图的定义图G是由数据元素集合 V与边的集合 E组成的一种数据结构。数据元素常称为顶点,因此数据元素集合称为顶点集合。其中,顶点集合 V不能为空,边表示顶点之间的关系, 用连线表示。图 G的形式化定义为: G=(V,E) ,其中, V={ x|x ∈数据元素集合}, E={< x,y >| Path(x,y)/\(x ∈ V,y ∈V )} 。 图的定义 图的相关概念 图的相关概念子图: 图的相关概念连通图与强连通图: 图的相关概念生成树: 图的相关概念网: 图的抽象数据类型