图基本概念

图：顶点和边的集合。

无向图：每条边都是无方向的

有向图：每条边都是有方向的

完全图：任意两个点都有一条边相连

稀疏图：有很少边或弧的图

稠密图：有较多边或弧的图

网：边/弧带权的图

邻接：有边/弧相连的两个顶点之间的关系

（vi，vj）不分先后关系

<vi，vj>分先后关系，序偶

关联（依附）：边/弧与顶点之间的关系。

顶点的度：与该顶点相关联的边的数目，记为TD（v）

在有向图中，顶点的度等于该顶点的入度与出度之和。

路径：接续的边构成的顶点序列。

路径长度：路径上边或弧的数目/权值之和

回路（环）：第一个顶点和最后一个顶点相同的路径。

简单路径：除路径起点和终点可以相同外，其余顶点均不相同的路径

简单回路（简单环）：除路径起点和终点相同外，其余顶点均不相同的路径。

连通图（强连通图）：在无（有）向图G=（V，{E}）中，若对任何两个顶点v，u都存在从v到u的路径，则称G是连通图（强连通图）

权：图中边或弧所具有的相关数。表明从一个顶点到另一个顶点的距离或耗费。

网：带权的图。

子图：G1是G的子图。

连通分量（强连通分量）

极小连通子图：该子图是G的连通子图，在该子图中删除任何一条边，子图不在连通。

生成树：包含无向图G所有顶点的极小连通子图。

生成森林：对非连通图，由各个连通分量的生成树的集合。

图的存储结构：

邻接表：

1. 有向图：缺点：求结点的度困难---》十字链表

2. 无向图：缺点：每条边都要存储两遍---》邻接多重表

生成树：所有顶点均由边连接在一起，但不存在回路的图。

一个图可以有许多棵不同的生成树。