01前言
1、图是一种较线性表和树更为复杂的数据结构。
2、在线性表中,数据元素之间仅有线性关系,每个数据元素只有一个直接前驱和一个直接后继。
3、在树形结构中,数据元素之间有着明显的层次关系,并且每一层上的数据元素可能和下一层中多个元素(即孩子结点)相关,但只能和上一层一个元素(双亲结点)相关。
4、在图形结构中,结点之间的关系可以是任意的,图中任意两个数据元素之间都可能相关。
02图的定义和术语
1、图是一种数据结构,加上一组基本操作,就构成了抽象数据类型。
2、数据对象:是具有相同特性的数据元素的集合,称为顶点集。
3、弧尾、弧头、有向图、无向图、完全图、有向完全图、稀疏图、稠密图、路径。
4、图的边或弧具有与它相关的数,这种与图的边或弧相关的数叫做权。这些权可以表示从一个顶点到另一个顶点的距离或耗费,这种带权的图通常称为网。
5、第一个顶点和最后一个顶点相同的路径称为回路或环。
6、序列中顶点不重复出现的路径称为简单路径。
7、除了第一个顶点和最后一个顶点之外,其余顶点不重复出现的回路,称为简单回路或简答环。
8、有向图中的极大强连通子图称做有向图的强连通分量。
9、一个连通图的生成树是一个极小连通子图,它含有图中全部顶点,但只有足以构成一棵树的n-1条边。
10、如果一个有向图恰有一个顶点的入度为0,其余顶点的入度均为1,则是一棵有向图。一个有向图的生成森林由若干棵有向树组成,含有图中全部顶点,但只有足以构成若干棵不相交的有向树的弧。
热门跟贴