TOC
图论
最小生成树需要你掌握基本的图论 在书的附录中有介绍，可以先去看看 设 V 为 有向图（v,e）的顶点集 那么遍历这个图的成本为 O(V ^ 2) 如果一个有向图 G=(V,E)是连通的 那么他的边必然大于等于他的顶点数
在计算机中表现图的常见方法
- 邻接矩阵 说白了就是一个 n*n 的表格 其中 arr[i][j] == 1 就代表连通 0 代表不联通。 他的特点在于比较适合稠密图，不适合稀疏图，常年占据
V ^ 2的空间，如果稀疏不太划算。 - 邻接表 比如顶点 a 与 c b d 邻接 那么就表示为 a{c,b,d} 相比较矩阵而言，空间大幅度减少，等于这个图的总度数 _ 顶点数 =
O(E _ V)（无向图情况下），如果是有向图则为O(E)。
握手定理
我们把某个顶点所邻接的数量称之为度，而每一次邻接就会让两个顶点都增加一点的度，所以总度会等于顶点都数量 X2
贪心算法
贪心法，又称贪心算法、贪婪算法、或称贪婪法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。[比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。
贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。
贪心算法与动态规划的不同在于它对每个子问题的解决方案都做出选择，不能回退。动态规划则会保存以前的运算结果，并根据以前的结果对当前进行选择，有回退功能。
贪心法可以解决一些最优化问题，如：求图中的最小生成树、求哈夫曼编码……对于其他问题，贪心法一般不能得到我们所要求的答案。一旦一个问题可以通过贪心法来解决，那么贪心法一般是解决这个问题的最好办法。由于贪心法的高效性以及其所求得的答案比较接近最优结果，贪心法也可以用作辅助算法或者直接解决一些要求结果不特别精确的问题。
活动选择问题
在书中首先介绍了这么一类问题，即每个活动都有开始和结束时间，在同一时间的只能执行一个，我们需要在这些活动中选出一个最大活动集合，并且他们必须相互兼容，即互不冲突，在书中，这种问题的准确名称是 调度竞争共享资源的多个活动问题 。
这个问题点关键在于，只要你在每一步找出最早结束的活动，这个活动永远是整个最终的最佳选择里面的一部分，所以这个问题能够使用贪心算法来解决,值得注意点就是结束列表与开始列表必须 11 对应，比如 s[1]和 f[1]两个其实代表的就是一个活动的开始时间与结束时间，并且顺序必须与结束时间为准，这也就是为什么找到一个开始时间小于上一个活动那个结束时间马上可以跳出的原因，因为这时候这个活动必然与上个活动不冲突并且结束时间最早。
const startActList = [0, 1, 3, 2, 7, 8, 9]
const endActList = [0, 3, 6, 8, 9, 10, 14]
// 为了免除初始化从 0 开始 m = 0 + 1 直接跳过第一组的问题 在前面填充一个虚值0
/**
@param {s:Array} 活动开始时间列表 有序 与结束对应关系
@param {f:Array} 活动的结束时间列表
@param {k:Number} 当前的求解的子问题 你可以认为是最终列表里第n个目标活动 初始化为0
@param {n:Number} 活动的子规模 随着k的变化 可能会大幅降低
*/
function ACTIVITY_SELECTOR(s, f, k, n) {
let m = k + 1 // 当前需要判断的活动
while (m <= n && s[m] < f[k]) {
m++ // 再当前子问题中寻找结束最早 并且与当前活动不冲突的活动
}
if (m <= n) {
return [m].concat(ACTIVITY_SELECTOR(s, f, m, n))
}
return []
}
const result = ACTIVITY_SELECTOR(
startActList,
endActList,
0,
endActList.length - 1
)
console.log(result) // [ 1, 2, 4, 6 ] 也就是说 活动开启顺序为 a1{1:3} > a2{3:6} > a4{7:9} > a6{8:10}
贪心选择性质
贪心选择性质是贪心算法最重要的性质之一，并且也是他和动态规划最大的区别
我们可以通过做出局部最优选择来构造全局最优解，其实就是每次都找眼前最好的，不去考虑子问题。通常来讲，贪心算法一般都是自顶向下，同时只存在一个子问题，随着算法的深入，这个子问题的规模将会逐渐减小，直到完成。而动态规划一般都是自底向上，填表式的操作。如果你发现某个问题会出现大量重叠子问题，那么很可能他只能用动态规划来解决。
最小生成树
首先 你有一个连通的无向图 G = (V,E) 一个给边加权的函数 W 他给每一条边都加一个实数的权重值 (假设他内映射的 也就是说对每一条边得出的权重都不相同) 输出一个树 这个树连接了所有顶点，并且他的所有边的权重的总和必须最小
最小生成树的特性
首先一颗最小生成树是拥有最优子结构的特性的
假设我们拥有一个一颗最优子结构树 T 并切断他的一组连通关系 使得这棵树 T 变成两颗互不联通的树 T1 T2 这时候你将这两个树进行反向生成 也就是把所有的节点重新连接起来 反向推导出一个图 G1 G2 在这种情况下，T1 将会是 G1 的最小生成树 T2 也是图 G2 的最小生成树
书中的证明似乎就是利用矛盾关系，假设拥有一颗更加低权重的最小生成树，那么我们本身最小生成树这个命题就不成立。
并且他还拥有重叠子问题
一个树可以被多次拆分 多种拆分方式 所以会出现很多类似的子树,并且他拥有如下定理
定理
设 T 为一颗最小生成树 设 A 为 V 的一个子集 也就是顶点的子集 设 边 (u,v) 为拥有最小权重的一条边 那么 (u,v) 是 T 中的一条边 例子 从 A 的局部角度看，和他链接的边中 找出一个最小权重的边那么这个边就存在于 T 中
也就是说这个算法是拥有贪心选择性质的
最小生成树的实现
接下来介绍记录两种最小生成树算法的实现，两者其实都利用了安全边的概念，即每一次都去寻找一个必然在最终结果中的一条边，也就是当前能找到的权重最小的边。不断的将安全边存放到集合 A 中 其中 Kruskal 算法中集合 A 是一个森林（在算法进行的过程中不断进行合并，在算法完成的那一刻变成一个最小生成树） 而 Prim 算法中的集合 A 是一棵树（在算法进行过程中不断生长，最终变成完整的最小生成树）
由于篇幅实在太大，这里就只记录出书中的伪代码但会进行一些解读注释
Kruskal 算法
MST_KRUSKAL(G,w) // G为图 W是权重函数
A = Null // 初始化为空
for each vertex v G.V // 遍历图中的所有边
MAKE_SET(v) // 创建v颗树 每棵树内部只有一个节点
// 对图中所有的边进行排序
for each edge(u,v) // 遍历权重最小的边 与上面的建立关联 其实就是n*n的遍历
if FIND-SET(v) !== FIND-SET(u) // 如果这条边的两个节点不属于同一棵树
A = A U (u,v) // 将这边加入到森林中
UNION(u,v) // 合并两棵树
return A
其实一开始 A 将会是一颗很散的森林，算法会不断寻找权重较最低的边，将其加入合并到集合 A 中
Prim 算法
MST_PRIM(G,w,r) //G图 w权重函数 r初始点
for each u = G.V // 遍历图中所有节点 并把他们的值设置为正无穷 π为空
u.key = infinity //key会代表该节点的所有边中最小的权重值
u.π = null // π会代表该节点的父节点 一个指针
r.key = 0
Q=GV // 建立一颗由所有边组成的优先队列
while Q !== null
u = ex-min(Q) // 从优先队列中取出一个当前key最小的节点
for each v G.adj[u] // 找出与节点U相连的所有节点
if(v 属于 Q && w(u,v) < v.key) // 两点相连 如果权重小于U的key 并且属于堆中
v.π = u // 设置这个节点的父节点为u
v.key = w(u,v) // 设置key为新的权重值
// 这个操作将会导致每个V在优先队列中的位置不断更新 拥有越低权重的v将会更有机会被添加到集合A中
这里面的 Q 就像一个动态的优先池，里面的顺序会不断的变化，可以说节点的 KEY 属性就代表了这个节点的插入优先级，并且随着算法的深入，更多的节点将被检测他的优先级。 到最后，所有的节点都将会被探测完成。
代码实现（python）
首先是一组优先队列模块，最近在学 python，使用起来走了不少弯路。
# q.py
import math
def left(i): return 2 * i
def right(i): return 2 * i + 1
def parent(i): return math.floor(i / 2)
def MIN_HEAPIFY(A, heapSize, i):
l = left(i)
r = right(i)
cur = A[i]
minimum = i
if(l <= heapSize and cur['key'] > A[l]['key']):
minimum = l
if(r <= heapSize and A[minimum]['key'] > A[r]['key']):
minimum = r
if(minimum != i):
temp = A[i]
A[i] = A[minimum]
A[minimum] = temp
MIN_HEAPIFY(A, heapSize, minimum)
def BUILD_MIN_HEAP(A, heapSize):
i = math.floor(heapSize / 2)
for i in range(i, -1, -1):
print(i)
MIN_HEAPIFY(A, heapSize, i)
class Q:
def __init__(self, arr):
self.heap = arr[:]
self.heapSize = len(arr) - 1
BUILD_MIN_HEAP(self.heap, self.heapSize)
def getMinimun(self):
return self.heap[0]
def extHeapMin(self):
if(self.heapSize < 0):
return False
min = self.heap[0]
self.heap[0] = self.heap[self.heapSize]
self.heapSize -= 1
MIN_HEAPIFY(self.heap, self.heapSize, 0)
return min
def incrHeapKey(self, i, key):
if(key > self.heap[i]['key']):
return False
self.heap[i]['key'] = key
while(i > 0 and self.heap[parent(i)]['key'] > self.heap[i]['key']):
p_i = parent(i)
temp = self.heap[i]
self.heap[i] = self.heap[p_i]
self.heap[p_i] = temp
i = p_i
def insert(self, value):
self.heapSize += 1
self.heap.append(value)
self.incrHeapKey(self.heapSize, value['key'])
def has(self, name):
for i in range(0, self.heapSize):
if(self.heap[i]['name'] == name):
return True
return False
def isEmpty(self):
if(len(self.heap) <= 0 or self.heapSize < 0):
return True
return False
def findIndex(self, name):
index = -1
for i in range(0, self.heapSize):
if(self.heap[i]['name'] == name):
index = i
return index
核心
import q
my_nodes = [
{'name': 'a'}, {'name': 'b'}, {'name': 'c'}, {'name': 'd'}, {
'name': 'e'}, {'name': 'f'}, {'name': 'g'},
{'name': 'h'}, {'name': 'i'}
]
Gap = [
[0, 4, 0, 0, 0, 0, 0, 8, 0],
[4, 0, 8, 0, 0, 0, 0, 11, 0],
[0, 8, 0, 7, 0, 4, 0, 0, 2],
[0, 0, 7, 0, 9, 14, 0, 0, 0],
[0, 0, 0, 9, 0, 10, 0, 0, 0],
[0, 0, 4, 14, 10, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 2, 0, 1, 6],
[8, 11, 0, 0, 0, 0, 1, 0, 7],
[0, 0, 2, 0, 0, 0, 6, 7, 0]
]
def mst_prim(g, nodes, start):
for index, i in enumerate(nodes):
i['key'] = float('inf')
i['p'] = None
i['index'] = index
nodes[0]['key'] = 0
nodeQ = q.Q(nodes)
while(not nodeQ.isEmpty()):
u = nodeQ.extHeapMin()
for index, i in enumerate(g[u['index']]):
cur = nodes[index]
# 中间检测 heapSize 是因为循环到最后一个节点的时候，所有其他节点都已经从队列中删除完毕了
# 所以在检测到最后一个的时候 需要放宽条件
if(i != 0 and (nodeQ.has(cur['name']) or nodeQ.heapSize == 0) and i < cur['key']):
cur['p'] = u
index = nodeQ.findIndex(cur['name'])
nodeQ.incrHeapKey(index, i)
mst_prim(Gap, my_nodes, 0)
print(my_nodes)
节点的连接情况为了方便检查正确性都是从书上参考的。书中的伪代码其实没有考虑到最后一个节点并不能去做松弛操作的问题，我在实际的实现中发现了这个问题。我不知道有没有更加优秀的解决办法。总得来说难度并不是非常高，其逻辑很类似 dj 最短路径算法。我感觉这个就是松弛操作啊