基础概念

图（Graph）是由顶点的有穷非空集合和顶点之间的边的集合组成，通常表示为：G(V,E)，其中 G 表示一个图，V 是图 G 中的顶点的集合，E 是图 G 中边的集合。

相关概念：

• 顶点：图中的数据元素称之为顶点（Vertex），在图中不允许没有顶点，V 是有穷非空集合。
• 边：图中任意两个顶点之间的逻辑关系用边（Edge）来表示，边集合可以为空。
• 无向边：若顶点 vi 到 vj 之间的边没有方向，则称这条边为无向边，用无序偶对(vi,vj)来表示。
• 无向图：如果图中任意两个顶点之间的边都是无向边，则称该图为无向图。
• 有向边：若从顶点 vi 到 vj 之间的边有方向，则称这条边为有向边，也称为弧（Arc），用有序偶对<vi,vj>来表示。vi 称为弧尾，vj 称为弧头。
• 有向图：如果任意两个顶点之间的边都是有向边，则称该图为有向图。
• 邻接点：对于无向图 G=(V, {E})，如果边(v1,v2)∈E，则称 v1 和 v2 互为邻接点。对于有向图 G=(V,{E})，弧<v1,v2>∈E，则称顶点 v1 邻接到顶点 v2，顶点 v2 邻接自 v1。
• 顶点的度：对于无向图来说，顶点的度是和顶点相关联边的数目，记作 TD(v)。对于有向图，以顶点 v 为头的弧的数目称为 v 的入度（InDegree），记作 ID(v)；以顶点 v 为尾的弧的数目称为 v 的出度（OutDegree），记作 OD(v)；顶点 v 的度为 TD(v) = ID(v) + OD(v)。
• 路径的长度：路径长度是路径上边或弧的数目。
• 回路（环）：第一个顶点到最后一个顶点相同的路径称为回路或环。

下图所示为无向图，其顶点集合为 V={A,B,C,D}，边集合为 E={(A,B), (B,C), (C,D), (D,A), (A,C)}。

下图所示为有向图，连接顶点 A 到 D 的有向边就是弧，A 是弧尾，D 是弧头。<A,D>表示弧。顶点集合为 V={A,B,C,D}，弧集合为 E={<A,D>, <B,A>, <C,A>, <B,C>}。

::: 无向图是用“()”表示，有向图是用“<>”表示。 :::

在无向图中，如果任意两个顶点之间都存在边，则称该图为无向完全图，如下所示。含有 n 个顶点的无向完全图有 n*(n-1)/2 条边。

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

有很少条边或弧的图称为稀疏图，反之称为稠密图，这里稠密和稀疏的概念是比较模糊，没有明确的量化规则。

有些图的边或弧具有与其相关的数字，这种与图的边或弧相关的数字叫做权。带权的图通常称为网。

连通图

在无向图 G 中，如果从顶点 v1 到 v2 有路径，则称 v1 和 v2 是连通的。如果对于图中任意两个顶点之间都是连通的，则称 G 是连通图（Connected Graph）。

下图中图 1 由于顶点 A 到 E 和 F 之间没有路径，所以不是连通图，图 2 和图 3 很显然是连通图。

无向图中的极大连通子图称为连通分量。连通分量需要满足以下要求：

• 必须是子图。
• 子图要是连通的。
• 连通子图含有极大顶点数。
• 具有极大顶点数的连通子图包含依附于这些顶点的所有边。

上图中图 1 是一个无向非连通图，有两个连通分量图 2 和图 3。图 4 虽然是图 1 的子图，但不是图 1 的连通分量，因为不满足连通子图的极大极大顶点数。

在有向图 G 中，如果任意一对顶点 vi 和 vj，从 vi 到 vj 以及 vj 到 vi 之间存在路径，则称 G 是强连通图。下图图 1 中由于顶点 A 到顶点 D 存在路径，但是顶点 D 到顶点 A 不存在路径，所以图 1 不是强连通图，图 2 是强连通图。