1. 概念, 性质, 实现

1.1 定义

图是一个二元组 G=(V, E), V 是非空有穷的顶点集合, E 是顶点的边, 也是顶点之间的相互直接联系

图分为有向图, 无向图. 根据边的关系类型来分

  • 邻接点: 无向图中, 相互连接起来的就叫邻接点, 有向图中, x 指向 y, y 是 x 的邻接点. 这个连接的边就叫 邻接边
  • 顶点的 : 一个顶点有几条邻接边, 叫做该点的度. 对于无向图和邻接点是一个意思. 不过对于有向图就不一样了. 有出度入度之分. 意思是指出去的方向的邻接边数量, 和指向自己的边的数量
  • 路径长度: 点 a 到点 b 的边的条数总和
  • 回路: 起点和终点是相同的路径
  • 简单回路: 回路里除起点和终点相同, 其他点都不相同
  • 简单路径: 不包含回路的路径
  • 连通: 存在一条路径使得顶点 x 可以到达顶点 y, 则叫 x 到 y 是连通的. 注意到, 在有向图中, x -> y 连通, 并不意味 y -> x 也是连通的

1.2 一些图有名字的图

  1. 有根图: 图中至少存在一个顶点 v, 从顶点 v 能到图中的任意一个顶点, 意思顶点 v 和任意一个点都是连通的(注意边通不等于邻接). 这个顶点 v 就叫图的 . “至少” 两个字说明一个有根图中可能存在许多个根

  2. 完全图: 任意两个顶点之间都互为邻接点的图.

    • n 个顶点的无向完全图有 n * (n - 1) / 2 条边
    • n 个顶点的有向完全图有 n * (n - 1) 条边
  3. 连通图: 连通图指的是对于图中的任意两个顶点x, y, 这两顶点都是连通的. 对于有向图和无向图连通图可以具体些. 在无向图中称为, 连通无向图, 在有向图中称为, 强连通有向图. 在强连通的有向图中需要注意的是, 两顶点的连通的路径是有可能不一样的, x -> y 可能是直接的, y -> x 就有可能绕路间接连通. 而对于无向图, 如果不存在回路的话, 路径是固定的. 这从看, 只有完全图一定是连通的, 反过就不一定了

    强连通指是有向图, 无向图一般叫连通

  4. 最小连通图: 指的是去掉任意一条边, 图不再是连通图

    • 包含 n 个顶点的最小连通无向图有 n -1 条边
  5. 最小根图: 指的是去掉任意一条边, 图不再是有根图

    • 包含 n 个顶点的最小根图恰好包含 n - 1 条边
  6. 子图: 对于图 G=(V, E) 和图 G'=(V’, E’), 总是有 V' ⊆ V 而且 E' ⊆ E, G’ 便叫做 G 的子图. 所以任意图也是自己的子图

  7. 连通子图: 一个图可能不是连通图, 但它的一些子图是连通图, 则叫这些子图为连通子图

  8. 极大连通子图(连通分量): 图 G 中的连通子图 G’ 里, 不能再多加一个顶点或去掉任一条边, 否则就会导致子图不能构成连通, 要点是不能再添加.

    • 这说明是 G’ 取出的顶点不一定是最多的. 所以对于连通图来说, 连通分量就是它自己本身, 而对于非连通图来说, 有多种可能.
    • 而对于有向图来说, 称为极大强连通子图(强连通分量), 一个强连通图并不一定等于其本身
  9. 带权图: 图中的每条边都有一个权值

1.2 图的表现形式

一般用两种形式来表现图, 一是邻接矩阵, 二是邻接表

  • 邻接矩阵: 一个二维的数组, 图中的每一个元素表示其对应的顶点是否邻接. 如果是一个带权的邻接矩阵图, 一般我们会用一个无穷大来表示其不邻接. 然后可以用 0 来表示自身到自身是邻接的. 邻接矩阵的缺点就是占空间, 但其某个点到某个点是否为邻接是 O(1), 因为是数组实现
  • 邻接表: 用一个数组来记录所有的顶点, 然后这个数组元素里的顶点都有一个指针指向一个自己邻接顶点集合, 这个集合可以用数组或者用链表来实现. 集合中的邻接点不同的位置会导致我们在遍历图时有不同的顺序. 邻接表就是省空间, 而且使用链表实现的邻接集合也是很容易添加新的邻接关系, 但在查找邻接关系所需时间就需要看具体实现
1.3 在 Python 中图数据的实现
  • 用两个 list 或者两个 tuple 都能很好的实现邻接矩阵
  • 我们也可以自定义一种 dict 对象, {i: j} 来表示邻接映射关系, 这种实现可以让我们很容易在 O(1) 查找到邻接关系, 但由于内置 dict 是一个顺序储存的 hash 实现, 在大型图上我们需要的容量比图的实际容量大. 还有需要用到一些 python 小技巧, 我们并存储非邻接关系, 而是使用 dict.get 来默认返回一个 None 值, 这样所需空间可以小些
  • 利用 bytearray 或者内置库 array 来实现, 这两种都是可变类型
  • 自定义类型来实现邻接表, 比如集合以上方法
1.4 图的遍历算法

遍历指的是把图中的顶点都访问过一遍, 我们需要一个集合来记录已经访问过的顶点, 避免在回路中重复访问顶点, 另外一般图可能不是连通图, 我们可能需要重新选择一个起点来遍历图

  • 深度优先: 总是先一条路径走到黑, 然后再从邻接点里选一个再走, 直到所有顶点都遍历
    1. 选择一个顶点 v, 然后把 v 的邻接点都入栈, 标记 v 为遍历过
    2. 从栈中弹出一个邻接点 v1, 然后再把这个点的邻接点入栈, 把弹出的顶点标记为遍历过
    3. 重复上面的事, 每当弹出一个, 都表示遍历, 然后会总是找下层的邻接点
    4. 循环终止的条件有两个: 一是栈中没有元素, 二是所有点都被标记为遍历过(如果图不是连通图的话, 就有跟 v 不连通的顶点, 连通图就不用判断这个了)
  • 宽度优先: 总是先访问该顶点所有的邻接点, 再访问下一层
    1. 选择一个顶点, 然后把 v 的所有邻接点都入队列
    2. 依次访问队列头的顶点, 然后把该顶点的邻接点都加到队尾中
    3. 循环上面操作直到队列中没有顶点为止(在连通图中)

2. 生成树

2.1 什么是生成树

我们知道 1: 对于连通无向图/强连通图, 从任意一个顶点 v 都能到达其他任意顶点; 2: 对于有根有向图, 从根都可以到达任意一顶点.

生成树: 对于图 G 生成树是具有 G 所有的顶点, 并且边数最少的边通子图(因为条件是最少, 所以生成树不存在回路问题), 连通图的生成树可能有多个, 有根有向图只能是从根开始, 所以是一个

  • 生成树的边数: 如果 n 个顶点的连通图 G 生成树包含恰好 n - 1 条边, 所以在无向图的生成树就是其最小连通子图. 有向图的生成树中所有的边都位于从根到其他顶点的路径上
  • 包含 n 个顶点, m 个连通分量的无向图 G 的生成树恰好包含 n - m 条边
2.2 生成树构造方法
  • 依据图的深度优先算法构造的尝试优先生成树
  • 依据图的广度优先算法构造的广度优先生成树

3. 最小生成树

如果图是一个带权图, 那么其不同的生成树, 权值可能就不一样. 最小权值合的生成树便叫最小生成树

显然, 最小生成树也可能惟一. 下面是几种构造最小生成树的算法

3.1 Kruskal 算法

如果图 G = (V, E) 是一个包含 n 个顶点的连通图, 构造最小生成树步骤如下

  1. 初始时我们取 G 的所有的 n 个顶点, 形成一个孤立的图 T = (V, {}). 这样每一个顶点都是自成一个连通分量
  2. 将边集 E 中的按权值递增的顺序排序, 然后每次我们都取最小权值的边, 把这条边的对应关系填到 T 中
  3. 不断重复上边的操作, 直到 T 中所有的顶点都包含在一个连通分量为止, 最后 T 便是一棵最小生成树

用来判断的条件我们可以构造一个集合, 初始时集合中包含所有的顶点, 每次找到一个邻接关系时, 把对应的邻接点都集合中去掉, 当的集合为空时, 便得到了最小生成树.

而如果邻接边全都遍历过了, 并且集合也不为空, 说明没有得到最小生成树, 原图是不连通的

3.2 Prim 算法

Prim 算法主要使用了 MST 性质:

设有 G = (V, E) 图, U 是 V 的一个真子集, 当有一对邻接点(也是边) e = (u, v), u ⊆ U, v ⊆ (V -U), 也就是说, 这两个邻接点, 一个点 u 是在集合 U 中, 另一个点不在集合 U中, 并且点 v 是点 u 所有在集合 (V - U) 中邻接边可能会最小的. 这样的话, 图 G 必定有一棵包括边 e 的最小生成树

  1. 从图 G 中选取任一顶点 v0, 放到集合 U 中, 这里 U = {v<sub>0</sub>}, 设一个初始的边集合 E<sub>T</sub> = {}, 那么有 T = (U, E<sub>T</sub>) 是一棵树, 初始时只包含一个顶点
  2. 查找所有一个商战在集合 U 里而一个端点在集合 V - U 中的边, 也就是对于一个顶点 v, 找到其所有的邻接点, 并且这些个邻接点还没有和顶点 v 一样, 存在在集合 U 中, 我们找出这些点后, 取其中权值最小的边得到邻接点 v’, 把 v’ 存放到集合 U 中, 把 v 和 v’ 的邻接关系 e = (v, v'), v ⊆ U, v' ⊆ (V -U) 存放到第一步中的 E<sub>T</sub> 重复上面的步骤直到 U = V, 也即是图 G 中的所有顶点 V 都一一存在于集合 U 中, 这时集合 E<sub>T</sub> 里有 n - 1 条边, 子图 T = (U, E<sub>T</sub> ) 就是 G 的最小生成树