prim算法：最小生成树
https://www.bilibili.com/video/BV1Eb41177d1?spm_id_from=333.337.search-card.all.click
强推，一下看懂了
在图论和网络连接问题中，最小生成树（Minimum Spanning Tree，MST）是一个常见的问题。最小生成树是一个连接无向图中所有顶点的树，它的边具有最小的总权重。Prim算法是一种流行的算法，用于寻找图的最小生成树。本篇博客将深入介绍Prim算法的工作原理、应用场景以及提供Python代码示例，以便读者更好地理解和应用该算法。
Prim算法概述
Prim算法是一种贪婪算法，用于构建图的最小生成树。它的工作原理相对简单但非常有效。以下是Prim算法的基本思想：
- 选择一个初始顶点，将其标记为已访问。
- 从已访问的顶点集合中选择一条边，该边的权重最小并且连接到未访问的顶点。
- 将该边添加到最小生成树中，并将连接的顶点标记为已访问。
- 重复步骤2和3，直到最小生成树包括了图中的所有顶点。
Prim算法的主要优点是它适用于连接稠密图，而且其复杂度较低。
代码
_ = float('inf') # 正无穷 def prim(graph,n): dist=[_]*n # 记录最短权值 visit=[False]*n # 记录是否连通(去过) preIndex=[0]*n # 记录每次寻找的起点 # # 第一个顶点 # visit[0] = True # for i in range(n): # 相邻的边权值 # dist[i] = graph[0][i] # 找到当前无向图的最小生成树 for i in range(n): mindist=_+1 nextIndex = 0 # 扫描Scan：找到基于当前i，i行中哪一列距离最小作为下一个节点，前提是那个节点没有去过 for j in range(n): if dist[j]< mindist and not visit[j]: # visit[j] == False mindist = dist[j] nextIndex =j visit[nextIndex]= True # 添加Add # 更新Update：由于前面找到下一个节点了，下面构建下一个节点的dist矩阵，要看nextIndex这一行 for j in range(n): if dist[j]>graph[nextIndex][j] and not visit[j]: # visit[j] == False dist[j]=graph[nextIndex][j] preIndex[j]=nextIndex return dist,preIndex if __name__=='__main__': n=6 # A到B的权重是6 graph=[[0,6,3,_,_,_], [6,0,2,5,_,_], [3,2,0,3,4,_], [_,5,3,0,2,3], [_,_,4,2,0,5], [_,_,_,3,5,0]] dist,preIndex=prim(graph,n) print(dist) print(preIndex)
[inf, 2, 3, 3, 2, 3] [0, 2, 0, 2, 3, 3]
这段代码首先创建了一个Graph类，表示一个包含5个顶点的图。
然后，它使用邻接矩阵来表示图的边。
在prim_mst方法中，算法从顶点0开始，逐步添加边以构建最小生成树，并最终打印出最小生成树的边和权重。
可以根据自己的需求修改图的大小和权重来测试算法。
结语
Prim算法是寻找最小生成树的强大工具，适用于许多实际问题。
通过了解和应用Prim算法，可以更好地解决与网络和连接有关的问题，优化资源分配，提高效率，以及改善城市规划和通信网络。
算法提高 最小生成树
给定带权无向图，求出一颗最小的生成树。
输入格式：
输入多组测试数据。第一行为N,M，依次是点数和边数。接下来M行，每行三个整数U,V,W，代表连接U,V的边，和权值W。保证图连通。n=m=0标志着测试文件的结束。
输出格式：
对于每组数据，输出方差，四舍五入到0.01。输出格式按照样例。
代码
# 图初始化 N,M = map(int,input().split()) _ = float('inf') graph =[[_ for i in range(N)]for i in range(N)] # 读图 for i in range(M): U,V,W = map(int,input().split()) graph[U-1][V-1] = W for i in range(N): graph[i][i] = 0 print(graph)
4 5 1 2 1 2 3 2 3 4 2 4 1 1 2 4 3 [[0, 1, inf, inf], [inf, 0, 2, 3], [inf, inf, 0, 2], [1, inf, inf, 0]]
# 读图 _ = float('inf') def Prim(graph,n): dist=[_]*n #记录最短权值 preIndex=[0]*n #记录出发点 visit=[False]*n #记录是否访问过 for i in range(n): # 扫描Scan mindist = _ nextIndex = -1 for j in range(n): if dist[j] < mindist and not visit[j]: mindist = dist[j] nextIndex = j # 添加Add # preIndex[i] = nextIndex visit[nextIndex] = True # 更新Update for j in range(n): if dist[j] > graph[nextIndex][j] and not visit[j]: dist[j] = graph[nextIndex][j] preIndex[i] = nextIndex return dist,preIndex if __name__=='__main__': n=6 # A到B的权重是6 graph=[[0,6,3,_,_,_], [6,0,2,5,_,_], [3,2,0,3,4,_], [_,5,3,0,2,3], [_,_,4,2,0,5], [_,_,_,3,5,0]] dist,preIndex=prim(graph,n) print(dist) print(preIndex)
[inf, 2, 3, 3, 2, 3] [0, 2, 0, 2, 3, 3]
小结
① 二维数组初始化 graph =[[_ for i in range(N)]for i in range(N)]
② 初始化。一个访问与否bool visit，一个起始节点，一个最短路径。
③ 扫描Scan，添加Add，更新Update
解密动态规划
动态规划（Dynamic Programming，简称DP）是计算机科学中一种强大的算法范式，用于解决各种复杂问题，从最优化和路径查找到字符串处理和机器学习。这篇博客将详细介绍动态规划的概念、原理、应用场景以及提供一些示例，帮助读者深入了解这一重要的算法技术。
什么是动态规划？
动态规划是一种解决问题的方法，它将问题分解成一系列子问题，然后将子问题的解保存起来，以避免重复计算。这种分治和记忆的方式使动态规划成为解决许多复杂问题的有效工具。
动态规划通常适用于满足两个条件的问题：
- 重叠子问题（Overlapping Subproblems）：问题可以被分解为子问题，这些子问题在解决原问题时出现多次。因此，我们可以通过记忆子问题的解来避免重复计算。
- 最优子结构（Optimal Substructure）：问题的最优解可以通过子问题的最优解来构建。也就是说，问题可以分解成子问题的解，然后通过这些子问题的解来构建原问题的解。
动态规划的基本步骤
动态规划通常涉及以下基本步骤：
- 定义子问题：将原问题分解成一系列子问题，其中每个子问题都是原问题的简化版本。
- 定义状态：确定如何表示子问题的状态，以便记忆和检索已解决的子问题。
- 递推关系：建立子问题之间的递归关系，以描述如何从一个子问题的解构建下一个子问题的解。
- 初始化：确定初始问题的解，通常是最简单的问题的解。
- 计算顺序：确定计算子问题解的顺序，通常是自底向上，从较小的子问题到较大的子问题。
- 返回结果：计算并存储原问题的解，通常是最大的子问题的解。
动态规划的应用场景
动态规划在计算机科学和工程中有广泛的应用，涵盖了多个领域，包括但不限于以下几个：
- 最短路径问题：用于寻找网络、地图或图中的最短路径，如Dijkstra算法和Floyd-Warshall算法。
- 字符串处理：用于解决字符串匹配、编辑距离和编码问题，如编辑距离算法和最长公共子序列算法。
- 最优化问题：用于寻找最优解决方案，如0/1背包问题、旅行商问题和线性规划。
- 自然语言处理：用于处理自然语言文本、机器翻译、语音识别和文本生成。
- 计算生物学：用于分析DNA、蛋白质和基因组数据，如Smith-Waterman算法和Phylogenetic树的构建。
- 机器学习：用于强化学习、推荐系统和回归分析等。
动态规划的示例
以下是一个经典的动态规划示例：斐波那契数列的计算。
def fibonacci(n): fib = [0] * (n + 1) fib[0] = 0 fib[1] = 1 for i in range(2, n + 1): fib[i] = fib[i - 1] + fib[i - 2] return fib[n] n = 10 print(f"The {n}-th Fibonacci number is {fibonacci(n)}")
这段代码使用动态规划计算了第n个斐波那契数，避免了递归中的重复计算，提高了效率。
手写笔记
