数据结构-图的基本概念

图的定义

        图时由非空的顶点集合和一个描述顶点之间关系的集合组成。可以定义为：

                                        ​​​​​​​        ​​​​​​​        ​​​​​​​        

         G表示一个图，V表示点集，E表示边集。集合E的每一个二元组都包含两个值和，表示为一条边的两个顶点。

图的相关术语

        （1）无向图

        在一个图中顶点之间的连线没有指定方向。

        （2）有向图

        在一个图中顶点之间的连线有指定方向

        （3）顶点、边

        在无向图中，两个顶点之间的连线称为边，边用顶点的无序偶对表示，称顶点和顶点互为邻接点。

        （4）弧、弧头、弧尾

        在有向图中，两个顶点之间的连线称为弧，弧用顶点的有序偶对表示，有序偶对的第一个结点称为弧尾（图中没有箭头的一端），第二个结点称为弧头（图中有结点的一端）。若是一条弧，则称顶点邻接到。

        （5）无向完全图

        在一个无向图中，如果任意两点都有一条直接边相连接，则称为无向完全图。

        在一个个顶点的无向完全图中有条边。

        （6）有向完全图

        在一个有向图中，如果任意两点都有方向互为相反的两条弧相连接，则称为有向完全图。

        在一个个顶点的有向完全图中有条边。

        （7）稠密图、稀疏图

        若一个图接近完全图，称为稠密图

        边数很少的图为稀疏图

        （8）度

        顶点的度是与顶点相连接的边数，记为

        在有向图中有入度和出度的区分。

        入度指的是以顶点为终点的弧的数目，记为

        出度指的是以顶点为起点的弧的数目，记为

        对于具有个顶点、条边的图，顶点的度与顶点的个数以及边的数目的关系为：

        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        ​​​​​​​        

         （9）边权、网图

        当图的边带有数值信息时，这种数值称为权。

        每条边或弧都带权的图称为带权图或网。

        （10）路径、路径长度

        在无向图中，顶点到顶点之间的路径指序列，路径上边的数目称为路径长度。有向图中路径也是有向的。

        （11）回路，简单回路

        起点和终点相同的路径称为回路或环。除了第一个顶点与最后一个顶点之外其他顶点不重复出现的回路称为简单回路。

        （12）连通图

        在无向图中，任意两个顶点都相互连通，称为连通图。

        （13）强连通图

        在有向图中，如果从一个顶点到另一个顶点均有一条有向路径，则该图为强连通图