7.1 图的定义和术语

01前言

1、图是一种较线性表和树更为复杂的数据结构。

2、在线性表中，数据元素之间仅有线性关系，每个数据元素只有一个直接前驱和一个直接后继。

3、在树形结构中，数据元素之间有着明显的层次关系，并且每一层上的数据元素可能和下一层中多个元素（即孩子结点）相关，但只能和上一层一个元素（双亲结点）相关。

4、在图形结构中，结点之间的关系可以是任意的，图中任意两个数据元素之间都可能相关。

02 图的定义和术语

1、图是一种数据结构，加上一组基本操作，就构成了抽象数据类型。

2、数据对象：是具有相同特性的数据元素的集合，称为顶点集。

3、弧尾、弧头、有向图、无向图、完全图、有向完全图、稀疏图、稠密图、路径。

4、图的边或弧具有与它相关的数，这种与图的边或弧相关的数叫做权。这些权可以表示从一个顶点到另一个顶点的距离或耗费，这种带权的图通常称为网。

5、第一个顶点和最后一个顶点相同的路径称为回路或环。

6、序列中顶点不重复出现的路径称为简单路径。

7、除了第一个顶点和最后一个顶点之外，其余顶点不重复出现的回路，称为简单回路或简答环。

8、有向图中的极大强连通子图称做有向图的强连通分量。

9、一个连通图的生成树是一个极小连通子图，它含有图中全部顶点，但只有足以构成一棵树的n-1条边。

10、如果一个有向图恰有一个顶点的入度为0，其余顶点的入度均为1，则是一棵有向图。一个有向图的生成森林由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。

C语言 | 杨辉三角​ mp.weixin.qq.com

文章来源: zhuanlan.zhihu.com，作者：小林C语言，版权归原作者所有，如需转载，请联系作者。

原文链接：zhuanlan.zhihu.com/p/337458398