（本文为 latex 转 markdown 生成）
图在计算机中如何表示
邻接表
邻接表是一个链表的集合，链表的表头表示一个节点。比较适合存储稀疏的图。
例如，其中 1 到 3 有一条边，其权值为 3，则表示为
邻接表有边就记录，没边就不记录，这样很节省存储空间，不过邻接表也有缺点，当图比较稠密的时候，图中的边就特别多，链表中的元素也就特别多。链表上有除了数据域还有一个指针，相比邻接矩阵，这个指针完全是浪费空间的，它没有存储任何与图有关的内容。所以对于稠密图，邻接表的性能较低。
邻接矩阵
邻接矩阵是一个方阵，行和列的两组表头都是所有顶点。适合表示稠密的图，在这里讨论无向图。
比如说，一个图有 1，2，3，4，5 这些节点，那么就在行表头，列表头记 1，2，3，4，5；再将各边的权值记录在表中。实际在计算机中存储时，我们通常会用一个二维数组来表示。
例如，同上。其中 1 到 3 有一条边，其权值为 3，则在数组中的 [0][2] 赋值为 3，如
一般来说，我们使用权值来表示两个点之间的距离，如果两个点之间没有边，那么这两个点之间的距离可以视作无穷大。但在实际应用中，通常用一个很大的常量表示。
TSP 的暴力穷举解法
对于 n 个节点来说有 n! 个选择，计算出每条路径的权值和，并选其中最小的路径作为最佳路径。
解法：
-
将节点用邻接矩阵表示。
-
将 n 个节点进行排列，保存权值和。会有 n! 种结果。
-
用循环找出这 n! 个结果中最小的，保存到数组中，输出结果。
图上最小生成树问题
已知：边带权的连通图。
目标：找到一颗包含所有顶点的树，其权重最小。
邻域搜索
叙述
选择权值最小的边，加入到生成树中，不断迭代。从某一个顶点开始，不断扩展覆盖到连通图的所有节点。
-
图中所有的点集合为 V，生成树中的点集合 u={s}, 树外的点集合 v={V−u};
-
在两个集合 u 和 v 能组合成的边中，选择一条权值最小的边，加入到生成树中；并把连接这条边的 v 中的点加入到 u 中。
-
重复上述流程，直到生成树有 n-1 条边或 n 个顶点。
证明
使用归纳法进行可行性，最优性的证明。
-
第一次进行的边是权值最小的边，所以该解是最优解的其中之一。
-
假设前 s 个点满足要求，把连接这些点的边命名为 $n_1,n_2\dots n_{s-1}$ 设未确定最小边相连的已确定节点是 $n_k$。假设不是，那么，该未确定最小边一定和最小生成树构成回路，该回路某一边一定和 $n_1,n_2\dots n_{s-1}$ 中的两点相交，其中一点是 $n_k$，另一点设为 $n_i$，该回路中比存在与 $n_i$ 相邻的一条边比该未确定最小边大，用该未确定最小边代替这个比它大的这个边，结果仍然是生成树，该生成树比最小生成树还要小，这是矛盾的，因此，该未确定最小边一定是最优边。
-
综上，算法成立。
贪婪算法
叙述
初始最小生成树的边数为 0，每次迭代都选择一条可行的边加入到树中。
-
将图中的所有边按从小到大排列。
-
图中的 n 个顶点应看作 n 棵树，从小到大进行选择，所选边连接的两点应属于不同的树，将这两条树合并为一棵树。
-
重复上一步，直到生成树有 n-1 条边或 n 个顶点。
证明
使用反证法进行可行性，最优性的证明。
-
假定第 k 步首次出现了错误，算法选了 $E_1$，但实际上必须选另一条边 $E_2$ 才能得到最小生成树 $T_0$
-
$E_1$ 连接了两个连通分支，这两个连通分支在最终的 $T_0$ 里是连通的，所以把 $T_0$ 和 $E_1$ 放在一起之后形成的图有一个环，在这个环里一定有 k 步或之后新选的边（如果没有的话仅凭前 k-1 条边和 $E_1$ 不会构成环），依照 $E_1$ 的定义，这个环里存在比 $E_1$ 长的边，用 $E_1$ 换掉这条边之后得到的树 $T_1$ 比 $T_0$ 更短，矛盾
-
综上，算法成立。
利用最小生成树的结果找旅行路径
邻域搜索的扩展
-
确定起点
-
把已经访问过的作为 A，把未访问过的作为 B。最开始 A 只有起点，B 为所有其他点，寻找 A 与 B 的最短路径，并将这条边连接的点加入 A 中。
-
不断重复上述流程，直到 A 中有所有点。
贪婪算法的扩展
-
把所有边进行从小到大的排序。
-
把每个点按边的顺序依次添加，直到所有点都已经访问过。
-
找到其中的起点，从起点出发，输出结果。
利用最小生成树的结果找旅行路径
图顶点的深度优先搜索算法
-
确定顶点 V，作为起始点，并标记为已经访问过。
-
搜索所有与 V 相邻的点，判断这些点是否被访问过。如果存在未被访问过的点，则任选一点进行访问；如果没有未被访问过的点，则回退到上一次访问的点。
-
不断重复上一步，直到所有点都被访问。
遗传算法找最短路径
遗传算法将 “优胜劣汰，适者生存” 的生物进化原理引入优化参数形成的编码串联群体中，按所选择的适应度函数并通过遗传中的复制、交叉及变异对个体进行筛选，使适应度高的个体被保留下来，组成新的群体，新的群体既继承了上一代的信息，又优于上一代。这样周而复始，群体中个体适应度不断提高，直到满足一定的条件。遗传算法的算法简单，可并行处理，并能到全局最优解。
-
生成原始染色体种群
随机以 n 个数作为可行解（染色体），生成 n 个。
-
生成适应度函数
适应度函数在通常情况下求的是最大值，但在本文中是用来求最短路径的，所以取路程和的倒数作为适应度。
-
选择染色体
采用轮盘赌算法（$\mbox {染色体 i 被选择的概率} = \mbox {染色体 i 的适应度}{\div}\mbox {所有染色体的适应度之和}$) 产生父代染色体。
-
编码
把权值作为基因，n 个基因组合成一个染色体。
-
交叉
依概率选出偶数个染色体，将两个染色体的中间一段基因进行交换，以此生成 N - M 个自带染色体
-
变异
对上述 N - M 个染色体，随机选出染色体上的几个基因进行随机修改。
-
复制
对父代染色体中适应度较高的 M 个进行复制，作为子代。
-
解码
-
逐代进化
上述的经过交叉变异的 N - M 个染色体和经过复制的 M 个染色体作为子代，再重复操作不断进化。
总结
最小生成树
-
对于最小生成树的 Prim 算法，记一共有 v 个顶点，则时间复杂度为 $O (v^2)$。
-
对于最小生成树的 Kruskal 算法，记一共有 e 条边，则时间复杂度为 $O (e\log_{2}{e}) $。
-
对两种算法而言，点相对多的树宜采用 Kruskal 算法，边相对多的树宜采用 Prim 算法。
旅行商问题
Prim 算法和 Kruskal 算法扩展后不是最优解，两者为近似算法，是近似解。
近似算法所得出的近似解与实际最优解的近似比为 1 到 2 之间。
代码
例题图：
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 0 | 100 | 3 | 5 | 5 | 3 |
| 1 | 3 | 100 | 4 | 2 | 3 |
| 2 | 5 | 4 | 100 | 3 | 4 |
| 3 | 5 | 2 | 3 | 100 | 4 |
| 4 | 3 | 3 | 4 | 4 | 100 |
import numpy as np
# 邻域搜索算法的拓展，array 为邻接矩阵，first 为起点下标，n 为城市个数
def prim(array, first):
# a 为已访问过的城市列表
a = [first]
length = 0
n = len(array)
array_copy = [[0 for i in range(n)] for j in range(n)]
for i in range(0, n):
for j in range(0, n):
array_copy[i][j] = array[i][j]
copy = [array_copy[first]]
while len(a) < n:
# 下一个去的城市
new_to = np.argmin(copy[-1]) % n
a.append(new_to)
copy += [array_copy[new_to]]
for i in range(0, len(copy)):
for j in a:
copy[i][j] = 100
a.append(first)
for i in range(0, n):
length += array[a[i]][a[i + 1]]
print("Prim 结果为 " + str([i + 1 for i in a]) + "长度 " + str(length))
# 贪婪搜索算法的拓展，array 为邻接矩阵，first 为起点下标，n 为城市个数
def krul(array, first):
n = len(array)
length = 0
copy = [[0 for i in range(n)] for j in range(n)]
for i in range(0, 5):
for j in range(0, 5):
copy[i][j] = array[i][j]
a = []
while len(a) < n:
new_to = np.argmin(copy) % n
new_from = (np.argmin(copy) - new_to) // n
copy[new_from][new_to] = 100
copy[new_to][new_from] = 100
if new_to not in a and new_from not in a:
a.append(new_from)
a.append(new_to)
if new_to in a and new_from not in a:
a.append(new_from)
if new_to not in a and new_from in a:
a.append(new_to)
result = [i + 1 for i in a]
copy_result = result[:]
for i in copy_result:
if i != (first + 1):
result.pop(0)
result.append(i)
else:
break
result.append(first + 1)
for i in range(0, n):
length += array[result[i] - 1][result[i + 1] - 1]
print("Kruskal 结果为 " + str(result) + "长度 " + str(length))
if __name__ == '__main__':
array = [[100, 3, 5, 5, 3],
[3, 100, 4, 2, 3],
[5, 4, 100, 3, 4],
[5, 2, 3, 100, 4],
[3, 3, 4, 4, 100]]
prim(array, 1)
krul(array, 1)
运行结果：
Prim 结果为 [2, 4, 3, 5, 1, 2] 长度 15
Kruskal 结果为 [2, 4, 1, 5, 3, 2] 长度 18