本文为个人学习笔记(更新完毕) 如果觉得写的不错欢迎点赞收藏交流 如有疑问和建议欢迎留言或者私信
假设有n个信号塔用于播放海啸警告，坐标为（x,y），半径为r，信号塔发射型号后，辐射区域内的信号塔也会被激活。 给其中一些塔配备地震传感器，传感器可以使得该塔被激活。当所有塔激活便可以播放海啸警告。 怎样分配可以让地震传感器数量最少？
解决这个问题前回顾几个概念。
给定有向图 G = ( V , E ) G = (V,E) G=(V,E), 怎么求 v ∈ V v \in V v∈V的强连通分量C？
建立一个新有向图 G ′ = ( V , E ′ ) G' = (V, E') G′=(V,E′)，V与G相同，E‘ 则是G中的E的反向。利用BFS寻找到点集合 D ⊆ V D \subseteq V D⊆V, D中所有的点在 G G G中都可以从v出发寻到利用BFS寻找到点集合 R ⊆ V R \subseteq V R⊆V, R中所有的点在 G ′ G' G′中都可以从v出发寻到求得 C = D ∩ R C = D \cap R C=D∩R定义一个图： ∑ = ( S G , E ∗ ) \sum = (S_G, E^*) ∑=(SG,E∗) 其中， S G S_G SG是G中所有强连通分量的集合，对任意 σ 1 , σ 2 ∈ S G 且 σ 1 ≠ σ 2 \sigma_1, \sigma_2 \in S_G \ 且 \sigma_1 \neq \sigma_2 σ1,σ2∈SG 且σ1=σ2都存在 σ 1 → σ 2 ∈ E ∗ \sigma_1\to\sigma_2 \in E^* σ1→σ2∈E∗ 注意， σ 1 → σ 2 \sigma_1 \to \sigma_2 σ1→σ2表示存在点 u 1 ∈ σ 1 , u 2 ∈ σ 2 u_1 \in \sigma_1 , u_2 \in \sigma_2 u1∈σ1,u2∈σ2在E中有 u 1 → u 2 ∈ E u_1 \to u_2 \in E u1→u2∈E
很显然，图 ∑ \sum ∑是一个有向无环图（DAG），因此我们可以对其进行拓扑排序，拓扑排序后的DAG，所有edges都是从左至右。
初始化 空表L 用于存放即将排序好的元素 初始化 S 用于存放所有的点 ‘’’
while S not empty： 从S中移除点u 将u加入L尾部 for 对每个有e = (u,v)的v点： 从图中中移除e if v点没有edge了，插入S中 if 图还有edge，返回error(图像有环) else: return L‘’’
所以针对信号塔的问题，我们便可以通过先求出G的所有强连通分量，组成DAG，然后进行拓扑排序的方式解决。
有向图 G = ( V , E ) G = (V,E) G=(V,E), 每个edge都有非负权重w，给一个vertex v ∈ V v \in V v∈V，假设对所有 u ∈ V u \in V u∈V都有一条从v 到 u的路径，如何找到从v到所有 u ∈ V u \in V u∈V的最短路径？
首先我们要证明一点： 假定从点v到点z的最短路径为p， 对于路径p上的每个点w，从v到w的最短路径就是p路径在w的截断。
利用反证法， 存在一个v到w最短路径p1不是这个p的截断，此时我们便可以移除从p上从v到w的截断，利用这个p1取而代之，得到新的最短路径p*，与条件是v到z的最短路径矛盾。
以此为算法的贪心规则： 每一段都尽量找到v点到其他点的最短路径。我们有如下算法
设置 S = {s} ，对每个S中的点u, 存储一个距离d(u)，d(s) = 0 while S ！= V： 选择一个不在S中的点v, 使得从S到v至少有一条边e=(u,v)且 d'(v) = d(u) + length(e) 最小 将 u 加入 S并且 d(u) = d'(u) endwhile反证法， 假设G中存在从v到u的更短的路径，这条路径不由我们算法得出，根据我们的算法，我们选择的u都存在于S中，所以这条路径肯定不会全部在S中，我们假设这个不在S中的第一个点为点z，那从v到z的路径应该会比v到u更短，那我们的算法应该会选择z而不是u，矛盾。
我们需要优先队列来更有效的改变队列中键的改变。 首先我们有一个heapbased 优先队列结构A，A[i] 左孩子 A[2i] 右孩子A[2i+1] 存在A中的元素形式为 (i, k(i)), k(i)为元素i的key 另外一个array P，与A同长，存取A中每个元素的位置A[P[i]] = (i,k(i))
所以，当我们改变一个元素i的key，需要O（logn）操作: 首先查询 A[ P[i] ]然后改变A[ P[i] ] 元素中的 key，执行heappify操作保留堆属性。
一个优选队列可以有效地插入元素，删除元素，改变元素key（changekey），取出具有最小key的元素(extractmin)
起点为s，对于 u ∈ V a n d u ≠ s u \in V \ and\ u \neq s u∈V and u=s, 我们把 ( u , d ′ ( u ) ) (u, d'(u)) (u,d′(u))放入优先队列， 执行extractmin找出 d ′ ( u ) d'(u) d′(u)最小的点u加入S。 令点 w ∉ S w \notin S w∈/S是在优先队列中一个剩余的点， v ∈ S v \in S v∈S, 如果 ( v , w ) ∈ E (v,w) \in E (v,w)∈E, 则 d ′ ( w ) = m i n ( d ′ ( w ) , d ( v ) + l ( v , w ) ) d'(w) = min(d'(w), d(v) + l_{(v,w)}) d′(w)=min(d′(w),d(v)+l(v,w))，这一步就可能用到changeKey操作将w加入S，这个changeKey操作每条边最多出现一次
总的来说使用优先队列，Dijkstra算法可以在n个节点m个边的图上，运行O（m）时间，加上n次Extractmin和m次changekey时间，一共是O（mlogn）时间
连通图G的子图，拥有与G相同的点和最小长度的边，该子图为G的最小生成树
定理： 假设所有边费用不等，令S为G任意节点的非空真子集，令边e = (u,v)是一端在S，一端在V-S中的最小费用边，则所有的最小生成树都一定包含e 证明
反证法，假设存在一个不包含e = (u,v)的最小生成树TT是生成树，所以必定存在一条从u到v的路径因为 u ∈ S a n d v ∉ S u \in S\ and\ v \notin S u∈S and v∈/S, 所以路径一定经过S假设该路径在S中的最后一个点为点p, 下一个为点 q ∉ S q \notin S q∈/S边 ( p , q ) ∈ T (p,q) \in T (p,q)∈T的费用一定大于e=（u，v）（e的假设）将e加入此路径，则形成了一个 u → p → q → v → u u\to p\to q\to v\to u u→p→q→v→u的循环移除(p,q)，形成了一个新的生成树T*根据假设，e = (u,v)的费用比（p，q）更小， T与T的差别在于后者少了（p，q）多了（u,v），所以T是总费用比T更小的生成树，与T是最小生成树的假设矛盾Kruskal算法会生成最小生成树，如果所有边长度不同，则生成的最小生成树唯一 证明
设一条边 e = ( u , v ) e=(u,v) e=(u,v)被算法加入生成树在e加入前的一刻，从u点有路径通向某些结点，设这些结点集合S显然,此时 u ∈ S b u t v ∉ S u \in S \ but\ v \notin S u∈S but v∈/S，因为加入 ( u , v ) (u,v) (u,v)不会在S内构成环此时已经不存在一条 一端在S一端在S外 的边，因为如果这样的边存在且加入不会构成圈，那他肯定会被算法加入S因此， e = ( u , v ) e=(u,v) e=(u,v)便是一端在S一端在S外中最便宜的边，根据3.1.1的定理，它属于最小生成树。MakeUnionFind(S): 返回集合S上的一个Union-Find结构，其中所有元素都被放置在一个分离的单独的集合中： S = ( a , b , c ) → ( ( a ) , ( b ) , ( c ) ) S=(a,b,c) \to ((a),(b),(c)) S=(a,b,c)→((a),(b),(c)) 运行时间： O(n), n=|S|
Find(v)： 给定元素v，返回元v所属的集合, 运行时间：O(logn)。某些实现对这个操作实际上只需要O(1)
Union(A,B): A ∪ B A \cup B A∪B代替A,B集合，改变结构。运行时间：O(logn) 而k个连续Union操作运行时间为O(klogk)（接下来解释）
我们只看k个连续Union操作运行时间，是因为平均分析下来每个操作只需要O(logk)的时间而不是O(logn)
Union(i,j)操作被定义为：（元素数量少的被更新）
如果标签i集合的元素数量大于等于标签j集合，则A中标签为 j 的元素都被改成i，B也随之更新如果标i集合的元素数量少于标签j集合， 则A中标签为 i 的元素都被改成j，B也随之更新根据定义，假设Union操作改变元素m的标签，则产生的新集合的元素数量至少是被更新前元素m所在集合的元素数量的两倍
任何k个连续Union操作都会触及最多2k个S中的元素（应用在MakeUnionFind操作后产生的分离集合中），因此，一个经过k个连续Union操作后包含元素m的集合最多包含2k个元素。
因为每个union操作都会将包含元素m的集合的大小至少扩充一倍, 最多扩充到2k个元素，这意味着包含元素m的集合的标签最多被改变log2k次。
我们一共有最多2k个元素，所以总共经过k个连续union操作的后我们的A最多有 2 k × l o g 2 k 2k\times log2k 2k×log2k次的标签改变，B的话只有一些指针改变和集合大小改变。 因此，经过k个连续UNION操作的时间复杂度为O(klogk)
G = ( V , E ) G = (V,E) G=(V,E), 有n个点，m条边。
给m条边按长度排序,因为 m < = n 2 m<=n^2 m<=n2， 时间为O(mlogm)=O(mlogn)我们运行Kruskal算法，S是所有连通分量的分离集合（MakeUnionFind），然后通过（Union）操作将满足算法要求的连通分量合并，将S慢慢变成所有包含所有结点的连通分量集合。对于e=(u,v)，我们通过Find(u)和Find(v)来判断u,v是否属于同一连通分量。如果 F i n d ( u ) = i ≠ F i n d ( v ) = j Find(u)=i \neq Find(v)=j Find(u)=i=Find(v)=j，我们就添加e进入最小生成树（执行Union(i,j)，u,v的标签统一，从此同属一个连通分量）该算法执行2m次Find操作，每次操作O(1)，共O(m)；执行n-1次Union操作，共O(nlogn)； 排序边共O(mlogn)；总体时间复杂度为O(mlogn)
