## 图的定义 图 (Graph) 是由若干给定的顶点及连接两顶点的边所构成的图形，这种图形通常用来描述某些事物之间的某种特定关系。 顶点用于代表事物，连接两顶点的边则用于表示两个事物间具有这种关系。 图论 (Graph theory) 是数学的一个分支，图是图论的主要研究对象。 表达式：G=(V, E) V：顶点（数据元素）的有穷非空集合。 E：边的有穷集合。 Graph = (Vertex, Edge) ## 基本术语 **无向图**：顶点之间相连的线我们称为边，每条边都是无方向的。 **有向图**：顶点之间相连的线我们称为弧，每条弧都是有方向的。 **完全图**：任意两点都有一条边相连。（右向完全图和无向完全图） **稀疏图**：有很少边或弧的图。 **稠密图**：有较多边或弧的图。 **网**：边/弧带权值的图。 **邻接**：有边/弧相连的两个顶点之间的关系。 **顶点的度**：与该顶点相关联的边的数目，有入度和出度。 **路径**：连续的边/弧构成的顶点序列。 **路径长度**：路径上边或弧的数目/权值之和。 **回路（环）**：第一个顶点和最后一个顶点相同的路径。 **权与网**：图中边或弧所具有的相关数称为权。表明从一个顶点到另一个顶点的距离或耗费。带权的图称为网。 **子图**：设有两个图G=(V, {E})、G1=(V1, {E1})，若V1⊆V，E1⊆E，则称G1是G的子图。 **生成树**：包含无向图G所有顶点的极小连通子图。 **生成森林**：对非连通图，由各个连通分量的生成树的集合。