数据结构重学日记（二十五）图

概念

在计算机科学中，一个图就是一些 顶点的集合，这些顶点通过一系列边结对（连接）。顶点用源圆圈表示，边就是这些圆圈之间的连线。

顶点之间通过边连接。

顶点有时也称为节点或交点，边有时也称为链接。图不可以为空。

图

V（G）表示图 G 中顶点的有限非空集。用 V 表示图 G 中顶点的个数，也称为图 G 的阶。

E（G）表示图 G 中顶点之间的关系（边）集合。用 E 表示图 G 中边的条数。

图的分类

按照图边的方向，可以分为有向图和无向图。

有向图

有向边（弧）的有限集合。

有向图即图的边是有方向的，也称为弧。用<v, w>表示，v为弧尾，w 是弧头。

无向图

无向边（边）的有限集合。
即边没有方向

左弧右边

完全图

完全图也可以根据图边的方向进行划分，分为有向完全图和无向完全图。

有向完全图

如果任意两个顶点之间都存在方向相反的两条弧，则称为有向完全图。

每个顶点都与其他 n - 1 个顶点有一条边，由于方向不重复，所以一共有 n * (n - 1)条边。

有向完全图

无向完全图

如果任意两个顶点之间都存在边，则称为无向完全图。

每个顶点都与其他 n - 1 个顶点有一条边，由于重复，所以一共有 n * (n - 1) / 2 条边。

无向完全图

子图

假设有两个图 G(V, E) 和 G'(V', E')，若 V' 是 V 的子集，E' 是 E 的子集，那么 G' 是 G 的子图。

若子图的顶点与 G的顶点相同，则称为 G 的生成子图。

连通

顶点 v 和 v' 之间有路径，则称为连通。

图中任意两个顶点都是连通的，则称为连通图。

顶点 v 到顶点 w都有路径，称为强连通，图中任意一对顶点都是强连通，则这个图称为强连通图。