算法导论之图论

最近在二刷算法导论，特别关注平时工作能用到的部分。总结和整理如下，梳理脉络并加深记忆。本文摘录一些和图论相关的内容。

后续陆续更新。

最小生成树 - Prime 算法

(Update by 20211011)

普里姆算法，求解在连通加权无向图中权值最小的生成树，求存在解而非所有解。

求解过程及伪代码

以某一个点开始，寻找当前该点可以访问的所有的边；
在已经寻找的边中发现最小边，这个边必须有一个点还没有访问过，将还没有访问的点加入我们的集合，记录添加的边；
寻找当前集合可以访问的所有边，重复2的过程，直到没有新的点可以加入；
此时由所有边构成的树即为最小生成树

PRIM method
for each u in G:
    u.key = inf
    u.pre = null
Q = G.V
while (Q):
    u = EXTRACT-MIN(Q)  // 找到不在 Q 中的结点 u，使得 u 和 G - Q 中结点连成的边最小
    for each v in G.adj(u):
        RELAX(u, v, w)

求解过程和 dijkstra 方法非常相似，也是基于贪心算法完成。这里算法的核心也是 EXTRACT-MIN 和 RELAX （可以使用 priority queue），相关分析和技巧可以参考 dijkstra 部分的论述。

证明

可参考算法导论 chapter 23

一个例子

1584 连接所有点的最小费用

解答详细代码略，核心注意：

时刻注意剪枝，可以大幅降低复杂度
使用优先队列，提高 cpp stl 常用数据结构的熟悉程度

单源最短路径 - Dijkstra 算法

中文名为迪杰斯特拉算法。本章大部分内容摘录自《导论》chapter 24 集中相应章节。

算法简述

对于单源最短路径问题，当图内无负自环情况下，dijkstra 算法是其中一种较优的实现。 dijkstra 算法本质上依然是贪心算法。其伪代码如下:

// DIJKSTRA METHOD (G, w, s)

INITIALIZE(G, s)
S = {empty set}
Q = G.V
while Q != {empty set}	
    u = EXTRACT-MIN(Q)
    S = S + {u}     // update S and Q
    Q = Q - {u}     // 这行是我加的，原文没有
    for each vertex in G.adj[u]:  // 遍历 u 的所有邻边 
        RELAX(u, v, w)

算法内包括几个核心步骤

INITIALIZE: 初始化，对每个顶点元素 s，有 $s.d = infinity$
EXTRACT_MIN: 从剩余的顶点中，选择距离最短的。（重要，否则不能保证算法的正确性）
update: S and Q(always = G - S)
RELAX: delta(s, v) = min(delta(s, u)+ w(u, v), delta(s, v))

对于稀疏图，内层的for循环消耗时间极少，时间瓶颈在于Extract-min 函数。可以使用优先队列进行优化，下给出实例。

Note: 对于稠密图，优化可能并不会更快。

证明

算法导论的核心就是各种算法的证明。总结整理一个简化的版本如下:

符号说明：

$s$: 初始顶点
$y.d$: y在某时刻对应的距离（不一定是最短的）
$\delta(s, u)$ - $s$ 和 $u$ 之间的最短距离

我们希望证明 $Q$ 中每个 $u$ 移到 $S$ 中时候，都有 $u.d = \delta(s, u)$ :

反证，初始时刻显然成立。$u$ 是第一个不满足 $u.d = \delta(s, u)$ 条件的顶点，则 $s-u$ 的最短路线上存在点 $y$ ，$y$ 的前继顶点 $x$ ，且 $x \in S$, $y \in Q, u \in Q$，接下来我们分两个步骤来证明：

step1:

证明 $\delta(s, y) = y.d$

首先，因为u是第一个不满足此性质的点，所以$x.d=\delta(x, s)$ $x$ 是 $y$ 的前驱节点，则有 $s～x$ 也是最短路径，$\delta(s, x) = x.d$, 那么，一定有

\[y.d \leq x.d + w(x, y) = \delta(x, d) + w(x, y) = \delta(y.d)\]

relax操作保证了第一个不等式成立。最后一个等号成立的原因是，最短路径上的子路径也一定是最短的。

另一方面，有 $y.d \geq \delta(y, d)$，从而 step1成立。

step2:

证明 $y=u$

若不成立，则有 $y.d < u.d, y \in Q$, 与 $u$ 是 $Q$ 中 $\delta(u, s)$ 取最小值的顶点矛盾，从而得证。

1/2 共同证明了 dijkstra 算法的正确性。

杀鸡用牛刀 for leetcode127-单词接龙

为了熟悉 dijkstra 算法，特意找只鸡用牛刀试试。选择了一个 leetcode 中的题目，这个题目并不复杂，主要还是为了熟悉下算法原理。

题目

127. 单词接龙

字典 wordList 中从单词 beginWord 和 endWord 的转换序列是一个按下述规格形成的序列：

序列中第一个单词是 beginWord 。序列中最后一个单词是 endWord 。每次转换只能改变一个字母。转换过程中的中间单词必须是字典 wordList 中的单词。给你两个单词 beginWord 和 endWord 和一个字典 wordList ，找到从 beginWord 到 endWord 的最短转换序列中的单词数目。如果不存在这样的转换序列，返回 0。

输入：beginWord = “hit”, endWord = “cog”, wordList = [“hot”,”dot”,”dog”,”lot”,”log”,”cog”] 输出：5 解释：一个最短转换序列是 “hit” -> “hot” -> “dot” -> “dog” -> “cog”, 返回它的长度 5。

常规解法: bfs + 哈希。每次迭代将可以转换的元素加入一个hash序列，判断是否输出词是否在hash序列内即可。双向搜索还能更快一点。

建图

我们建立一个无向无环图，可以转换的两个词之间有边相连（权重为1），其余词之间无边（权重为∞）。

if(find(wordList.begin(), wordList.end(), endWord)==wordList.end()){
  return 0;  // 特殊case判断，终点词不在图内
}
    
wordList.emplace_back(beginWord);  // 把起始词加入wordlist，这样处理起来会更简单
int n_words = wordList.size();
vector<vector<int>> edge(n_words, vector<int>());  // construct graph
for (int i=0;i<n_words;i++){
  for (int j=i+1;j<n_words;j++){        
    if (diff_word(wordList[i], wordList[j])){
      edge[i].emplace_back(j);          
      edge[j].emplace_back(i);
    }
  }      
}

// 确定图的起始节点和终止节点     
int start_idx = -1;
for(int i=0;i<n_words;i++){
  if (wordList[i]==beginWord){
    start_idx = i;
  }
}
int end_idx = -1;
for(int i=0;i<n_words;i++){
  if (wordList[i]==endWord){
    end_idx = i;
  }
}
    
unordered_set<int> S; 
unordered_set<int> Q;  // V-S
vector<int> d(n_words, n_words+1);  // for distance 
... 
...

bool diff_word(string a, string b){
  int n = a.size();
  int dif = 0;
  for(int i=0;i<n;i++){
    if (a[i]!=b[i]){
      dif++;
      if (dif==2) return false;
    }
  }
  return true;
}

初始化

INITIALIZE 函数实现

S.insert(start_idx);    
for(int j=0;j<edge[start_idx].size();j++){      
  d[edge[start_idx][j]] = 1;
  d[start_idx]=0;
}

for(int i=0;i<n_words-1;i++){
  Q.insert(i);
}

朴素实现

while(Q.size()>0){  
  // u = Extract-MIN(Q)
  int u_idx = -1; int min_val = n_words+1;
  for(auto it=Q.begin();it!=Q.end();it++){
    int idx_q = *it; // todo        
    if (d[idx_q]<min_val){
        min_val = d[idx_q];
        u_idx = idx_q;
        // break;            
    }
  }
  
  if (u_idx==-1 || find(S.begin(), S.end(), end_idx)!=S.end()){
    break;  // 剪枝
  }  
  
  // Update
  S.insert(u_idx);
  Q.erase(u_idx);      
  
  // RELAX for edge  
  int u_size = edge[u_idx].size();
  for (int i=0;i<u_size;i++){
    int v_idx = edge[u_idx][i];
    if (d[v_idx]>d[u_idx]+1){
      d[v_idx] = d[u_idx] + 1;                
    }
  } 

  if (d[end_idx]>n_words-1){      
    return 0; // 未联通
  } else {
    return d[end_idx] + 1;
  }    
};

优化版本

使用优先队列priority queue进行优化，每次入队和出队的时间复杂度均为 logN，但可能会有元素重复入队(稀疏图下带来的额外开销不大)。

// 使用 vector used 代替 S, pq 代替 Q    
vector<int> d(n_words, n_words+1);    
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>> > heap; // 大根堆
vector<int> used(n_words, 0);
used[start_idx] = 1;
int used_total = 1;

d[start_idx]=0;
for(int j=0;j<edge[start_idx].size();j++){    
  int start_adj_idx = edge[start_idx][j];
  d[start_adj_idx] = 1;
  heap.push({d[start_adj_idx], start_adj_idx});
}

while(heap.size()>0){                
  // Extract-MIN(Q)      
  pair<int, int> q_pair = heap.top();
  heap.pop();
  int u_idx = q_pair.second;            
  if(used[u_idx]==1){  // only for Q: G-S
    continue;
  }
、  
  // update for S
  used[u_idx]=1;      
  used_total++;
  
  if(used[end_idx]==1){
    break;  // 剪枝 and lazy-deletion
  }
  
  // RELAX for edge
  int u_size = edge[u_idx].size();
  for (int i=0;i<u_size;i++){
    int v_idx = edge[u_idx][i];
    if (d[v_idx]>d[u_idx]+1){
      d[v_idx] = d[u_idx] + 1;                    
    }
    heap.push({d[v_idx], v_idx});     // 有重复计算   
  }            
}

if (d[end_idx]>n_words-1){      
  return 0;
}
return d[end_idx] + 1; 
}

备注: c++ stl 的 priority-queue 没有所谓的 decrease-key 操作接口（算法导论里面关于堆的设计下有。）因此，我们使用 lazy-deletion 来解决这个问题，即如代码所示，insert 更小的元素来代替 decrease key，在取出时候进行判断（第一次取出仍然是想要的结果）。虽然时间和空间都有少量的冗余，但综合来看，还是比自己手动实现一个新优先队列，在实际工作中更经济。

详细介绍也可以看这里

小结

整体来看，该算法实现起来还是比较简单的，在此基础上还有一些类似 A-star 之类的算法变种，也可以深入了解一下。

使用时注意几个要点

图中不能有负系数的自环
稀疏图时采用堆结构来优化性能（当然斐波那契堆可能可以更快，但就比较难理解）
时刻注意剪枝，可以大幅提高性能

对于类似规则地图之类的搜索(每个顶点只有有限条边，且权重有规则)，可能实现起来还会更简单一些。

Liufeng's Blogs