图 数据结构VIP免费

24/12/261“图”专题2012年11级新队员暑假ACM培训主讲：廖枝平24/12/2621)了解图的定义和术语；2)掌握图的各种存储结构；3)掌握图的深度优先搜索和广度优先搜索遍历算法；4)理解最小生成树、最短路径、拓扑排序等图的常用算法

““图”专题学习导读图”专题学习导读主要介绍图的基本概念、图的存储结构和有关图的一些常用算法

学习目的：24/12/263集合:数据元素间的关系是同属一个集合

线性结构：结点间的关系是线性关系，除开始结点和终端结点外，每个结点只有一个直接前趋和直接后继

树形结构：结点间的关系实质上是层次关系，同层上的每个结点可以和下一层的零个或多个结点（即孩子）相关，但只能和上一层的一个结点（即双亲）相关（根结点除外）

图（Graph）结构：对结点（图中常称为顶点）的前趋和后继个数不加限制的，即结点之间的关系是任意的

图是一种较线性表和树更为复杂的非线性结构

是对结点的前趋和后继个数不加限制的数据结构，用来描述元素之间“多对多”的关系

24/12/26424/12/26577

1图的定义图的定义图是由一个顶点集图是由一个顶点集VV和一个弧集和一个弧集RR构成的数据结构成的数据结构

Graph=(V,R)Graph=(V,R)VV={={xx||xx某个数据对象某个数据对象}}，是顶点的有穷非空集合；，是顶点的有穷非空集合；R——R——边的有限集合边的有限集合RR={(={(xx,,yy)|)|xx,,yyVV}}无向图或无向图或RR={||xx,,yyVV&&&&PathPath((xx,,yy)})}有向图有向图是顶点之间关系的有穷集合，也叫做边是顶点之间关系的有穷集合，也叫做边((edge)edge)集合

PathPath((xx,,yy))表示从表示从xx到到yy的一条单向通路的一条单向通路,,它是有方向的