1 二分查找算法(非递归)
1.1 二分查找算法(非递归)代码实现：
#二分查找法（非递归）
class BinarySearchNoRecur():
def __init__(self,list,target):
self.list = list
self.target = target
def search(self):
self.left = 0
self.right = len(self.list)-1
while (self.left <= self.right):
self.middle = int((self.left+self.right)/2)
if self.list[self.middle] == self.target:
return self.middle
elif self.list[self.middle] > self.target:
self.right = self.middle - 1
else:
self.left = self.middle + 1
return ("not found")
list = [1,2,4,6,8,11,55,66]
bsnr = BinarySearchNoRecur(list,66)
print(bsnr.search())
2 分治算法
分治算法介绍
(1) 分治法是一种很重要的算法。字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题......直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法(快速排序，归并排序)，傅立叶变换(快速傅立叶变换)......
(2) 分治算法可以求解的一些经典问题
二分搜索
大整数乘法
棋盘覆盖
合并排序
快速排序
线性时间选择
最接近点对问题
循环赛日程表
汉诺塔分治算法的基本步骤
分治法在每一层递归上都有三个步骤：
(1) 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
(2) 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问
(3) 合并：将各个子问题的解合并为原问题的解。
3.分治算法-汉诺塔的实现
#递归汉诺塔
#汉诺塔思路：可以把汉诺塔当成两层来看，上层是num-1 下层是num
class Hanoitower():
def process(self,num,A,B,C,):
if (num == 1):
#如果只有一个盘直接把A柱的盘移动到C柱
print(num , A + "->" +C)
else:
#1.把上层的盘从A柱移动到B柱，这么想，如果上层只有一个盘的时候，调用process会直接输出，那么这时候会输出A->C 注意这不是字符而是变量， 因此你需要传递参数的时候把B传给process的C，这样就可以直接输出了第一步从A柱到B柱
self.process(num-1,A,C,B)
#2.输出把下层从A柱移动到C柱，和只有一层的情况一样。
print(num, A + "->" + C)
#3.把现在在B柱的上层移动到C柱，很明显，这会因为要调用process还是输出的A->C，因此这里把B传给A就可以，C还是C
self.process(num-1,B,A,C)
hanoi = Hanoitower()
hanoi.process(3,"A","B","C")
3 动态规划算法
- 动态规划算法介绍：
(1) 动态规划(Dynamic Programming)算法的核心思想是：将大问题划分为小问题进行解决，从而一步步获取最优解
的处理算法
(2) 动态规划算法与分治算法类似，其基本思想也是将待求解问题分解成若干个子问题，先求解子问题，然后从这
些子问题的解得到原问题的解。
(3) 与分治法不同的是，适合于用动态规划求解的问题，经分解得到子问题往往不是互相独立的。 ( 即下一个子
阶段的求解是建立在上一个子阶段的解的基础上，进行进一步的求解 )
(4) 动态规划可以通过填表的方式来逐步推进，得到最优解.
2 应用场景-背包问题
背包问题：有一个背包，容量为4 磅 ， 现有如下物品:
- 要求达到的目标为装入的背包的总价值最大，并且重量不超出
- 要求装入的物品不能重复
-
思路：
(1) 背包问题主要是指一个给定容量的背包、若干具有一定价值和重量的物品，如何选择物品放入背包使物品的价值最大。其中又分01 背包和完全背包(完全背包指的是：每种物品都有无限件可用)
(2) 这里的问题属于01 背包，即每个物品最多放一个。而无限背包可以转化为01 背包。
(3) 算法的主要思想，利用动态规划来解决。每次遍历到的第i 个物品，根据w[i]和v[i]来确定是否需要将该物品放入背包中。即对于给定的n 个物品，设v[i]、w[i]分别为第i 个物品的价值和重量，C 为背包的容量。再令v[i][j]表示在前i 个物品中能够装入容量为j 的背包中的最大价值。
3 代码实现：
#动态规划 背包问题
#动态规划的核心在于，它不是用递归也不用while循环，而是用for循环，通过之前得到的值做调整，通过之前的值这便是动态规划
#本算法目的是要得到一个这种表格，最右下角便是最优解
#[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
#[0, 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500, 1500]
#[0, 1500, 1500, 1500, 3000, 4500, 4500, 4500, 4500, 4500, 4500]
#[0, 1500, 1500, 2000, 3500, 4500, 4500, 5000, 6500, 6500, 6500]
#[0, 1500, 1500, 2000, 3500, 5000, 6500, 6500, 7000, 8500, 9500]
class KnapsackProblem():
def __init__(self):
#物品重量
self.weights = [1,4,3,5]
#物品价值
self.values= [1500,3000,2000,5000]
#背包最大容量
self.maxcapacity = 9
#最大价值
#1.先把表哥第0行第0列置0，必须置0因为第1行可能用到第0行的值
self.maxvalue = [[0 for i in range(self.maxcapacity+1)]for i in range(len(self.weights)+1)]
#路径，放了啥
self.path = [[0 for i in range(self.maxcapacity+1)]for i in range(len(self.weights)+1)]
def plan(self):
for i in range(len(self.weights)):
for j in range(self.maxcapacity+1):
self.remainingcapacity = j
if self.weights[i] <= self.remainingcapacity:
self.remainingcapacity -= self.weights[I]
#这里为什么是i+1？ 因为我们多了一行全0 以及一列全0 也就是第i个商品self.values[i] 其实相当于maxvalue第i+1行self.maxvalue[i]，至于列的话因为从0开始遍历遍历到10，那么就可以和容量对应上了，因此不需要j+1
#2.如果当前物品的重量小于等于背包剩余容量的话，先把容量扣掉，再让当前物品的最大价值self.maxvalue[i+1][j] = max(self.maxvalue[i][j], self.values[i]+self.maxvalue[i][self.remainingcapacity])
#self.maxvalue[i][j]表示上一行的值，因为可能你加上当前物品的价值还不如之前不加当前物品的价值多，那么就要用之前的策略
# self.values[i]+self.maxvalue[i][self.remainingcapacity] 表示 当前物品的价值+剩余容量的最大价值，这个怎么找呢？
# 首先我们已经又的剩余容量也就是self.remainingcapacity，所以找这列，然后找这一列的尽量下面一个也就是第i行，为什么不是本行i+1行呢，因为这个是01背包，你第i+1行算的是第i个商品，
# 此时你再前面已经把第i个商品的价值给加上了，因此这里只能用第i-1行的值
#v[i][j] = Math.max(v[i - 1][j], val[i - 1] + v[i - 1][j - w[i - 1]])
# self.maxvalue[i+1][j] = max(self.maxvalue[i][j], self.values[i]+self.maxvalue[i][self.remainingcapacity])
#考虑到path：什么时候需要做标记，首先你肯定要先把物品加进来，其次加进来之后，你要保证加得有意义，也就是 self.maxvalue[i][j] < self.values[i]+self.maxvalue[i][self.remainingcapacity]
#如果没有，那就是拿上次的结果就可以了，这次就没有必要标记了
self.maxvalue[i+1][j] = max(self.maxvalue[i][j], self.values[i]+self.maxvalue[i][self.remainingcapacity])
if self.maxvalue[i][j] < self.values[i]+self.maxvalue[i][self.remainingcapacity]:
self.path[i+1][j] = 1
else:
#3.如果当前物品的重量大于背包剩余容量的话，也就是放不下了，就拿上一行的数据就行了
self.maxvalue[i+1][j] = self.maxvalue[i][j]
self.Print()
def Print(self):
i = len(self.weights)
j = self.maxcapacity
print(self.maxvalue)
#输出path方法：
#从最后一行最后一列也就是最后一个开始找，如果有做标记就把该行也就是i也就是第几个物品输出出来。那么就要把容量扣掉，再去找，如果这一行没有找到就往上一行找，如果有一定找得到，可能不在本行在上一行，否则直到最后找到第-1行就退出
while (i>=0 and j>=0):
if self.path[i][j] == 1:
print("添加第",i,"个物品到包里")
j -= self.weights[i-1]
else:
i -=1
knapsack = KnapsackProblem()
knapsack.plan()
结果
4 KMP算法：
1 应用场景-字符串匹配问题:
(1) 有一个字符串 str1= "ababababc"，和一个子串 str2="ababc"
(2) 现在要判断 str1 是否含有 str2, 如果存在，就返回第一次出现的位置, 如果没有，则返回-1
2 KMP算法介绍：
(1) KMP 是一个解决模式串在文本串是否出现过，如果出现过，最早出现的位置的经典算法
(2) Knuth-Morris-Pratt 字符串查找算法，简称为 “KMP 算法”，常用于在一个文本串S 内查找一个模式串P 的出现位置，这个算法由Donald Knuth、Vaughan Pratt、James H. Morris 三人于1977 年联合发表，故取这3 人的姓氏命名此算法.
(3) KMP 方法算法就利用之前判断过信息，通过一个next 数组，保存模式串中前后最长公共子序列的长度，每次回溯时，通过next 数组找到，前面匹配过的位置，省去了大量的计算时间
next数组的原理
(4) 参考资料：https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html
3 kmp算法代码实现：
#kmp算法：
#首先定义一下next数组的意义：
#例如有一个字符串，对应的next数组如下
#a b c a b a b c a b c
#0 0 0 1 2 1 2 3 4 5 3
#next数组的值表示搜索到当前字符的时候，包括其自身字符的最大重复子串的个数
#例如搜索到abcababc的时候此时i=7 j=2 相等则 j+=1 next.append(j) i += 1 再继续搜索下去
#因此就有以下三种情况：
#1.相等即str1[i]==str1[j]
#2.若str1[i]!=str1[j]且j==0的情况，这个时候是还没有匹配到重复的子串如刚开始的abc，直接把0添加到next数组，并让 i+=1
#3.最难的是str1[i]!=str1[j] 且 j!=0的情况，这时候不能直接让j置0
#如abcababcabc 当匹配到倒数第二个字符的时候此时i=9,j=4,此时相等，那么就j +=1 next.append(j) i +=1，此时就是i=10，j=5此时str1[i]!=str1[j]若直接把j置0
#那么 仍然str1[i]!=str1[j]且j==0，就会直接把0给加到next数组里面去，代表此时最大重复子串为0很明显不是的，此时最大重复子串的长度应该为3
#问题就出在这，因为我们应该让j = next[j-1] 这句话怎么理解？
#还是比如我们找到最后一个字符c ， 此时i=10，j=5，我们知道str[0:4] str1[5:9]是重复的，因为i=9时，next[9]=5，也就是str1[0:j-1] str1[j:i-1]是相等的，（其实数学原理不是这样的，我们只是想了一个特例）
#那么我们就应该去找搜索到第i-1个字符时的最大重复子串的长度，也就是i=4时，next[i]=? ，因为我们找到了i=4的最大重复字串比如 i=4时->“abcab”,最大重复字串是"ab",而str1[j:i-1] 与str1[0:j-1]又是相等的
#因此str1[j:i-1] 与整个字符串的最大重复字串就是“ab”，
#上面分析的实例：
#1.a b c a b a b c a b c 加了c之后不等
#2.由于前半段a b c a b 和后半段a b c a b 是重复的
#3.找到前半段a b c a b 的最大重复字串那么肯定和后半段a b c a b也是重复的，因此此时我们就从c这个位置开始比对最后一个字符，
#4.这里为什么直接找next[4]就可以了，因为这里存的是2，也就是j=2，那么就找到的是c而不是b，因此可以直接与最后一个字符进行比较
def next(str1):
I=1
next=[0]
j=0
while(i<len(str1)):
if (str1[i]==str1[j]):
j +=1
next.append(j)
i +=1
elif(j==0):
next.append(0)
i +=1
else:
# print(i,j)
j = next[j-1]
return next
# list = 'abcababcabc'
# result= next(list)
# print(result)
#接下来是kmp算法，当你实现了求next数组之后kmp算法就简单了
#首先是需要传入两个字符串，一个是初始字符串，一个是搜索字符串
#1.先获得搜索字符串的next数组
#2.将初始字符串与搜索字符串一个一个进行对比，同样有三种情况：
#2.1 若相等的话，不用考虑j是否为0反正都要 jk+=1，但是这里需要判断是否输出，因为假如刚好你已经匹配完整个searchlist了并且最后一个字符还与当前的initlist[i]相等，说明整个搜索字符串相等，那就返回i-j
#2.2 如果不等就需要判断j是否为0，如果为0那么意味着，当前字符与搜索字符串的第0个字符就不想等，因此把当前字符往后移一位就行，也就是i+=1， j不用动
#2.3 如果j不等于0，那么就要找到当前字符的前一个next值，例如找到i=j=4的时候 这时候 initlist[4]=a ,searchlist[4]=c ，不等，那么就需要找到nextlist[3]的值代表着searchalist[0:4]
# 这个字符串中最大的重复字串，那么这些就不用再比了，只要比最大重复字串的后一个字符就行，因此j=2 也就是从a开始比，这时候i也不需要懂，因为i之前的字串肯定和这个最大的重复字串也重复，因此直接比对就可以
def kmp(initlist,searchlist):
nextlist = next(searchlist)
i = 0
j = 0
while (i < len(initlist)):
if initlist[i] == searchlist[j] :
#print(i,initlist[I])
#print(j,searchlist[j])
if j == len(searchlist)-1:
return i-j
i += 1
j += 1
else:
if j==0:
I+=1
else:
j = nextlist[j-1]
return("none")
# initlist = 'abcabababcababcabc'
# searchlist = 'abcababcabc'
initlist = 'ababababc'
searchlist = 'ababc'
kmp = kmp(initlist,searchlist)
print(kmp)
5 贪心算法
5.1 应用场景-集合覆盖问题
假设存在下面需要付费的广播台，以及广播台信号可以覆盖的地区。 如何选择最少的广播台，让所有的地区都可以接收到信号
2 贪心算法介绍
(1) 贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法
(2) 贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果
3 贪心算法思路分析
(1) 目前并没有算法可以快速计算得到准备的值， 使用贪婪算法，则可以得到非常接近的解，并且效率高。选择
策略上，因为需要覆盖全部地区的最小集合:
(2) 遍历所有的广播电台, 找到一个覆盖了最多未覆盖的地区的电台(此电台可能包含一些已覆盖的地区，但没有关
系）
(3) 将这个电台加入到一个集合中(比如ArrayList), 想办法把该电台覆盖的地区在下次比较时去掉。
(4) 重复第1 步直到覆盖了全部的地区
(5) 图解：
4 贪心算法代码实现：
#贪心算法：
#1.首先需要将各个电台不同的城市加到allcity中，也就是保证allcity每个元素的唯一性
def getallcity():
k1 = ["beijing","shanghai","tianjin"]
k2 = ["guangzhou","beijing","shenzhen"]
k3 = ["chengdu","shanghai","hangzhou"]
k4 = ["shanghai","tianjin"]
k5 = ["hangzhou","dalian"]
allradio = [k1, k2, k3, k4, k5]
allcity = []
for i in range(len(allradio)):
for j in range(len(allradio[i])):
#由于allcity初始没有元素，因此需要判断若长度为0需要将k1的第0个城市添加进来，以便判断是否重复
if len(allcity) == 0:
allcity.append(allradio[i][j])
continue
for k in range(len(allcity)):
#如果在allcity中找到重复的，那么就不用再遍历allcity了，继续遍历allradio[i] 就行。
if allradio[i][j] == allcity[k]:
break
#想想什么时候需要添加进来，就是当allcity遍历完了，此时k=len(allcity)-1 并且都没有找到重复的。
elif k == len(allcity)-1 :
allcity.append(allradio[i][j])
return (allradio,allcity)
#2.进行贪心算法
#2.1
#这里就是拿allradio中的每个元素即k1,k2,k3,k4,k5中的每个元素与 allcity进行比较，若有重复的我们让key+=1，就遍历本电台的下一个城市
#当遍历完每个电台之后，将此时的key存入到keylist中，以便后边与maxkey进行比较，此时如果maxkey<key 的时候要对maxkey进行更新
#并且当每个电台遍历完后，要对key进行清零
#2.2
# 此时就获得了keylist，与maxkey。再去遍历keylist找到第一个与maxkey相等的值，这个便是我们要找的电台，将其添加到selectradio中，
# 并把这个电台中的所有城市在 allcity中删除，这样就保证这个电台下次的key为0，也就不必担心我们刚才直接找到第一个与maxkey相等的值会不会不是我们想要的
# 完事之后只需要判断allcity的长度是否为0，为0就说明删除完了，就可以返回selectradio了
def GreedyAlgorithm(allradio, allcity):
selectradio = []
while (len(allcity)!=0):
maxkey = 0
keylist = []
key = 0
for i in range(len(allradio)):
key = 0
for j in range(len(allradio[i])):
for k in range(len(allcity)):
if allradio[i][j] == allcity[k]:
key += 1
break
keylist.append(key)
if maxkey < key:
maxkey = key
for i in range(len(keylist)):
if keylist[i] == maxkey:
selectradio.append(I+1)
for j in range(len(allradio[i])):
k =0
while k < len(allcity):
if allradio[i][j] == allcity[k]:
allcity.remove(allcity[k])
else:
k += 1
return selectradio
allradio,allcity = getallcity()
select = GreedyAlgorithm(allradio, allcity)
print(select)
结果
6 普里姆算法
6.1 应用场景-修路问题
(1) 有胜利乡有7 个村庄(A, B, C, D, E, F, G) ，现在需要修路把7 个村庄连通
(2) 各个村庄的距离用边线表示(权) ，比如 A – B 距离 5 公里
(3) 问：如何修路保证各个村庄都能连通，并且总的修建公路总里程最短?
思路: 将10 条边，连接即可，但是总的里程数不是最小.
正确的思路，就是尽可能的选择少的路线，并且每条路线最小，保证总里程数最少.
6.2 最小生成树
修路问题本质就是就是最小生成树问题， 先介绍一下最小生成树(Minimum Cost Spanning Tree)，简称MST。
给定一个带权的无向连通图,如何选取一棵生成树,使树上所有边上权的总和为最小,这叫最小生成树
(1) N 个顶点，一定有N-1 条边
(2) 包含全部顶点
(3) N-1 条边都在图中
(4) 举例说明(如图:)
(5) 求最小生成树的算法主要是普里姆算法和克鲁斯卡尔算法
6.3 普里姆算法介绍
普利姆(Prim)算法求最小生成树，也就是在包含n 个顶点的连通图中，找出只有(n-1)条边包含所有n 个顶点的
连通子图，也就是所谓的极小连通子图
普利姆的算法如下:
(1) 设G=(V,E)是连通网，T=(U,D)是最小生成树，V,U 是顶点集合，E,D 是边的集合
(2) 若从顶点u 开始构造最小生成树，则从集合V 中取出顶点u 放入集合U 中，标记顶点v 的visited[u]=1
(3) 若集合U 中顶点ui 与集合V-U 中的顶点vj 之间存在边，则寻找这些边中权值最小的边，但不能构成回路，将
顶点vj 加入集合U 中，将边（ui,vj）加入集合D 中，标记visited[vj]=1
(4) 重复步骤②，直到U 与V 相等，即所有顶点都被标记为访问过，此时D 中有n-1 条边
(5) 提示: 单独看步骤很难理解，我们通过代码来讲解，比较好理解.
(6) 图解普利姆算法:
普利姆算法
6.4 普里姆算法代码实现：
#普里姆算法（最小生成树问题）
#构建图，包括verxs 顶点（结点）个数、data 顶点数据，weight边的权重
class MGraph():
def __init__(self,verxs,data,weights):
self.verxs = verxs
self.data = data
self.weights = weights
#普里姆算法的实现：
# 1.我们知道普里姆算法有个公式 N个结点一定有N-1条边， 因此我们首先要循环 len(self.graph.data)-1 次 获取这么多条边
# 2.先遍历self.visited 再遍历 self.graph.weights[i] 因为我们要先通过self.visited 里的数据，确定这次选边的一个结点，因为我们需要先找到包含在self.visited 里面所有结点所有不重复的边 ，再通过遍历 self.graph.weights[i]确定另一个结点
# 3.因此不管是判断这条边的权重是否为10000（是否连通）， 或者 这条边的权重是否小于minweight 都是通过jk去搜索的，i只是作为生成6条边而已。
class Prim():
def __init__(self,graph):
self.graph = graph
self.visited = []
self.minweight = 10000
def minTree(self,start):
self.visited.append(start)
self.datalength = len(self.graph.data)-1
for i in range(self.datalength):
for k in self.visited:
for j in range(len(self.graph.weights[i])):
#如果这条边为10000说明没有连通，遍历下一个结点也就是遍历下条边
if self.graph.weights[k][j] == 10000:
continue
#这里需要判断 j 是否在 visited列表里， 若在说明这条边已经存在不需要再比较了
elif self.visited.count(j) == 0 and self.graph.weights[k][j] < self.minweight:
self.minweight = self.graph.weights[k][j]
self.h0 = k
self.h1 = j
print(self.graph.data[self.h0], self.graph.data[self.h1],self.minweight)
self.visited.append(self.h1)
#记得将minweight 初始化
self.minweight = 10000
return self.visited
data = ['A', 'B', 'C', 'D', 'E', 'F', 'G']
weights = [[10000,5,7,10000,10000,10000,2],
[5,10000,10000,9,10000,10000,3],
[7,10000,10000,10000,8,10000,10000],
[10000,9,10000,10000,10000,4,10000],
[10000,10000,8,10000,10000,5,4],
[10000,10000,10000,4,5,10000,6],
[2,3,10000,10000,4,6,10000]]
graph = MGraph(len(data),data,weights)
prim = Prim(graph)
mintree = prim.minTree(1)
print(mintree)
结果
7 克鲁斯卡尔算法
1.克鲁斯卡尔算法介绍
(1) 克鲁斯卡尔(Kruskal)算法，是用来求加权连通图的最小生成树的算法。
(2) 基本思想：按照权值从小到大的顺序选择n-1 条边，并保证这n-1 条边不构成回路
(3) 具体做法：首先构造一个只含n 个顶点的森林，然后依权值从小到大从连通网中选择边加入到森林中，并使森林中不产生回路，直至森林变成一棵树为止
2.思路图解：
-
难点分析：
克鲁斯卡尔算法重点需要解决的以下两个问题：
问题一 对图的所有边按照权值大小进行排序。采用排序算法进行排序即可。
问题二 将边添加到最小生成树中时，怎么样判断是否形成了回路？
记录顶点在"最小生成树"中的终点，顶点的终点是"在最小生成树中与它连通的最大顶点"。然后每次需要将一条边添加到最小生存树时，判断该边的两个顶点的终点是否重合，重合的话则会构成回路。
终点重合分析 - 代码实现
#克 鲁 斯 卡 尔 算 法 - 公 交 问 题
class Kruskal():
def __init__(self,vertex,martix):
#vertex : 顶点数组
self.vertex = vertex
#martix : 邻接矩阵
self.martix = martix
#所有边的数量
self.alledgesnum = 0
#所有边的集合
self.edges = []
#顶点数组对应的终点列表
self.endlist = [0 for i in range(len(self.vertex))]
#最小生成树结果
self.result = []
#通过遍历邻接矩阵将边的信息添加到self.edges中。 [['E', 'F', 2], ['C', 'D', 3], ['D', 'E', 4]...]
#这里很巧妙的是，我们选择邻接矩阵的右上部分，这就保证了每条边起始点都比终点来得小，不然后面获得终点的时候就乱了
def getEdges(self):
for i in range(len(self.martix)):
for j in range(i+1,len(self.martix[i])):
if self.martix[i][j] != float("inf"):
#单一条边
self.edge = []
# print(self.martix[i][j])
self.alledgesnum += 1
self.edge.append(self.vertex[I])
self.edge.append(self.vertex[j])
self.edge.append(self.martix[i][j])
self.edges.append(self.edge)
# print((self.edges))
return (self.edges)
#获得某一个字符对应在vertex中的位置
def getPosition(self,ch):
for i in range(len(self.vertex)):
if self.vertex[i] == ch:
return I
else:
return -1
#将边的集合按照权重排序（生序，冒泡法）
def sortEdges(self,edges):
self.edges = edges
for i in range(len(self.edges)):
for j in range(len(self.edges)):
if self.edges[i][2] < self.edges[j][2]:
self.edges[i],self.edges[j] = self.edges[j],self.edges[I]
return self.edges
#这个函数是精华，这个函数可以获得某个字符对应的终点的索引
#先判断它是否为0，若为0说明以它为起点的边还没有被我们选中。
#如果不为0说明以它为起点的边已经被我们选中，我们需要找到最终的终点，那就需要用while，而不能仅仅是if
#直到找到最后为0了，把这个位置返回就是我们要找的终点了，
def getEnd(self,ch):
self.pos = self.getPosition(ch)
if self.endlist[self.pos] == 0:
return self.pos
#while 是精华
while self.endlist[self.pos] != 0:
self.pos = self.endlist[self.pos]
return self.pos
#前面的准备工作做好之后，真正的算法其实就很简单了，首先需要获得排序后的边，然后遍历它
#每获得一条边之后就去获取这条边两个顶点各自对应的终点，如果相等说明说你不能再添加它们进去了，不然就形成回路了
#如果不等，那么把这条边添加到resule列表里， 并把这条边结束位置的终点 赋值给 起始位置的终点，就说明了从起始位置到结束位置的终点整个都连起来了
#至于为什么我们不需要给结束位置的终点赋值 是因为，它现在是作为结束位置，它作为初始位置又还没有跟别的顶点连线被我们选择，那么这个时候它对应的endlist就为0
#这时候返回的是它本身，所以就不需要赋值了。因为作为结束位置你赋值也是赋值它本身。
def kruskal(self):
self.edges = self.getEdges()
self.sortedges = self.sortEdges(self.edges)
for i in range(len(self.sortedges)):
end1 = self.getEnd(self.sortedges[i][0])
end2 = self.getEnd(self.sortedges[i][1])
print("----------------------------------------------------------------")
print(self.sortedges[i][0],end1,self.sortedges[i][1],end2)
if end1 != end2 :
self.result.append(self.sortedges[I])
self.endlist[end1] = end2
print(self.result)
print(self.endlist)
inf = float("inf")
vertex = ['A','B','C','D','E','F','G']
martix = [
[0,12,inf,inf,inf,16,14],
[12,0,10,inf,inf,7,inf],
[inf,10,0,3,5,6,inf],
[inf,inf,3,0,4,inf,inf],
[inf,inf,5,4,0,2,8],
[16,7,6,inf,2,0,9],
[14,inf,inf,inf,8,9,0]]
kruskal = Kruskal(vertex,martix)
kruskal.kruskal()
结果
8 迪杰斯特拉算法
1 迪杰斯特拉(Dijkstra)算法介绍
迪杰斯特拉(Dijkstra)算法是典型最短路径算法，用于计算一个结点到其他结点的最短路径。它的主要特点是以
起始点为中心向外层层扩展(广度优先搜索思想)，直到扩展到终点为止。
2 迪杰斯特拉(Dijkstra)算法过程
- 设置出发顶点为v，顶点集合V{v1,v2,vi...}，v 到V 中各顶点的距离构成距离集合Dis，Dis{d1,d2,di...}，Dis集合记录着v 到图中各顶点的距离(到自身可以看作0，v 到vi 距离对应为di)
- 从Dis 中选择值最小的di 并移出Dis 集合，同时移出V 集合中对应的顶点vi，此时的v 到vi 即为最短路径
- 更新Dis 集合，更新规则为：比较v 到V 集合中顶点的距离值，与v 通过vi 到V 集合中顶点的距离值，保留值较小的一个(同时也应该更新顶点的前驱节点为vi，表明是通过vi 到达的)
-
重复执行两步骤，直到最短路径顶点为目标顶点即可结束
3 迪杰斯特拉代码实现
class Dijkstra():
def __init__(self,vertix,martix,ch):
#顶点
self.vertix = vertix
#邻接矩阵
self.martix = martix
#已访问
self.already_arr = [0 for i in range(len(self.vertix))]
#前序
self.pre_visited = []
#到start顶点的距离
self.distance = []
self.inf = float("inf")
#广度遍历第几层
self.index = 0
#起点结点
self.start = ch
#广度遍历的树
self.tree = []
self.tree.append(list(self.start))
#为起点初始化
self.visit(self.start)
self.Print()
#通过起点更新
self.update(self.start)
self.Print()
#需要先初始化 already_arr 、 pre_visited、distance
def visit(self,ch):
pos = self.getpos(ch)
self.already_arr[pos] = self.index+1
self.pre_visited1 = [-1 for i in range(len(self.vertix))]
self.pre_visited.append(self.pre_visited1)
self.distance1 = [self.inf for i in range(len(self.vertix))]
self.distance1[pos] = 0
self.distance.append(self.distance1)
#传进来一个字符，返回其在vertix 的位置
def getpos(self,ch):
for i in range(len(self.vertix)):
if self.vertix[i] == ch:
return I
elif i == len(self.vertix):
return -1
#传进来一个字符，会以当前字符为顶点，广度遍历其子结点
def update(self,ch):
self.pos = self.getpos(ch)
self.vertixDisthList = self.martix[self.pos]
self.already_arr[self.pos] = 1
for i in range(len(self.vertixDisthList)):
#什么时候需要更新？ 第i个顶点未被访问过且len 小于出发顶点到第i个顶点的距离,
# 距离= 当前顶点ch 到出发顶点的距离 + 当前顶点到第i个顶点的距离
self.length = self.distance[0][self.pos] + self.martix[i][self.pos]
if self.already_arr[i] == 0 and self.length <= self.distance[0][I]:
self.pre_visited[0][i] = self.pos
self.distance[0][i] = self.length
def dijkstra(self):
#当不是所有的already_arr里的元素都为1时 就要一直循环
while self.already_arr.count(1) != len(self.vertix):
#当本层树不为空时就一直循环
while (len(self.tree[self.index]) != 0):
#每次都从当前层的树里拿出一个值
self.curvertix = self.tree[self.index].pop()
self.treedemo = []
#遍历当前字符的子字符，若子字符没有找过 且 子字符到当前距离不为inf 则此字符是我们要找的字符，加到 treedemo里
for i in range(len(self.already_arr)):
if self.already_arr[i] == 0 and self.martix[self.getpos(self.curvertix)][i] < self.inf :
self.treedemo.append(self.vertix[I])
#给treedemo 从大到小排序 pop的时候就从小到大pop，我认为是需要排序的，不然你先加了一个进去，结果不是最近的点，但是已经标记为alreaddy_arr 就不能再更改它了
self.treedemo = self.sort(self.treedemo,self.curvertix)
#遍历treedemo 去更新 注意更新 和 取得子字符并添加到treedemo 是分开的
for i in range(len(self.treedemo)-1,-1,-1):
self.update(self.treedemo[I])
print(self.treedemo[I])
self.Print()
#本层tree遍历完就将treedemo 添加到tree 里， 并遍历这个treedemo
self.tree.append(self.treedemo)
self.index += 1
# 从大到小排序
def sort(self,list,pre):
self.list = list
self.pos = self.getpos(pre)
for i in range(len(self.list)-1):
self.posi = self.getpos(self.list[I])
for j in range(i+1,len(self.list)):
self.posj = self.getpos(self.list[j])
if self.martix[self.pos][self.posi] < self.martix[self.pos][self.posj]:
self.list[i],self.list[j] = self.list[j],self.list[i]
return self.list
def Print(self):
print(self.already_arr)
print(self.pre_visited)
print(self.distance)
inf = float("inf")
vertix = ['A','B','C','D','E','F','G']
martix = [
[inf,2,7,inf,inf,inf,11],
[2,inf,inf,9,inf,inf,8],
[7,inf,inf,inf,8,inf,inf],
[inf,9,inf,inf,inf,4,inf],
[inf,inf,8,inf,inf,5,4],
[inf,inf,inf,4,5,inf,10],
[11,8,inf,inf,4,10,inf]
]
djs = Dijkstra(vertix,martix,'G')
djs.dijkstra()
# djs.Print()
结果：
9 弗洛伊德算法
1 弗洛伊德(Floyd)算法介绍:
(1) 和Dijkstra 算法一样，弗洛伊德(Floyd)算法也是一种用于寻找给定的加权图中顶点间最短路径的算法。该算法
名称以创始人之一、1978 年图灵奖获得者、斯坦福大学计算机科学系教授罗伯特·弗洛伊德命名
(2) 弗洛伊德算法(Floyd)计算图中各个顶点之间的最短路径
(3) 迪杰斯特拉算法用于计算图中某一个顶点到其他顶点的最短路径。
(4) 弗洛伊德算法 VS 迪杰斯特拉算法：迪杰斯特拉算法通过选定的被访问顶点，求出从出发访问顶点到其他顶点
的最短路径；弗洛伊德算法中每一个顶点都是出发访问点，所以需要将每一个顶点看做被访问顶点，求出从每
一个顶点到其他顶点的最短路径。
2 弗洛伊德(Floyd)算法图解分析:
(1) 设置顶点vi 到顶点vk 的最短路径已知为Lik，顶点vk 到vj 的最短路径已知为Lkj，顶点vi 到vj 的路径为Lij，则vi 到vj 的最短路径为：min((Lik+Lkj),Lij)，vk 的取值为图中所有顶点，则可获得vi 到vj 的最短路径
(2) 至于vi 到vk 的最短路径Lik 或者vk 到vj 的最短路径Lkj，是以同样的方式获得
(3) 弗洛伊德(Floyd)算法图解分析-举例说明
步骤：
第一轮循环中，以A(下标为：0)作为中间顶点【即把A 作为中间顶点的所有情况都进行遍历, 就会得到更新距离表 和 前驱关系】，
- 以A 顶点作为中间顶点是，B->A->C 的距离由N->9，同理C 到B；C->A->G 的距离由N->12，同理G 到C
- 更换中间顶点，循环执行操作，直到所有顶点都作为中间顶点更新后，计算结束
- 最终可以获得从任意一个顶点到另外一个顶点最短的距离为多少，并且路径也能显示（路径还没有完全实现，还有点问题）
3 代码实现
# Floyd
class Floyd():
def __init__(self,vertix,martix,ch):
#顶点
self.vertix = vertix
#邻接矩阵
self.martix = martix
#前序
self.pre_visited = [[]for i in range(len(self.vertix))]
for j in self.vertix:
self.pos = self.getpos(j)
for i in range(len(self.vertix)):
self.pre_visited[self.pos].append(j)
#距离表直接拿邻接矩阵实时更新
self.distance = self.martix
self.inf = float("inf")
#传进来一个字符，返回其在vertix 的位置
def getpos(self,ch):
for i in range(len(self.vertix)):
if self.vertix[i] == ch:
return I
elif i == len(self.vertix):
return -1
def floyd(self):
#中间顶点 i g 6
for i in range(len(self.vertix)):
#起始顶点 j a 0
for j in range(len(self.vertix)):
#终止顶点 k d 3
for k in range(len(self.vertix)):
if j == i or k == i or j == k :
continue
else:
self.length = self.distance[i][j] + self.distance[i][k]
if self.length < self.distance[j][k]:
self.distance[j][k] = self.length
self.pre_visited[j][k] = self.pre_visited[i][k]
self.Print()
def Print(self):
for i in range(len(self.vertix)):
print(self.pre_visited[I])
print(self.distance[I])
for j in range(len(self.vertix)):
print(self.vertix[i], "->" , self.vertix[j] , "经过" , self.pre_visited[i][j] , " 距离为：" , self.distance[i][j])
inf = float("inf")
vertix = ['A','B','C','D','E','F','G']
martix = [
[0,5,7,inf,inf,inf,2],
[5,0,inf,9,inf,inf,3],
[7,inf,0,inf,8,inf,inf],
[inf,9,inf,0,inf,4,inf],
[inf,inf,8,inf,0,5,4],
[inf,inf,inf,4,5,0,6],
[2,3,inf,inf,4,6,0]
]
djs = Floyd(vertix,martix,'G')
djs.floyd()
# djs.Print()
结果：
10 马踏棋盘算法
10.1 马踏棋盘算法介绍
- 马踏棋盘算法也被称为骑士周游问题
- 将马随机放在国际象棋的8×8 棋盘Board[0～7][0～7]的某个方格中，马按走棋规则(马走日字)进行移动。要求
每个方格只进入一次，走遍棋盘上全部64 个方格
10.2 马踏棋盘游戏代码实现 - 马踏棋盘问题(骑士周游问题)实际上是图的深度优先搜索(DFS)的应用。
- 如果使用回溯（就是深度优先搜索）来解决，假如马儿踏了53 个点，如图：走到了第53 个，坐标（1,0），发
现已经走到尽头，没办法，那就只能回退了，查看其他的路径，就在棋盘上不停的回溯...... ，思路分析+代码
实现
