网站建设树状图,在云服务器打建网站,有网站做点什么好,营销型科技网站三.贪心算法 文章目录 三.贪心算法1.贪心算法#xff1a;2.贪心算法中的经典问题#xff1a;1.找零问题2.背包问题3.买卖股票的最佳时机4.哈夫曼编码5.最小生成树—prim算法6.单源最短路径—Dijkstra算法 3.总结 1.贪心算法#xff1a;
①贪心算法的概念#xff1a; 贪心算…三.贪心算法 文章目录 三.贪心算法1.贪心算法2.贪心算法中的经典问题1.找零问题2.背包问题3.买卖股票的最佳时机4.哈夫曼编码5.最小生成树—prim算法6.单源最短路径—Dijkstra算法 3.总结 1.贪心算法
①贪心算法的概念 贪心算法就是不断选择在当前看来最好的选择也就是说贪心算法并不从整体最优考虑它所作出的选择只是在某种意义上的局部最优选择 虽然贪心算法不能对所有问题都得到整体最优解但在一些情况下即使贪心算法不一定能得到整体最优解其最终结果却是最优解的很好近似 ②贪心算法的选择
用贪心法求解问题要满足以下条件
贪心选择性 所求问题的整体最优解可以通过一系列局部最优的选择即贪心选择来达到——这是贪心算法可行的第一个基本要素也是贪心算法与动态规划算法的主要区别 最优子结构性质 当一个问题的最优解包含其子问题的最优解时称此问题具有最优子结构性质——最优子结构性质是该问题可用 动态规划算法 or 贪心算法 求解的关键特征 ③贪心算法与动态规划的差异 相同贪心算法和动态规划算法都要求问题*具有最优子结构性质 差异 动态规划算法通常以自底向上的方式解各子问题而贪心算法则通常以自顶向下的方式进行以迭代的方式作出相继的贪心选择—即每作一次贪心选择就将所求问题简化为规模更小的子问题
经典硬币问题 不能选择贪心必须要用动态规划解决
④贪心算法的步骤
从某一起点出发在每一个解决问题步骤中根据局部最优策略得到一部分解缩小问题规模将所有解综合起来 不难看出在以上的过程中由于贪心算法的策略都是当前最优解很显然高效和简介的代码自顶向下利用迭代拆解问题是它的最大优点 2.贪心算法中的经典问题
贪心算法是一种解决问题的思想由此列举出在以下几种常见问题中的贪心法
1.找零问题 钱币找零问题是一个简单的问题但也能很直观的体现出贪心算法的逻辑理念和思想 示例1
题目描述
假设商店老板需要找零n≥0元钱币的面额有100元50元20元5元1元如何找零使得所需的钱币数最少
输入描述
在第一行给出测试例个数 N代表需要找零的钱数1≤N≤105
输出描述
输出共有 5 行每一行输出数据输出找零的金额与数量详情看样例
**输入**
365**输出**
100:3
50:1
20:0
5:3
1:0思路分析
贪心法从最大硬币面值开始计算这一类面值可以找的最大金额每一类面值硬币的找零数量就是一个子问题同时汇总以达到总硬币数最小的目标 注意这里只需要考虑≤0时的不合法情况因为存在面值为1的货币 def charge(t,n):global dicif n0:return0
# 每一次让当前最大面值的金额达到最大数目for i in range(len(t)):cntn//t[i]dic[i]dic.get(i,cnt)n%t[i]return1t[1,5,20,50,100]
t.sort(reverseTrue) # 将数组逆序由大及小遍历
nint(input())
dic{}
if charge(t,n):for key,value in dic.items():print(f{t[key]}:{value})
else:print(无法找零)示例2
翻硬币
思路分析
由于题设默认给出的开始状态的硬币一定可以达到最终状态所以不判断不满足的情况如不同的硬币数为奇数时
贪心法*遇到不相同就立即改变当前位置*
在对开始和结束时状态初始化完成后遍历对应位置上的每一个数从第一个到倒数第二个其中’*’为1’o’为0 若对应位置上的数不相同则将该位置上的数变为end位置上的数再将后一位置上的数翻面 start[i1] abs(start[i1]-1) # 0-1 1-0 start[i]end[i]
def init(a):for i in input():if i *:a.append(1)else:a.append(0)start[]
end[]
init(end)
init(start)
cnt0
for i in range(len(end)-1):if start[i]!end[i]:start[i1] abs(start[i1]-1) # 0-1 1-0start[i]end[i] # 令其相等cnt1
print(cnt)2.背包问题 背包问题即有若干物品每个物品有自己的价值和重量背包有总重量问题就是怎样将背包装的最大价值背包问题也分很多种很多需要用动态规划才能得到最优解 贪心算法中的背包问题物品可以拆分的背包问题所谓可拆分就是物品不是一个整体并不是严格要求只能是装或不装的情况——也就是在选择物品i装入背包中时可以选择物品 i 的一部分而不一定要全部装入背包中 示例1
快乐司机
思路分析 题目给出了汽车核载重量为 w可供选择的物品的数量 n每个物品的重量为 gi, 价值为 pi很明显物品是可以拆分的因为可以只装入该物品重量的一部分 贪心法 由可拆分性可知要得到最大价值需要根据物品的性价比大小决定也就是单位重量下物品的价值 : ai[(pi/gi)gi]可以通过二维数组将每个物品的单价和重量放在一起储存 ①若剩余的容量能装下当前最大价值的物品则将其全部放入总重量 w-a[1] 总价值a[0]*a[1] ②若剩余的容量不能全部装下当前最大价值的物品则可以等效为物品足够多因此能装入的重量为 w(能装多少装多少)总价值w*a[0] def getmax(val_num,w):res0# a[0]是单价 a[1]是总重量for a in val_num:ya[0]*a[1]if wa[1]: # 如果能装下当前最大价值的所含物品总数w-a[1]resyif w0:return reselse: # 如果装不下全部可以看作是物品数量足够多resw*a[0] # 能装多少装多少return resn,wmap(int,input().split())
val_num[]
for i in range(n):g,pmap(int,input().split())val_num.append([p/g,g])
val_num.sort(keylambda x:x[0],reverseTrue)
print(%.1f%getmax(val_num,w))示例2
旅行家的预算
思路分析
贪心算法因为要使费用最低因此每一次要尽可能地找到最便宜的油价加油站在起点到终点之间的最便宜的站点加尽可能多的油——可拆解
贪心判断每经过一个点包括起点时假设在此点加满油后能走距离为D会有如下三种情况 若在所能走的D距离内都没有加油站比当前所在的加油站油价更便宜 则选择在此点加满油后到达 最近的下一个点 继续重复贪心判断 若在所能走的D距离内存在有加油站比当前的加油站油价更加便宜 则只用选择加够能到 最近的便宜加油站 的油即可在该点继续重复贪心判断 若在所能走的D距离内都无法到达最近的下一点则 no solution 这里设定终点的油价为0——因为若在某点判断距离范围内最近的且比它便宜的油价加油站就是终点则直接可以开到终点 一题多解 这里我的做法思路是先判断最远距离再判断中间是否有更便宜的加油站;当然也可以先判断最便宜的加油站在判断是否能走能走就直接到不能走就在中间再找最便宜的加油站 具体实现
题中变量 D1——总距离C——油箱容量D2——每升油能走的距离P——起点油价N——加油站数量可为0 初始化构造二维数组sum[…][0]表示距离[…][1]表示油价 结构sum[[当前站到起点距离, 当前站油价],…] 注意这里将起点设为 [0, P]终点设为 [D1, 0] 贪心递归函数 参数index—记录当前所在位置c—记录当前邮箱剩余的油量 递归结束条件 到达终点indexN1 递归体 ①先判断加满油时是否能到达下一加油站 dC*D2sum[index1][0]-sum[index][0] 不能达到则结束 ②若能达到 先根据距离判断能到达的最远加油站 m mindex1while mN1:if sum[m][0]sum[index][0]d sum[m1][0]:breakm1如果在这些加油站中有比当前加油站油价便宜的 j只需加够到该站 j的油即可再对 j 站递归 要注意剩余油量c和理论油量c0之间的关系 for j in range(index1,m1):if sum[j][1]sum[index][1]: # 如果存在加油站价格比当前站便宜 # 只用加够到该站的油即可c0(sum[j][0]-sum[index][0])/D2 **# 理论要加的油**if cc0: # 当前油少ressum[index][1]*(c0-c) # 只用再补上即可price(j,0) # 递归else: # 当前油多price(j,c-c0) # 不用出钱break如果在这些加油站中没有比当前加油站油价便宜的则需要加满油到达下一站后再进行判断即递归下一站index1 ...elif jm: # 之间没有加油站比当前站更便宜ressum[index][1]*(C-c) # 加满油c0(sum[index 1][0]-sum[index][0])/D2 **# 理论需要油量**c C-c0 # 到达下一站剩余油量price(index1, c)返回res即为最小费用最后要注意一个特例就是若起点终点时费用为0
贪心递归
def price(index,c): # 当前所在位置index,油量和上一层能达到的最远加油点global res# 递归结束条件——已经到达终点if indexN1:return res# 递归体dC*D2if dsum[index1][0]-sum[index][0]: # 加满油也无法到达下一站return 0else:# 判断最远能达到的加油站位置mmindex1while mN1:if sum[m][0]sum[index][0]d sum[m1][0]:breakm1for j in range(index1,m1):if sum[j][1]sum[index][1]: # 如果存在加油站价格比当前站便宜 # 只用加够到该站的油即可c0(sum[j][0]-sum[index][0])/D2 # 理论要加的油if cc0: # 当前油少ressum[index][1]*(c0-c) # 只用再补上即可price(j,0) # 递归else: # 当前油多price(j,c-c0) # 不用出钱breakelif jm: # 之间没有加油站比当前站更便宜ressum[index][1]*(C-c) # 加满油c0(sum[index 1][0]-sum[index][0])/D2 # 理论需要油量c C-c0 # 到达下一站剩余油量price(index1, c)**# 1.初始化**
alist(input().split())
D1,C,D2,P[float(i) for i in a[:4]]
Nint(a[4])# sum[[当前站到起点距离,当前站油价],...]
sum[[0,P]]
for i in range(N):di,pimap(float,input().split())sum.append([di,pi])
sum.append([D1,0])**# 2.贪心递归**
res0
if price(0,0)!0: **# 传入起点和起点油量**print(%.2f%res)
elif D10: **# 这是个特殊案例 起点就是终点**print(0)
else:print(No Solution)3.买卖股票的最佳时机
示例1
买卖股票的最好时机I 思路分析
这里题目要求找到一次交易能获得的最大利润 不难想到找到最大和最小的极差即可但这里要注意要先买入才能卖掉所以极大要出现在极小之后所以目标就是找到区间内存在的极差再选择所有区间内极差的最大值 ①暴力法超时
分别假设每一天买入股票后遍历之后每一天找到极差最大值
class Solution:def maxProfit(self, prices: list[int]) - int:nlen(prices)res0for i in range(n):for j in range(i1,n):resmax(0,prices[j]-prices[i])return res②贪心法 当利润小于0时舍弃之前的股票买入当前股票并计算接下去时间段内能达到的最大利润 具体实现 构造差分数组profit profit[i]——记录prices[i1]和prices[i]之间的差值即为利润 记录当前总利润sum 如果sum≤0说明前面一段时间的总买卖是亏损的不管profit[i]等于多少都让sumprofit[i]表示摒弃前面买的重新买入当前新的股票与明天进行差分计算利润profit并继续判断sum如果sum≥0说明之前买卖的股票盈利在此基础上加上今天与明天的差分profit继续判断sum
图解算法 贪心差分
class Solution:def maxProfit(self, prices: list[int]) - int:nlen(prices)# 差分数组profit []for i in range(1,n):profit.append(prices[i]-prices[i-1])# 求一次交易能达到的最大利润sum0res-1for i in range(n-1):if sum0:sumprofit[i]else:sumprofit[i]if sumres:ressumresmax(0,res)return res示例2
买卖股票的最好时机II
思路分析
这里和上一道题有所不同的是此时的最大利润是所有买卖的到利润的总和可以来自多次交易
因此我们需要求得所有买卖获利的情况计算他们的总和
贪心法 每一轮买卖都要求得盈利最大的情况也就是只要第二天股票价格变低立刻选择在今天卖出保持当前所获利润最大如果仍处于上升趋势则继续获利 也就是要获得所有股票上升的区段并求得利润总和
具体实现 利用pre来定位上升的起点 比较之后天的prices和pre 若prices[i]-pre0: resprices[i]-pre 并继续判断 若prices[i]-pre≤0: preprices[i] 更新pre指向新起点重新判断
图解算法 class Solution:def maxProfit(self, prices: list[int]) - int:res0preprices[0]nlen(prices)for i in range(1,n):if prices[i]pre:resprices[i]-prepreprices[i]else:preprices[i]return res4.哈夫曼编码
在了解哈夫曼编码之前我们先了解不同类型的编码方式 1固定长度编码不同字符之间用相等长度的二进制位表示 2可变长度编码允许不同字符用不同长度的二进制位表示 3前缀编码没有一个编码是另一个编码的前缀 例如不可能出现110101这种以另一个二进制数为前缀的编码 4哈夫曼编码字符集中的每一个字符作为一个叶子节点各个字符出现的频度作为权值构造哈夫曼树——也是一种前缀编码 二义性
可以观察下列编码方式非前缀编码 可以看到对一段非前缀编码数字解码时通过不同的拆解方式得到的解码也不相同这是因为d,c具有相同的前缀所以导致01和010只相差一位就可以得到不同解 ①哈夫曼编码 是一种十分有效的编码方法广泛用于数据压缩中其压缩率通常在 20%90% 之间。采用不等长编码使编码不会有歧义也就是无二义性并且和等长编码相比更加节省空间
其中贪心算法 的主要思路是通过每次查找最小权和次小权构建叶子节点叶子节点的和作为父节点的权值如此循环下来构成一棵完全二叉树对应的左子树编码为0右子树编码为1通过遍历树即可得出最终的哈夫曼编码
实现方式 图解算法
1.若已经得到了各初始字母结点的权值 2.选取最小的两个权值作为叶子节点(fe)他们的和作为父节点 3.重复2中操作直到所有结点均成为一棵完全二叉树上的叶子节点为止 a,c,d,e,f 最终全部变为叶子节点由此按照左边为0右边为1的规则走可以通过走过边上的数字组合成为二进制数最终得到各字母的哈夫曼编码** ②哈夫曼编码的性质
1每一个给定的初结点最后都会成为叶子结点所以权值越小到根节点的路径长度也就越大
2假设初始时给定n个结点由于要结合n-1次每结合一次都会新增一个结点因此哈夫曼树的结点数为 2n-1 个
3哈夫曼树中不存在度为1的结点也就是完全二叉树
4哈夫曼树并不唯一但所有哈夫曼树的带权路径长度一定是相同的 ③哈夫曼树的引例
可以看一个有意思的例子来具体了解一下哈夫曼编码 若有100道选择题其中有60个A20个B15个C和5个D两个人想要在考试中作弊希望通过一种暗号进行传递他们规定短为0长为1那么应该如何设计编码使得传递更高效呢 思路分析
由题设可以分别确定A B C D的权值因此我们只用构造哈夫曼树即可
ABCD频次权值6020155定长编码000001010011哈夫曼编码010110111
所以 A—0B—10C—110D—111
那么它高效在哪呢
对比定长编码我们可以知道100道题
定长编码需要敲击桌子 300次很难不被监考老师发现
而哈夫曼编码只用敲击桌子 60x120x215x35x3 160次这大大降低了被发现的可能所以得出结论哈夫曼编码——好
代码实现
一.哈夫曼树的构造 先将结点初始化用二位数组记录它的结点名和权值 结构arr[结点名权值] 构造哈夫曼树 贪心法 ①不断处理结点数组—arr直到arr内结点全部合并为一棵树 ②每一轮循环都让arr重新根据权重排序从小到大 ③排序后选出最小的两个结点arr[0]arr[1]分别作为右节点r和左节点也可以反过来 将贪心选择出来的左右结点/子树合并为一棵树 ①如果当前队列数组里还有两个以上的节点个数 将左右子树的结点名称合并值相加得到新的父结点: 1.tree增加一个键值对 tree[ l[0]r [0]]{‘left’: l, ‘right’: r} 树内键值对结构——字典套字典套列表 { 树名即树下所有结点名相加 : { left:【左子树/左叶子结点名, 左子树/左结点值】, right:【右子树/右叶子结点名, 右子树/右结点值】 } } 2.arr添加新结点——入队 arr.append([l[0] r[0], l[1] r[1]]) 3.让左右这一轮选出的左右结点出队 arrarr[2:] ②如果只剩下两个结点 根据权值大小直接作为左右结点并定义该树的根节点 ‘root’
# 1.初始化
slist(input().split())
wlist(map(int,input().split()))# 构造一个嵌套列表存储每一个结点
arr [[s[i], w[i]] for i in range(len(s))]
# # [[结点:值],...][[a, 60], [b, 20], [c, 15], [d, 5]]# 2.构造哈夫曼树——**字典套字典套列表**
tree {}
while len(arr) 1:**# 1 根据权重排序——从小到大**arr.sort(keylambda x: x[1])**# 2 选出最小的两个节点分别作为左子树右子树**r arr[0] # 小的为右子树l arr[1] # 大的为左子树if len(arr) 2:# 将左子树和右子树的结点汇总构成新的树tree[l[0] r[0]] {left: l, right: r}# 3.将最小权值的两个结点出队arr arr[2:]arr.append([l[0] r[0], l[1] r[1]])else: # 只剩下一个结点和一棵树tree[root] {left: l, right: r}break二.哈夫曼编码
定义哈夫曼编码函数 传入参数 now_root : 传入构造的tree中当前根节点键对应的值 注意这里的now_root为字典储存这根下的左右子树如初始时now_roottree[’root’]now_root为{‘left’: [‘bdc’, 40], ‘right’: [‘a’, 60]} 可以看到now_root实际上是字典使用时要注意用法 tree : 传入树本身 codecode’’ 实际上是默认参数不传实参时默认为空字符传实参时值为实参 huffmancodehuffmancode{} 也为默认参数用于记录结点对应的编码 dfs 分别深根遍历左子树和右子树(方法类似)以左子树为例 ①当左子树不为叶子结点时 即now_root[’left’][0]≠1 解释之前强调过now_root实际上是存有左右子树信息的字典而子树中字典的值又是一个列表所以now_root[’left’] 先取出了 左子树信息的列表再根据列表索引 …[0] 将左子树名取出由于树的名称长度代表了树下有多少个结点所以1即表示不为叶子结点 这里选择每第一次到达某层就更新编码值所以为右加 ’0’: 定义当前的 huffman_codecode0 由于不是叶子结点继续递归 huffman(tree[now_root[left][0]],tree,huffman_code) tree[now_root[’left’][0]]——在tree树中找到键为左子树名称所对应的值字典传入更新后的huffman_code ②当左子树为叶子结点时 加上该边的二进制编码值 ’0’ 并更新huffmancode字典中对应结点的编码值结束
同理继续对右子树操作最终函数返回 huffmancode
**# 函数先传入默认参数**
def huffman(now_root,tree,code,huffmancode{}):# 1.dfs左子树# 如果左子树不为叶子结点if len(now_root[left][0])!1:huffman_codecode0 # 当前的哈夫曼编码加上0huffmancodehuffman(tree[now_root[left][0]],tree,huffman_code) # 继续dfs# 如果左子树为叶子结点else:huffman_codecode0huffmancode[now_root[left][0]]huffman_code# 2.dfs右子树# 如果右子树不为叶子结点if len(now_root[right][0])!1:huffman_codecode1 # 当前的哈夫曼编码加上1huffmancodehuffman(tree[now_root[right][0]],tree,huffman_code,huffmancode) # 继续dfs# 如果右子树为叶子结点else:huffman_codecode1huffmancode[now_root[right][0]]huffman_code return huffmancode完整代码
def huffman(now_root,tree,code,huffmancode{}):# 1.dfs左子树# 如果左子树不为叶子结点if len(now_root[left][0])!1:huffman_codecode0 # 当前的哈夫曼编码加上0huffmancodehuffman(tree[now_root[left][0]],tree,huffman_code) # 继续dfs# 如果左子树为叶子结点else:huffman_codecode0huffmancode[now_root[left][0]]huffman_code# 2.dfs右子树# 如果右子树不为叶子结点if len(now_root[right][0])!1:huffman_codecode1 # 当前的哈夫曼编码加上1huffmancodehuffman(tree[now_root[right][0]],tree,huffman_code,huffmancode) # 继续dfs# 如果右子树为叶子结点else:huffman_codecode1huffmancode[now_root[right][0]]huffman_codereturn huffmancode**# 1.初始化**
slist(input().split())
wlist(map(int,input().split()))# 构造一个嵌套列表存储每一个结点
arr [[s[i], w[i]] for i in range(len(s))]
# # [[结点:值],...][[a, 60], [b, 20], [c, 15], [d, 5]]**# 2.构造哈夫曼树——字典套字典套列表**
tree {}
while len(arr) 1:# 1 根据权重排序——从小到大arr.sort(keylambda x: x[1])# 2 选出最小的两个节点分别作为左子树右子树r arr[0] # 小的为右子树l arr[1] # 大的为左子树if len(arr) 2:# 将左子树和右子树的结点汇总构成新的树tree[l[0] r[0]] {left: l, right: r}# 3.将最小权值的两个结点出队arr arr[2:]arr.append([l[0] r[0], l[1] r[1]])else: # 只剩下一个结点和一棵树tree[root] {left: l, right: r}break**# 3.对所给字符进行哈夫曼编码**
huffmancodehuffman(tree[root],tree)
print(树:,tree) # 打印哈夫曼树
print(\\n对应编码:,huffmancode) # 打印哈夫曼编码
# 输出:
树: {cd: {left: [c, 15], right: [d, 5]},cdb: {left: [cd, 20], right: [b, 20]},root: {left: [a, 60], right: [cdb, 40]}}对应编码: {a: 0, c: 100, d: 101, b: 11}以下为图论中的应用
5.最小生成树—prim算法
首先要了解一些基本概念
1连通图的生成树是指包含图中全部顶点边尽可能少但要连通的树
2最小生成树为带权的连通无向图 ①最小生成树的性质
不唯一但权值和相同边数顶点数-1如果一个连通图本身就是树则它本身就是一棵最小生成树
②prim算法
Prim算法又称为加点法每次找出距离最小的边对应的点(此处的距离指的是未加点到最小生成树的距离)算法从某一个顶点s开始逐渐将剩余n个点纳入最小生成树中 ③prim算法的步骤 第一步设图中所有顶点的集合为Vu代表已经加入最小生成树的顶点的集合v代表未加入最小生成树的顶点的集合由于从某点s开始因此初始化 u{s}v{V-u} 第二步在两个集合u,v中选择一条代价最小的边将在v中连接这条边的那个顶点x加入到最小生成树顶点集合u中并且更新与x相连的所有邻接点的权值 第三步重复上述第二步直到最小生成树顶点集合u中有n个顶点为止 最终目标u{V},v{}
图解算法 这是一张初始的无向图以0作为起点集合u{0}v{1,2,3,4,5,6} 构造min[]数组索引表示图中结点对应的值表示未加入的点到当前得到的最小生成树的最短距离*即到最小生成树中点的最小距离* min的初始化标记起点为0其余点初始化为inf 加入起点0后更新树组中与0相邻的点 1 和 3 的值 u{0}v{1,2,3,4,5} 由于更新后数组中最小权值为5则选择加入与0相邻的点 3 u{0,3}v{1,2,4,5} 加入点3后只用检查与3相邻的所有点到3的权值并更新即可 因为与0相邻的所有点已经检查过只用更新新加入点到相邻点的权值即可而当选择下一个加入点时是对所有u集合内的点进行搜查的最终选择点 1 u{0,1,3}v{2,4,5} 重复上述操作直到所有点多加入最小生成树中为止 u{0,1,2,3,4,5}v{} 对上述过程的min数组
min0123456①0∞∞∞∞∞∞②08∞5∞∞∞③03∞5∞715④0312510715⑤03259715⑥03256715 示例模板题
最小生成树MST
这里给几个样例
# 样例一
4 5
1 2 2
1 3 2
1 4 3
2 3 4
3 4 3————7
# 样例二
5 18
2 4 276
3 3 435
3 4 608
2 4 860
1 2 318
1 3 547
5 4 419
2 5 98
1 5 460
5 3 399
3 5 240
3 2 733
3 3 903
4 2 909
5 2 206
3 4 810
2 1 115
2 3 419————729
# 样例三
6 10
1 2 6
1 3 1
1 4 5
2 3 5
2 5 3
3 4 5
3 5 6
3 6 4
4 6 2
5 6 6————15思路分析
思路参考Prim算法_CSDN博客_prim算法
prim算法的思路在之前已经叙述过但要实现仍要做一些准备代码解释如下 lowcost[i]: 表示以 i为终点的边的最小权值 当lowcost[i]0 说明以i为终点的边的最小权值0,也就是表示i点加入了MST mst[i]: 表示对应lowcost[i]的起点边mst[i],i是MST的一条边即点i的最小权值边在MST中对应的点最小权值边的另一个点 当mst[i]0 表示起点i加入MST graph[i][j]这里用邻接矩阵存储 邻接矩阵为对称矩阵graph[i][j]graph[j][i]的值表示边i,j对应的权值 注意有坑因为可能存在两点之间有多条重复的边选最小的即可 min表示此轮prim找到的最小边的权值 贪心法每一轮都会选择一个与MST相连的最小权值边和对应的点加入MSTmin则表示边的权值 minid表示此轮prim加入MST的点 初始化 先将graph的第一行赋值给lowcost表示以1为起点的MST的初始状态并初始化lowcost[1]0因为点1已经在MST中了将mst赋值为1mst[1]0表示除点1外的其他点当前的最小权值边都是以1为起点来初始化的而此时点1已经在MST中了 将所有点加入到MST中遍历n-1轮 找到与当前MST连接的最小权值边 每一轮先让min为∞minid为0(如果循环结束仍为0表示该图不连通) 对所有点进行遍历如果点 j对应边的最小权值小于min结束后则更新min的值并将 j赋值给minid结束后则将minid加入MST … if lowcost[j] min and lowcost[j] ! 0: min lowcost[j]; minid j; summin lowcost[minid]0 … 当前的lowcost[j]如果小于min由于不为∞则既表示和MST有连接边又表示为较小的权值边而lowcost[j]0即表示点 j不在MST中则循环一轮后表示 j为即将加入MST的点min为此轮的最小权值 更新lowcost 因为新加入一个点所以有些点的最小权值会改变由于加入点为minid相当于解锁了graph[minid][]即根据graph表可得minid所连接的所有点对应边的权值只用更新比当前lowcost小的即可
prim:
空间爆了3个邻接表存储空间大 global n,m,graph
def prim(p):# 1.初始化sum0lowcost[-1 for _ in range(n1)]# mst[1 for _ in range(n1)]# mst[1]0 # 初始化点1lowcost[1]0for i in range(2,n1):lowcost[i]graph[1][i]# 2.加入所有点for i in range(n-1):minfloat(inf)minid0for j in range(2,n1):if lowcost[j]min and lowcost[j]!0:minlowcost[j]minidjif minid0:return -1# print(f{mst[minid]}-{minid}{min}) # 打印MST加入的新边summinlowcost[minid]0for k in range(2,n1):if lowcost[k]graph[minid][k] and lowcost[k]!0: # 判断不在树内的点k对应的lowcost[k]是否可以得到更小值lowcost[k]graph[minid][k]# mst[k]minid # 更新点k对应的最小权值边在MST中对应的点return sumn,mmap(int,input().split()) # n为点个数m为边个数
# 1.构造邻接矩阵,从(1,1)开始存图
graph[[float(inf)]*(n1) for i in range(n1)]
for i in range(1,m1):p1,p2,wimap(int,input().split())if wigraph[p1][p2]: # 这里有坑因为可能存在两点之间有多条重复的边选最小的即可graph[p1][p2]wigraph[p2][p1]wi# 2.prim
resprim(1)
if res-1:print(orz)
else:print(res)6.单源最短路径—Dijkstra算法
首先要了解
①单源最短路径
对于有向带权图G(V,E)其中每条边的权值都是非负 实数给定V中的一个节点称为源点计算源点到其他各节点之间的最短路径即单源最短路径
②Dijkstra算法
Dijkstra算法是解决单源最短路径问题的**贪心算法**Dijkstra算法基本思路是先求出源点 离当前节点最短的一条路径然后根据当前最短路径末端点能够到达的点求出下一条离源点最近的路径直到求出源点到其他各节点的最短路径 定理最短路径的子路径仍然是最短路径 如图源点A到C的最短路径为9A→E→B→C经过了B点则此最短路径中从源点到B点的子路径一定是所有从源点到B点的路径中最短的那条 因为若为最短路径d则一定要求所经过的点每一步都是最短的否则不可能成立 反证法已知源点到点C的最短路径为 d到我们假设到点B的子路径 L1不是B的最短路径那么一定存在 L2L1使得源点到B点最短则当前dL1LB→C L2LB→C所以得出d不是最短路径与题设不符假设不成立
③Dijkstra算法的步骤
找出从起点出发可以前往的路径最短的未处理点对于该结点的邻接点检查是否有前往他们的更短路径如果有则更新其最短路径将该结点加入已处理队列中后续不再处理该结点重复1-4步直到对图中除了终点的所有结点都进行了检查得到最终路径
算法分析
我们需要先构造三个数组
final[]: 标记各顶点是否已经找到最短路径dist[]表示源点到该点的最短路径长度path[]: 当前到该点路径上的前驱
具体步骤
初始化
ABCDEfinal[]TrueFalseFalseFalseFalsedist[]010∞∞5—最小path[]-10-1-10
第一轮寻找
①循环遍历所有结点找到还未确定最短路径且dist最小的结点vi
令final[vi]True表示vi已经找到了最短路径—d0dist[vi]
②检查所有与vi相连的结点若还未确定最短路径则更新path与dist的值
更新为dd0wi
则有
ABCDEfinal[]TrueFalseFalseFalseTruedist[]08147—最小5path[]-14440 第二轮寻找 在余下未确定最短路径的所有点中以dist最小的未顶点vi重复上述操作
ABCDEfinal[]TrueFalseFalseTrueTruedist[]08—最小1375path[]-14340
ABCDEfinal[]TrueTrueFalseTrueTruedist[]089—最小75path[]-14440 最后寻找 已经找不到其他为False的结点将所有的结点设为True返回数组
ABCDEfinal[]TrueTrueTrueTrueTruedist[]08975path[]-14440 示例1模板题
dijstra求最短路径
n, m map(int, input().split())
maxdist float(inf)
g [[maxdist] * (n1) for _ in range(n1)] # 由于是密集图mn因此用邻接矩阵来存储g[x][y]表示x指向y的距离
d [maxdist] * (n1) # 存储每个点距离起点的距离初始化为距离最大d[1]0
st [False] * (n1) # 判断某一点的最短距离是否已经确定False表示未确定True表示确定def dijkstra():d[1] 0for i in range(1, n1): # 因为要确定n个点的最短路因此要循环n次t -1for j in range(1, n1): # 每次找到还未确定最短路的点中距离起点最短的点tif not st[j] and (t-1 or d[t]d[j]):t jst[t] Truefor j in range(1, n1): # 用t来更新t所指向的点的距离d[j] min(d[j], d[t] g[t][j])if d[n] maxdist:return -1else:return d[n]for _ in range(m):x, y, z map(int, input().split())g[x][y] min(g[x][y], z) # 当出现重边时只需取两个距离中的最小值
print(dijkstra())示例2
最小花费
def dijkstra(A):# 1.初始化final[False for _ in range(n1)]# dist存到该点需要的最少钱dist[float(inf) for _ in range(n1)]dist[A]100# 2.dijkstrafor _ in range(n): # 必须要将所有点遍历完才能结束算法minfloat(inf)node0for j in range(1,n1): # 遍历所有点if final[j]!True and dist[j]min: # 如果未被访问过# 找出每一轮循环的最小值mindist[j]nodejfinal[node]True# node为该轮的最小点更新所连点的最小费用for k in range(1,n1):if graph[node][k]float(inf): #如果node和k有边faredist[node]/(1-graph[node][k]) # node到k点的费用if faredist[k]: # 如果费用比当前少dist[k]fare # 更新最少费用return dist[B]# 1.初始化
n,mmap(int,input().split())
# graph扣除率
graph[[float(inf)]*(n1) for i in range(n1)] # 邻接矩阵
for i in range(m):x,y,zmap(int,input().split())if graph[x][y]z:graph[x][y]z*0.01graph[y][x]z*0.01
A,Bmap(int,input().split())# 2.dijkstra
print(%.8f%dijkstra(A))
当出现重边时只需取两个距离中的最小值
print(dijkstra())3.总结 本章主要讲解了贪心算法的众多实际应用包括找零背包编码以及图论相关的算法后续仍会持续更新一些其他常见的算法如果有错误请欢迎指正~~感谢 觉得本篇有帮助的话, 就赏个三连吧~
