图算法--深度优先/广度优先/最小生成树/最短路径_tremaux演算法

1. 深度优先搜索

1.1 标记法探索迷宫

探索迷宫而不迷路的一种古老办法叫做Tremaux搜索（标记法），要探索迷宫中的所有通道，我们需要：

1. 选择一条没有标记过的通道，在你走过的路上铺一条绳子；
2. 标记所有你第一次路过的路口和通道；
3. 当来到一个标记过的路口时（用绳子）回退到上个路口；
4. 当回退到的路口已没有可走的通道时继续回退。

绳子可以保证你总能找到一条出路，标记则能保证你不会两次经过同一条通道或者同一个路口。

1.2 深度优先搜索算法

和Tremaux搜索类似，深度优先搜索，只需用一个递归方法来遍历所有顶点。在访问其中一个顶点时：

1. 将它标记为已访问；
2. 递归地访问它的所有没有被标记过的邻居顶点。

2. 广度优先搜索

问题是这样：给定一幅图和一个起点s，回答“从s到给定目的顶点v是否存在一条路径？如果有，找出其中最短的那条（所含边数最少）。”

2.1 广度优先搜索算法

广度优先搜索是这样的：要找到从s到v的最短路径，从s开始，在所有由一条边就可以到达的顶点中寻找v，如果找不到我们就继续在与s距离两条边的所有顶点中查找v，如此一直进行。

在程序视线中，我们一般使用一个队列来保存所有已经被标记过但其邻接表还未被检查过的顶点。

1. 先将起点加入队列，然后重复以下步骤直到队列为空：
2. 取队列中的下一个顶点v并标记它；
3. 将与v相邻的所有未被标记过的顶点加入队列。

2.2 广度优先搜索和迷宫最短路径

广度优先搜索正是为了寻找迷宫的最短路径才出现的，因为：

1. 队列总是包含零个或多个到起点的距离为k的顶点，之后是零个或多个到起点的距离为k+1的顶点，其中k为整数，起始值为0
2. 这意味着顶点是按照它们和s的距离的顺序加入或者离开队列的
3. 从顶点v加入队列到它离开队列之前，不可能找出到v的更短的路径
4. 而在v离开队列之后发现的所有能够到达v的路径都不可能短于v在树中的路径长度

3. 最小生成树

图的生成树是它的一棵含有其所有顶点的无环连通子图。
一幅加权图的最小生成树（MST）是它的一棵权值（树中所有边的权值之和）最小的生成树。

最小生成树算法在设计各种类型的网络中都起到了重要的作用。

3.1 树的性质

1. 用一条边连接树中的任意两个顶点都会产生一个新的环；
2. 从树中删去一条边将会得到两棵独立的树。

3.2 切分定理

在一幅加权图中，给定任意的切分，它的横切边中的权重最小者必然属于图的最小生成树。

令e为权重最小的横切边，T为图的最小生成树。我们采用反证法：

1. 假设T不包含e。
   1.1 那么如果将e加入T，得到的图必然含有一条经过e的环
   1.2 且这个环至少含有另一条横切边——设为f, f的权重必然大于e。
   1.3 那么我们删掉f而保留e就可以得到一棵权重更小的生成树。
2. 这和我们的假设T矛盾

3.3 最小生成树的贪心算法

切分定理是解决最小生成树问题的所有算法的基础。

使用切分定理找到最小生成树的一条边，不断重复直到找到最小生成树的所有边。

1. 首先从起点a开始，把a加入U集合
2. 然后，寻找从与a有关联的边中，权重最小的那条边并且该边的终点b在顶点集合：（V-U）中，我们也把b加入到集合U中，并且输出边（a，b）的信息，这样我们的集合U就有：{a,b}，
3. 然后，我们寻找与a关联和b关联的边中，权重最小的那条边并且该边的终点在集合：（V-U）中，我们把c加入到集合U中，并且输出对应的那条边的信息，这样我们的集合U就有：{a,b,c}这三个元素了
4. 依次类推，直到所有顶点都加入到了集合U。

如何才能（有效地）找到最小权重的横切边呢？Prim算法使用一条优先队列MinPQ＜Edge＞来根据权重比较所有边。

每当我们向树中添加了一条边之后，也向树中添加了一个顶点。要维护一个包含所有横切边的集合，就要将连接这个顶点和其他所有不在树中的顶点的边加入优先队列。

class Solution:
    def minCostConnectPoints(self, points: List[List[int]]) -> int:
        from queue import PriorityQueue
        cal = lambda p1, p2: abs(p1[0] - p2[0]) + abs(p1[1] - p2[1])  # 计算曼哈顿距离的函数

        pq = PriorityQueue() 
        visit = set(range(len(points)))  # 待访问的节点集
        res = 0

        pq.put((0, 0))  # (distance, point_id)
        while visit:  # 当没有访问完所有节点 
            dis, now = pq.get()  # 获取优先队列中最小的项 => (到扩展集中某最近点的距离，某最近点的序号)
            if now not in visit:  # 已访问过的直接跳过
                continue
            visit.remove(now)  # 移除出待访问的节点集
            res += dis
            for i in visit:  # 构建扩展集，就是把当前点对所有未访问点的距离都求一遍
                # 以距离为cost丢进优先队列排序
                pq.put((cal(points[now], points[i]), i))
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

4. 最短路径

定义：在一幅加权有向图中，从顶点s到顶点t的最短路径是所有从s到t的路径中的权重最小者。

4.1 松弛技术

松弛这个术语来自于用一根橡皮筋沿着连接两个顶点的路径紧紧展开的比喻：放松一条边就类似于将橡皮筋转移到一条更短的路径上，从而缓解了橡皮筋的压力。

边的松弛：放松边v→w意味着检查从s到w的最短路径是否是先从s到v，然后再由v到w。

顶点的松弛：谨慎选择顶点，使得每次顶点松弛操作都能得出到达某个顶点的更短的路径，最后逐渐找出到达每个顶点的最短路径。

4.2 最优性条件

判断路径是否为最短路径的全局条件与在放松一条边时所检测的局部条件是等价的。

1. 令G为一幅加权有向图，顶点s是G中的起点
2. distTo[]是一个由顶点索引的数组，对于从s可达的所有顶点v，distTo[v]的值是从s到v的某条路径的长度，对于从s不可达的所有顶点v，该值为无穷大。
3. 当且仅当对于从v到w的任意一条边e，这些值都满足distTo[w]＜=distTo[v]+e.weight()时，它们是最短路径的长度。

必要性证明：
假设distTo[w]是从s到w的最短路径。如果对于某条从v到w的边e有distTo[w]＞distTo[v]+e.weight()，那么从s到w（经过v）且经过e的路径的长度必然小于distTo[w]，矛盾。因此最优性条件是必要的。

4.3 通用算法

将distTo[s]初始化为0，其他distTo[]元素初始化为无穷大，继续如下操作：

1. 放松G中的任意边，直到不存在有效边为止。

对于任意从s可达的顶点w，在进行这些操作之后，distTo[w]的值即为从s到w的最短路径的长度。

4.4 Dijkstra算法实现最短路径树

通用算法并没有指定边的放松顺序。

Dijkstra算法主要特点是从起始点开始，每次都会为最短路径树添加一条顶点，这点距离始点距离最近且未被访问过，直到扩展到终点为止。

要实现Dijkstra算法，需要一条优先队列，以保存需要被放松的顶点并确认下一个被放松的顶点。

public void dijkstra(int s, int t) { // 从顶点s到顶点t的最短路径
  int[] predecessor = new int[this.v]; // 用来还原最短路径
  Vertex[] vertexes = new Vertex[this.v];
  for (int i = 0; i < this.v; ++i) {
    vertexes[i] = new Vertex(i, Integer.MAX_VALUE);
  }
  PriorityQueue queue = new PriorityQueue(this.v);// 小顶堆
  boolean[] inqueue = new boolean[this.v]; // 标记是否进入过队列
  vertexes[s].dist = 0;
  queue.add(vertexes[s]);
  inqueue[s] = true;
  while (!queue.isEmpty()) {
    Vertex minVertex= queue.poll(); // 取堆顶元素并删除
    if (minVertex.id == t) break; // 最短路径产生了
    for (int i = 0; i < adj[minVertex.id].size(); ++i) {
      Edge e = adj[minVertex.id].get(i); // 取出一条minVetex相连的边
      Vertex nextVertex = vertexes[e.tid]; // minVertex-->nextVertex
      if (minVertex.dist + e.w < nextVertex.dist) { // 更新next的dist
        nextVertex.dist = minVertex.dist + e.w;
        predecessor[nextVertex.id] = minVertex.id;
        if (inqueue[nextVertex.id] == true) {
          queue.update(nextVertex); // 更新队列中的dist值
        } else {
          queue.add(nextVertex);
          inqueue[nextVertex.id] = true;
        }
      }
    }
  }
  // 输出最短路径
  System.out.print(s);
  print(s, t, predecessor);
}

private void print(int s, int t, int[] predecessor) {
  if (s == t) return;
  print(s, predecessor[t], predecessor);
  System.out.print("->" + t);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39