算法6 基本图算法 - ricket-sjtu/bi028 GitHub Wiki

基本内容

  • 图（Graphs）的基本概念
  • 图的表示：邻接矩阵（Adjacency matrix）和邻接表（Adjacency list）
  • 特殊的图
  • 深度优先（depth-first）与广度优先（breadth-first）搜索
  • 拓扑排序（topological sort）
  • 欧拉回环（Eulerian circuit）
  • 最小生成树（Minimum spanning tree, MST）
  • 强连通组分（Strongly connected component, SCC）

1. 图的概念

  • 用节点（nodes, vertices）和边（edges）表示连接关系（connection）的抽象方法（abstract method）。
  • 将节点标注为1-$n$
  • 存在$m$条边连接一对对的节点，边可以是有向的（directed），也可以是无向的（undirected），甚至是双向的（bidirectional）。
  • 节点和边可以有其他附加的属性（auxiliary information）

1.1 图研究中的基本问题

  • 最短路径问题（shortest path）
  • 网络流分布问题（network flow）
  • 图匹配问题（matching problem）
  • 2-SAT问题
  • 图着色问题（graph coloring）
  • 旅行商问题（traveling salesman problem, TSP）
  • ...

2. 图的表示方法：数据结构

要存储图的数据结构，必须满足以下要求：

  • 必须同时存储节点（nodes）和边（edges）以及它们的附属信息；
  • 必须能够完成以下操作：
    • 获取与某个指定节点相连的边
    • 考察两个节点是否直接相连
  • 一般用邻接矩阵或者邻接表完成图的数据结构

2.1 邻接矩阵（Adjacency matrix）

  • 是一种存储连接信息的简易方法：
    • 检查两个节点是否直接相连：时间复杂度为$\mathcal{O}(1)$
  • 建立$n\times n$的矩阵 $$ a_{ij} = \begin{cases} 1 & \text{if there is an edge from } i \text{ to } j\\ 0 & \text{otherwise} \end{cases} $$
  • 空间复杂度$\mathcal{\Theta}(n^2)$
    • 仅当$n<1000$时候使用，且
    • 图是稠密的（dense）而不是稀疏的（sparse）
  • 优点：
    • 容易理解和实现
  • 缺点：
    • 不适用于大规模的稀疏图

2.2 邻接表（Adjacency list）

  • 实现方案：每个节点存储从其出去的边的表（list）
  • 优点：容易遍历（traverse）与每个节点相连的节点和边
  • 缺点：每个表具有不同的长度
  • 存储：$\mathcal{\Theta}(n+m)$

2.3 如何实现邻接表（adjacency list）

  • 方案1：使用链表（linked list）
    • 时间/内存的开销较大
    • 使用动态分配的内存和指针的方法是比较糟糕的
  • 方案2：使用向量数组（an array of vectors）
    • 容易编程实现，没有内存的问题
    • 非常慢
  • 方案3：使用数组
    • 假设总边数（total number of edges）已知
    • 首选，速度快，内存开销小

2.4 用数组实现图

  • 用两个数组E[m]{to, nextID}和LE[n]
    • E存储边
    • LE存储边的起始节点（starting node）的指针（pointer）
  • 初始化$LE$，令LE[i]=-1
  • 插入一条新的ID为k的边(u, v)：
    • E[k].to = v
    • E[k].nextID = LE[u]
    • LE[u] = k
  • 遍历从u开始的边：
for (ID=LE[u]; ID!=-1; ID=E[ID].nextID)
//E[ID] is an edge starting from u
  • 缺点：一旦建立，无法修改边
    • 静态图
    • 容易加入新的边

3. 特殊的图

  • 树（tree）
  • 有向无环图（directed acyclic graph, DAG）
  • 二部图（bipartite graph）

3.1 树

  • 无环图（acyclic graph）
  • 最为重要的特殊图
    • 许多问题在树结构下容易解决
  • 其他类似的定义：
    • 具有$n-1$条边的连通图
    • 具有$n-1$条边的无环图
    • 任意一对节点中有且仅有一条路径
    • 无环图，但加入一条边会产生环
    • 连通图，但是去掉任一条边将成为非连通图

3.2 其他特殊的图

  • 有向无环图（DAG）
    • 相当于节点的部分排序
  • 二部图
    • 可以将节点分为$S$与$T$两个集合，这样所有的边都在$S$与$T$之间，也就是说$S$和$T$内部不存在边。

4. 图的遍历（traversal）

  • 最基本的图算法就是按照一定的序列访问图中的每一个节点
  • 是许多其他问题的子程序（subroutine）
  • 两种基本方法：
    • 深度优先搜索（DFS）：采用递归recursion的结构（栈，stack）
    • 广度优先搜索（BFS）：采用队列（queue）结构

4.1 深度优先搜索（Depth-first search, DFS）

  • DFS(v)：按照深度优先顺序访问从v开始的所有节点
    • 将visited[v] = True；
    • 对于每条边v->u:
      • if !visited[v]: DFS(u)
  • 如果递归深度太高（超过1000），用非递归版本替代
    • 将递归调用替换为栈操作

4.2 广度优先搜索（Breadth-first search, BFS）

  • BFS(v)：按照广度优先策略访问从v开始的所有节点
    • 初始化一个队列Q=queue()
    • visited[v]=True; Q.push(v)
    • while !empty(Q):
      • w = Q.getFrontElement()
      • foreach edge w->u:
        • if !visited[u]: visited[u]=True; Q.push(u)

5. 拓扑排序（topological sort）

  • 输入有向无环图（DAG）：G=(V, E)
  • 输出：按照一定的次序输出所有的节点，对于每条边u->v，u需置于v前
  • 同一个图，可以不止一个答案

5.1 拓扑排序基本思路

  • 所有无进入边的节点可以作为第一个元素

  • 确定第一个节点后，删除这个节点的所有输出边

  • 重复1-2步

  • 时间复杂度：$\mathcal{O}(n^2+m)$

    • 非常慢...

5.2 拓扑排序的快速版本

  • 先计算每个节点的输入边的数量deg(v)

  • 初始化Q=queue()

  • 对于任意的节点v，如果deg(v)=0，则Q.push(v)

  • 当!empty(Q)：

    • 从Q中取出节点v
    • 对所有的边v->u：
      • deg(u) -= 1
      • 如果deg(u)=0，Q.push(u)

  • 时间复杂度：$\mathcal{\Theta}(n+m)$

6. 欧拉回路（Eulerian Circuit）

  • 输入：无向图G
  • 输出：节点序列，访问每一条边仅一次，最终回到出发点
  • 欧拉回路存在，当且仅当
    • G是连接的
    • 每个节点都连接偶数条边

6.1 相关问题

  • 欧拉路径（Eulerian path）：存在，当且仅当图是连接的，且具有奇数边的节点的数量为0或2；
  • **汉密尔顿路径/环（Hamiltonian path/cycle）：访问图中的每个节点仅一次，与前面的问题类似，但更困难！

7. 最小生成树（Minimum Spanning tree, MST）

  • 输入：无向加权图G=(V, E)
  • 输出：找到一个E的子集，将所有的节点连接为树，令其总权重最小
  • 两种基本算法：
    • Kruskal算法
    • Prim算法

7.1 Kruskal算法

  • 主要思想：具有最小权重的边$e^*$必须包含在MST中
  • 简单证明:
    • 假设存在一个MST为T不包含$e^*$
    • 将$e^*$加入T中，产生环
    • 从环中去除具有最高权重的边，删除的边不可能是$e^*$，因为其有最小的权重
    • 这个树比T的总权重更小，这与前面的假设矛盾，得证！

7.2 Kruskal算法

  • 另一个主要思想：当某一条边被选择后，两端的节点可以合并为一个超节点（supernode）
  • 伪代码：
    • 将所有的边按照升序排列
    • 重复以下过程，直到只剩下一个超节点为止
      • 取最小权重的边$e^*$
      • 如果$e^*$连接两个超节点，合并这两个超节点为一个超节点；否则忽略这条边，尝试下一个边

7.3 Prim算法

  • 主要思想
    • 从一个节点$s$开始的一个集合$S$
    • 找到连接$u \in S$和$v \not\in S$的边中权重最小的边$e^* = (u, v)$
    • 将$e^*$加入MST，$v$加入$S$
    • 重复这个过程，直到$S = V$
  • 与Kruskal算法不同的是，同时只生长一个超节点$S$，而不是同时产生多个超节点
  • 伪代码：
    • 初始化S:={s}; D_v = cost(s, v) for every v
      • 如果(s,v)不存在，则cost(s,v)=infty
    • 重复过程，直到$S=V$:
      • 采用优先队列或简单线性搜索找到$v \not\in S$具有最小的$D_v$的节点v
      • 将v加入S，同时将$D_v$加入MST的总权重
      • 对于与v连接的所有边(v, w)：更新$D_w := \min(D_w, cost(v, w))$
  • 可以修改为计算实际的MST以及其总权重

7.4 比较Kruskal与Prim算法

  • Kruskal算法
    • 时间复杂度：$\mathcal{O}(m\log m)$
    • 优点：容易编程实现
    • 缺点：速度比Prim慢
  • Prim算法
    • 算法复杂度取决于实现手段：
      • 可以为$\mathcal{O}(n^2+m), \mathcal{O}(m \log n), \mathcal{O}(m+n\log n)$
    • 编程复杂一些
    • 比Kruskal速度快

8. 强连通组分（Strongly connected component, SCC）

  • 输入：有向图$G=(V, E)$
  • 一个图为强连通当且仅当对于图中的每一个节点，都可以有一条路径到达图中的任意另一个节点。
  • 一个图的强连通组分就是该图的最大强连通子图（strongly connected subgraph）

8.1 Kosaraju算法

  • 初始化计数器$c:=0$
  • 当仍存在节点未标注：
    • 随机选择一个未标注节点$v$
    • 从$v$开始进行DFS
      • 将当前节点$x$标注为visited
      • 递归访问所有未访问邻居
      • 当每次DFS调用结束，$c:=c+1$，将$x$标注为$c$
  • 将每条边的方向逆转
  • 对于标签为$n, n-1, \dots, 1$的节点$v$:
    • 找到对于节点$v$的所有可到达节点，将其合并为一个SCC

Kosaraju算法

  • Let $G$ be a directed graph and $S$ be an empty stack.
  • While $S$ does not contain all vertices:
    • Choose an arbitrary vertex $v$ NOT in $S$;
    • Perform a depth first search starting at $v$;
    • Each time that depth-first search finishes expanding a vertex $u$, push $u$ onto $S$.
  • Reverse the directions of all arcs to obtain the transpose graph.
  • While $S$ is nonempty:
    • Pop the top vertex $v$ from $S$.
    • Perform a depth-first search starting at $v$ in the transpose graph.
    • The set of visited vertices will give the strongly connected component containing $v$;
    • Record this and remove all these vertices from the graph $G$ and the stack $S$.