1 二分查找算法(非遞歸)
1.1 二分查找算法(非遞歸)代碼實(shí)現(xiàn)：
#二分查找法（非遞歸）
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) 分治法是一種很重要的算法。字面上的解釋是“分而治之”，就是把一個(gè)復(fù)雜的問(wèn)題分成兩個(gè)或更多的相同或相似的子問(wèn)題，再把子問(wèn)題分成更小的子問(wèn)題......直到最后子問(wèn)題可以簡(jiǎn)單的直接求解，原問(wèn)題的解即子問(wèn)題的解的合并。這個(gè)技巧是很多高效算法的基礎(chǔ)，如排序算法(快速排序，歸并排序)，傅立葉變換(快速傅立葉變換)......
(2) 分治算法可以求解的一些經(jīng)典問(wèn)題
二分搜索
大整數(shù)乘法
棋盤覆蓋
合并排序
快速排序
線性時(shí)間選擇
最接近點(diǎn)對(duì)問(wèn)題
循環(huán)賽日程表
漢諾塔分治算法的基本步驟
分治法在每一層遞歸上都有三個(gè)步驟：
(1) 分解：將原問(wèn)題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問(wèn)題形式相同的子問(wèn)題
(2) 解決：若子問(wèn)題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個(gè)子問(wèn)
(3) 合并：將各個(gè)子問(wèn)題的解合并為原問(wèn)題的解。
3.分治算法-漢諾塔的實(shí)現(xiàn)
#遞歸漢諾塔
#漢諾塔思路：可以把漢諾塔當(dāng)成兩層來(lái)看，上層是num-1 下層是num
class Hanoitower():
def process(self,num,A,B,C,):
if (num == 1):
#如果只有一個(gè)盤直接把A柱的盤移動(dòng)到C柱
print(num , A + "->" +C)
else:
#1.把上層的盤從A柱移動(dòng)到B柱，這么想，如果上層只有一個(gè)盤的時(shí)候，調(diào)用process會(huì)直接輸出，那么這時(shí)候會(huì)輸出A->C 注意這不是字符而是變量， 因此你需要傳遞參數(shù)的時(shí)候把B傳給process的C，這樣就可以直接輸出了第一步從A柱到B柱
self.process(num-1,A,C,B)
#2.輸出把下層從A柱移動(dòng)到C柱，和只有一層的情況一樣。
print(num, A + "->" + C)
#3.把現(xiàn)在在B柱的上層移動(dòng)到C柱，很明顯，這會(huì)因?yàn)橐{(diào)用process還是輸出的A->C，因此這里把B傳給A就可以，C還是C
self.process(num-1,B,A,C)
hanoi = Hanoitower()
hanoi.process(3,"A","B","C")
3 動(dòng)態(tài)規(guī)劃算法
- 動(dòng)態(tài)規(guī)劃算法介紹：
(1) 動(dòng)態(tài)規(guī)劃(Dynamic Programming)算法的核心思想是：將大問(wèn)題劃分為小問(wèn)題進(jìn)行解決，從而一步步獲取最優(yōu)解
的處理算法
(2) 動(dòng)態(tài)規(guī)劃算法與分治算法類似，其基本思想也是將待求解問(wèn)題分解成若干個(gè)子問(wèn)題，先求解子問(wèn)題，然后從這
些子問(wèn)題的解得到原問(wèn)題的解。
(3) 與分治法不同的是，適合于用動(dòng)態(tài)規(guī)劃求解的問(wèn)題，經(jīng)分解得到子問(wèn)題往往不是互相獨(dú)立的。 ( 即下一個(gè)子
階段的求解是建立在上一個(gè)子階段的解的基礎(chǔ)上，進(jìn)行進(jìn)一步的求解 )
(4) 動(dòng)態(tài)規(guī)劃可以通過(guò)填表的方式來(lái)逐步推進(jìn)，得到最優(yōu)解.
2 應(yīng)用場(chǎng)景-背包問(wèn)題
背包問(wèn)題：有一個(gè)背包，容量為4 磅 ， 現(xiàn)有如下物品:
- 要求達(dá)到的目標(biāo)為裝入的背包的總價(jià)值最大，并且重量不超出
- 要求裝入的物品不能重復(fù)
-
思路：
(1) 背包問(wèn)題主要是指一個(gè)給定容量的背包、若干具有一定價(jià)值和重量的物品，如何選擇物品放入背包使物品的價(jià)值最大。其中又分01 背包和完全背包(完全背包指的是：每種物品都有無(wú)限件可用)
(2) 這里的問(wèn)題屬于01 背包，即每個(gè)物品最多放一個(gè)。而無(wú)限背包可以轉(zhuǎn)化為01 背包。
(3) 算法的主要思想，利用動(dòng)態(tài)規(guī)劃來(lái)解決。每次遍歷到的第i 個(gè)物品，根據(jù)w[i]和v[i]來(lái)確定是否需要將該物品放入背包中。即對(duì)于給定的n 個(gè)物品，設(shè)v[i]、w[i]分別為第i 個(gè)物品的價(jià)值和重量，C 為背包的容量。再令v[i][j]表示在前i 個(gè)物品中能夠裝入容量為j 的背包中的最大價(jià)值。
3 代碼實(shí)現(xiàn)：
#動(dòng)態(tài)規(guī)劃 背包問(wèn)題
#動(dòng)態(tài)規(guī)劃的核心在于，它不是用遞歸也不用while循環(huán)，而是用for循環(huán)，通過(guò)之前得到的值做調(diào)整，通過(guò)之前的值這便是動(dòng)態(tài)規(guī)劃
#本算法目的是要得到一個(gè)這種表格，最右下角便是最優(yōu)解
#[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]
#物品價(jià)值
self.values= [1500,3000,2000,5000]
#背包最大容量
self.maxcapacity = 9
#最大價(jià)值
#1.先把表哥第0行第0列置0，必須置0因?yàn)榈?行可能用到第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？ 因?yàn)槲覀兌嗔艘恍腥? 以及一列全0 也就是第i個(gè)商品self.values[i] 其實(shí)相當(dāng)于maxvalue第i+1行self.maxvalue[i]，至于列的話因?yàn)閺?開始遍歷遍歷到10，那么就可以和容量對(duì)應(yīng)上了，因此不需要j+1
#2.如果當(dāng)前物品的重量小于等于背包剩余容量的話，先把容量扣掉，再讓當(dāng)前物品的最大價(jià)值self.maxvalue[i+1][j] = max(self.maxvalue[i][j], self.values[i]+self.maxvalue[i][self.remainingcapacity])
#self.maxvalue[i][j]表示上一行的值，因?yàn)榭赡苣慵由袭?dāng)前物品的價(jià)值還不如之前不加當(dāng)前物品的價(jià)值多，那么就要用之前的策略
# self.values[i]+self.maxvalue[i][self.remainingcapacity] 表示 當(dāng)前物品的價(jià)值+剩余容量的最大價(jià)值，這個(gè)怎么找呢？
# 首先我們已經(jīng)又的剩余容量也就是self.remainingcapacity，所以找這列，然后找這一列的盡量下面一個(gè)也就是第i行，為什么不是本行i+1行呢，因?yàn)檫@個(gè)是01背包，你第i+1行算的是第i個(gè)商品，
# 此時(shí)你再前面已經(jīng)把第i個(gè)商品的價(jià)值給加上了，因此這里只能用第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：什么時(shí)候需要做標(biāo)記，首先你肯定要先把物品加進(jìn)來(lái)，其次加進(jìn)來(lái)之后，你要保證加得有意義，也就是 self.maxvalue[i][j] < self.values[i]+self.maxvalue[i][self.remainingcapacity]
#如果沒(méi)有，那就是拿上次的結(jié)果就可以了，這次就沒(méi)有必要標(biāo)記了
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.如果當(dāng)前物品的重量大于背包剩余容量的話，也就是放不下了，就拿上一行的數(shù)據(jù)就行了
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方法：
#從最后一行最后一列也就是最后一個(gè)開始找，如果有做標(biāo)記就把該行也就是i也就是第幾個(gè)物品輸出出來(lái)。那么就要把容量扣掉，再去找，如果這一行沒(méi)有找到就往上一行找，如果有一定找得到，可能不在本行在上一行，否則直到最后找到第-1行就退出
while (i>=0 and j>=0):
if self.path[i][j] == 1:
print("添加第",i,"個(gè)物品到包里")
j -= self.weights[i-1]
else:
i -=1
knapsack = KnapsackProblem()
knapsack.plan()
結(jié)果
4 KMP算法：
1 應(yīng)用場(chǎng)景-字符串匹配問(wèn)題:
(1) 有一個(gè)字符串 str1= "ababababc"，和一個(gè)子串 str2="ababc"
(2) 現(xiàn)在要判斷 str1 是否含有 str2, 如果存在，就返回第一次出現(xiàn)的位置, 如果沒(méi)有，則返回-1
2 KMP算法介紹：
(1) KMP 是一個(gè)解決模式串在文本串是否出現(xiàn)過(guò)，如果出現(xiàn)過(guò)，最早出現(xiàn)的位置的經(jīng)典算法
(2) Knuth-Morris-Pratt 字符串查找算法，簡(jiǎn)稱為 “KMP 算法”，常用于在一個(gè)文本串S 內(nèi)查找一個(gè)模式串P 的出現(xiàn)位置，這個(gè)算法由Donald Knuth、Vaughan Pratt、James H. Morris 三人于1977 年聯(lián)合發(fā)表，故取這3 人的姓氏命名此算法.
(3) KMP 方法算法就利用之前判斷過(guò)信息，通過(guò)一個(gè)next 數(shù)組，保存模式串中前后最長(zhǎng)公共子序列的長(zhǎng)度，每次回溯時(shí)，通過(guò)next 數(shù)組找到，前面匹配過(guò)的位置，省去了大量的計(jì)算時(shí)間
(4) 參考資料：https://www.cnblogs.com/ZuoAndFutureGirl/p/9028287.html
3 kmp算法代碼實(shí)現(xiàn)：
#kmp算法：
#首先定義一下next數(shù)組的意義：
#例如有一個(gè)字符串，對(duì)應(yīng)的next數(shù)組如下
#a b c a b a b c a b c
#0 0 0 1 2 1 2 3 4 5 3
#next數(shù)組的值表示搜索到當(dāng)前字符的時(shí)候，包括其自身字符的最大重復(fù)子串的個(gè)數(shù)
#例如搜索到abcababc的時(shí)候此時(shí)i=7 j=2 相等則 j+=1 next.append(j) i += 1 再繼續(xù)搜索下去
#因此就有以下三種情況：
#1.相等即str1[i]==str1[j]
#2.若str1[i]!=str1[j]且j==0的情況，這個(gè)時(shí)候是還沒(méi)有匹配到重復(fù)的子串如剛開始的abc，直接把0添加到next數(shù)組，并讓 i+=1
#3.最難的是str1[i]!=str1[j] 且 j!=0的情況，這時(shí)候不能直接讓j置0
#如abcababcabc 當(dāng)匹配到倒數(shù)第二個(gè)字符的時(shí)候此時(shí)i=9,j=4,此時(shí)相等，那么就j +=1 next.append(j) i +=1，此時(shí)就是i=10，j=5此時(shí)str1[i]!=str1[j]若直接把j置0
#那么 仍然str1[i]!=str1[j]且j==0，就會(huì)直接把0給加到next數(shù)組里面去，代表此時(shí)最大重復(fù)子串為0很明顯不是的，此時(shí)最大重復(fù)子串的長(zhǎng)度應(yīng)該為3
#問(wèn)題就出在這，因?yàn)槲覀儜?yīng)該讓j = next[j-1] 這句話怎么理解？
#還是比如我們找到最后一個(gè)字符c ， 此時(shí)i=10，j=5，我們知道str[0:4] str1[5:9]是重復(fù)的，因?yàn)閕=9時(shí)，next[9]=5，也就是str1[0:j-1] str1[j:i-1]是相等的，（其實(shí)數(shù)學(xué)原理不是這樣的，我們只是想了一個(gè)特例）
#那么我們就應(yīng)該去找搜索到第i-1個(gè)字符時(shí)的最大重復(fù)子串的長(zhǎng)度，也就是i=4時(shí)，next[i]=? ，因?yàn)槲覀冋业搅薸=4的最大重復(fù)字串比如 i=4時(shí)->“abcab”,最大重復(fù)字串是"ab",而str1[j:i-1] 與str1[0:j-1]又是相等的
#因此str1[j:i-1] 與整個(gè)字符串的最大重復(fù)字串就是“ab”，
#上面分析的實(shí)例：
#1.a b c a b a b c a b c 加了c之后不等
#2.由于前半段a b c a b 和后半段a b c a b 是重復(fù)的
#3.找到前半段a b c a b 的最大重復(fù)字串那么肯定和后半段a b c a b也是重復(fù)的，因此此時(shí)我們就從c這個(gè)位置開始比對(duì)最后一個(gè)字符，
#4.這里為什么直接找next[4]就可以了，因?yàn)檫@里存的是2，也就是j=2，那么就找到的是c而不是b，因此可以直接與最后一個(gè)字符進(jìn)行比較
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)
#接下來(lái)是kmp算法，當(dāng)你實(shí)現(xiàn)了求next數(shù)組之后kmp算法就簡(jiǎn)單了
#首先是需要傳入兩個(gè)字符串，一個(gè)是初始字符串，一個(gè)是搜索字符串
#1.先獲得搜索字符串的next數(shù)組
#2.將初始字符串與搜索字符串一個(gè)一個(gè)進(jìn)行對(duì)比，同樣有三種情況：
#2.1 若相等的話，不用考慮j是否為0反正都要 jk+=1，但是這里需要判斷是否輸出，因?yàn)榧偃鐒偤媚阋呀?jīng)匹配完整個(gè)searchlist了并且最后一個(gè)字符還與當(dāng)前的initlist[i]相等，說(shuō)明整個(gè)搜索字符串相等，那就返回i-j
#2.2 如果不等就需要判斷j是否為0，如果為0那么意味著，當(dāng)前字符與搜索字符串的第0個(gè)字符就不想等，因此把當(dāng)前字符往后移一位就行，也就是i+=1， j不用動(dòng)
#2.3 如果j不等于0，那么就要找到當(dāng)前字符的前一個(gè)next值，例如找到i=j=4的時(shí)候 這時(shí)候 initlist[4]=a ,searchlist[4]=c ，不等，那么就需要找到nextlist[3]的值代表著searchalist[0:4]
# 這個(gè)字符串中最大的重復(fù)字串，那么這些就不用再比了，只要比最大重復(fù)字串的后一個(gè)字符就行，因此j=2 也就是從a開始比，這時(shí)候i也不需要懂，因?yàn)閕之前的字串肯定和這個(gè)最大的重復(fù)字串也重復(fù)，因此直接比對(duì)就可以
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 應(yīng)用場(chǎng)景-集合覆蓋問(wèn)題
假設(shè)存在下面需要付費(fèi)的廣播臺(tái)，以及廣播臺(tái)信號(hào)可以覆蓋的地區(qū)。 如何選擇最少的廣播臺(tái)，讓所有的地區(qū)都可以接收到信號(hào)
2 貪心算法介紹
(1) 貪婪算法(貪心算法)是指在對(duì)問(wèn)題進(jìn)行求解時(shí)，在每一步選擇中都采取最好或者最優(yōu)(即最有利)的選擇，從而希望能夠?qū)е陆Y(jié)果是最好或者最優(yōu)的算法
(2) 貪婪算法所得到的結(jié)果不一定是最優(yōu)的結(jié)果(有時(shí)候會(huì)是最優(yōu)解)，但是都是相對(duì)近似(接近)最優(yōu)解的結(jié)果
3 貪心算法思路分析
(1) 目前并沒(méi)有算法可以快速計(jì)算得到準(zhǔn)備的值， 使用貪婪算法，則可以得到非常接近的解，并且效率高。選擇
策略上，因?yàn)樾枰采w全部地區(qū)的最小集合:
(2) 遍歷所有的廣播電臺(tái), 找到一個(gè)覆蓋了最多未覆蓋的地區(qū)的電臺(tái)(此電臺(tái)可能包含一些已覆蓋的地區(qū)，但沒(méi)有關(guān)
系）
(3) 將這個(gè)電臺(tái)加入到一個(gè)集合中(比如ArrayList), 想辦法把該電臺(tái)覆蓋的地區(qū)在下次比較時(shí)去掉。
(4) 重復(fù)第1 步直到覆蓋了全部的地區(qū)
(5) 圖解：
4 貪心算法代碼實(shí)現(xiàn)：
#貪心算法：
#1.首先需要將各個(gè)電臺(tái)不同的城市加到allcity中，也就是保證allcity每個(gè)元素的唯一性
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初始沒(méi)有元素，因此需要判斷若長(zhǎng)度為0需要將k1的第0個(gè)城市添加進(jìn)來(lái)，以便判斷是否重復(fù)
if len(allcity) == 0:
allcity.append(allradio[i][j])
continue
for k in range(len(allcity)):
#如果在allcity中找到重復(fù)的，那么就不用再遍歷allcity了，繼續(xù)遍歷allradio[i] 就行。
if allradio[i][j] == allcity[k]:
break
#想想什么時(shí)候需要添加進(jìn)來(lái)，就是當(dāng)allcity遍歷完了，此時(shí)k=len(allcity)-1 并且都沒(méi)有找到重復(fù)的。
elif k == len(allcity)-1 :
allcity.append(allradio[i][j])
return (allradio,allcity)
#2.進(jìn)行貪心算法
#2.1
#這里就是拿allradio中的每個(gè)元素即k1,k2,k3,k4,k5中的每個(gè)元素與 allcity進(jìn)行比較，若有重復(fù)的我們讓key+=1，就遍歷本電臺(tái)的下一個(gè)城市
#當(dāng)遍歷完每個(gè)電臺(tái)之后，將此時(shí)的key存入到keylist中，以便后邊與maxkey進(jìn)行比較，此時(shí)如果maxkey<key 的時(shí)候要對(duì)maxkey進(jìn)行更新
#并且當(dāng)每個(gè)電臺(tái)遍歷完后，要對(duì)key進(jìn)行清零
#2.2
# 此時(shí)就獲得了keylist，與maxkey。再去遍歷keylist找到第一個(gè)與maxkey相等的值，這個(gè)便是我們要找的電臺(tái)，將其添加到selectradio中，
# 并把這個(gè)電臺(tái)中的所有城市在 allcity中刪除，這樣就保證這個(gè)電臺(tái)下次的key為0，也就不必?fù)?dān)心我們剛才直接找到第一個(gè)與maxkey相等的值會(huì)不會(huì)不是我們想要的
# 完事之后只需要判斷allcity的長(zhǎng)度是否為0，為0就說(shuō)明刪除完了，就可以返回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)
結(jié)果
6 普里姆算法
6.1 應(yīng)用場(chǎng)景-修路問(wèn)題
(1) 有勝利鄉(xiāng)有7 個(gè)村莊(A, B, C, D, E, F, G) ，現(xiàn)在需要修路把7 個(gè)村莊連通
(2) 各個(gè)村莊的距離用邊線表示(權(quán)) ，比如 A – B 距離 5 公里
(3) 問(wèn)：如何修路保證各個(gè)村莊都能連通，并且總的修建公路總里程最短?
思路: 將10 條邊，連接即可，但是總的里程數(shù)不是最小.
正確的思路，就是盡可能的選擇少的路線，并且每條路線最小，保證總里程數(shù)最少.
6.2 最小生成樹
修路問(wèn)題本質(zhì)就是就是最小生成樹問(wèn)題， 先介紹一下最小生成樹(Minimum Cost Spanning Tree)，簡(jiǎn)稱MST。
給定一個(gè)帶權(quán)的無(wú)向連通圖,如何選取一棵生成樹,使樹上所有邊上權(quán)的總和為最小,這叫最小生成樹
(1) N 個(gè)頂點(diǎn)，一定有N-1 條邊
(2) 包含全部頂點(diǎn)
(3) N-1 條邊都在圖中
(4) 舉例說(shuō)明(如圖:)
(5) 求最小生成樹的算法主要是普里姆算法和克魯斯卡爾算法
6.3 普里姆算法介紹
普利姆(Prim)算法求最小生成樹，也就是在包含n 個(gè)頂點(diǎn)的連通圖中，找出只有(n-1)條邊包含所有n 個(gè)頂點(diǎn)的
連通子圖，也就是所謂的極小連通子圖
普利姆的算法如下:
(1) 設(shè)G=(V,E)是連通網(wǎng)，T=(U,D)是最小生成樹，V,U 是頂點(diǎn)集合，E,D 是邊的集合
(2) 若從頂點(diǎn)u 開始構(gòu)造最小生成樹，則從集合V 中取出頂點(diǎn)u 放入集合U 中，標(biāo)記頂點(diǎn)v 的visited[u]=1
(3) 若集合U 中頂點(diǎn)ui 與集合V-U 中的頂點(diǎn)vj 之間存在邊，則尋找這些邊中權(quán)值最小的邊，但不能構(gòu)成回路，將
頂點(diǎn)vj 加入集合U 中，將邊（ui,vj）加入集合D 中，標(biāo)記visited[vj]=1
(4) 重復(fù)步驟②，直到U 與V 相等，即所有頂點(diǎn)都被標(biāo)記為訪問(wèn)過(guò)，此時(shí)D 中有n-1 條邊
(5) 提示: 單獨(dú)看步驟很難理解，我們通過(guò)代碼來(lái)講解，比較好理解.
(6) 圖解普利姆算法:
6.4 普里姆算法代碼實(shí)現(xiàn)：
#普里姆算法（最小生成樹問(wèn)題）
#構(gòu)建圖，包括verxs 頂點(diǎn)（結(jié)點(diǎn)）個(gè)數(shù)、data 頂點(diǎn)數(shù)據(jù)，weight邊的權(quán)重
class MGraph():
def __init__(self,verxs,data,weights):
self.verxs = verxs
self.data = data
self.weights = weights
#普里姆算法的實(shí)現(xiàn)：
# 1.我們知道普里姆算法有個(gè)公式 N個(gè)結(jié)點(diǎn)一定有N-1條邊， 因此我們首先要循環(huán) len(self.graph.data)-1 次 獲取這么多條邊
# 2.先遍歷self.visited 再遍歷 self.graph.weights[i] 因?yàn)槲覀円韧ㄟ^(guò)self.visited 里的數(shù)據(jù)，確定這次選邊的一個(gè)結(jié)點(diǎn)，因?yàn)槲覀冃枰日业桨趕elf.visited 里面所有結(jié)點(diǎn)所有不重復(fù)的邊 ，再通過(guò)遍歷 self.graph.weights[i]確定另一個(gè)結(jié)點(diǎn)
# 3.因此不管是判斷這條邊的權(quán)重是否為10000（是否連通）， 或者 這條邊的權(quán)重是否小于minweight 都是通過(guò)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說(shuō)明沒(méi)有連通，遍歷下一個(gè)結(jié)點(diǎn)也就是遍歷下條邊
if self.graph.weights[k][j] == 10000:
continue
#這里需要判斷 j 是否在 visited列表里， 若在說(shuō)明這條邊已經(jīng)存在不需要再比較了
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)
結(jié)果
7 克魯斯卡爾算法
1.克魯斯卡爾算法介紹
(1) 克魯斯卡爾(Kruskal)算法，是用來(lái)求加權(quán)連通圖的最小生成樹的算法。
(2) 基本思想：按照權(quán)值從小到大的順序選擇n-1 條邊，并保證這n-1 條邊不構(gòu)成回路
(3) 具體做法：首先構(gòu)造一個(gè)只含n 個(gè)頂點(diǎn)的森林，然后依權(quán)值從小到大從連通網(wǎng)中選擇邊加入到森林中，并使森林中不產(chǎn)生回路，直至森林變成一棵樹為止
2.思路圖解：
-
難點(diǎn)分析：
克魯斯卡爾算法重點(diǎn)需要解決的以下兩個(gè)問(wèn)題：
問(wèn)題一 對(duì)圖的所有邊按照權(quán)值大小進(jìn)行排序。采用排序算法進(jìn)行排序即可。
問(wèn)題二 將邊添加到最小生成樹中時(shí)，怎么樣判斷是否形成了回路？
記錄頂點(diǎn)在"最小生成樹"中的終點(diǎn)，頂點(diǎn)的終點(diǎn)是"在最小生成樹中與它連通的最大頂點(diǎn)"。然后每次需要將一條邊添加到最小生存樹時(shí)，判斷該邊的兩個(gè)頂點(diǎn)的終點(diǎn)是否重合，重合的話則會(huì)構(gòu)成回路。
終點(diǎn)重合分析 - 代碼實(shí)現(xiàn)
#克 魯 斯 卡 爾 算 法 - 公 交 問(wèn) 題
class Kruskal():
def __init__(self,vertex,martix):
#vertex : 頂點(diǎn)數(shù)組
self.vertex = vertex
#martix : 鄰接矩陣
self.martix = martix
#所有邊的數(shù)量
self.alledgesnum = 0
#所有邊的集合
self.edges = []
#頂點(diǎn)數(shù)組對(duì)應(yīng)的終點(diǎn)列表
self.endlist = [0 for i in range(len(self.vertex))]
#最小生成樹結(jié)果
self.result = []
#通過(guò)遍歷鄰接矩陣將邊的信息添加到self.edges中。 [['E', 'F', 2], ['C', 'D', 3], ['D', 'E', 4]...]
#這里很巧妙的是，我們選擇鄰接矩陣的右上部分，這就保證了每條邊起始點(diǎn)都比終點(diǎn)來(lái)得小，不然后面獲得終點(diǎn)的時(shí)候就亂了
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)
#獲得某一個(gè)字符對(duì)應(yīng)在vertex中的位置
def getPosition(self,ch):
for i in range(len(self.vertex)):
if self.vertex[i] == ch:
return I
else:
return -1
#將邊的集合按照權(quán)重排序（生序，冒泡法）
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
#這個(gè)函數(shù)是精華，這個(gè)函數(shù)可以獲得某個(gè)字符對(duì)應(yīng)的終點(diǎn)的索引
#先判斷它是否為0，若為0說(shuō)明以它為起點(diǎn)的邊還沒(méi)有被我們選中。
#如果不為0說(shuō)明以它為起點(diǎn)的邊已經(jīng)被我們選中，我們需要找到最終的終點(diǎn)，那就需要用while，而不能僅僅是if
#直到找到最后為0了，把這個(gè)位置返回就是我們要找的終點(diǎn)了，
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
#前面的準(zhǔn)備工作做好之后，真正的算法其實(shí)就很簡(jiǎn)單了，首先需要獲得排序后的邊，然后遍歷它
#每獲得一條邊之后就去獲取這條邊兩個(gè)頂點(diǎn)各自對(duì)應(yīng)的終點(diǎn)，如果相等說(shuō)明說(shuō)你不能再添加它們進(jìn)去了，不然就形成回路了
#如果不等，那么把這條邊添加到resule列表里， 并把這條邊結(jié)束位置的終點(diǎn) 賦值給 起始位置的終點(diǎn)，就說(shuō)明了從起始位置到結(jié)束位置的終點(diǎn)整個(gè)都連起來(lái)了
#至于為什么我們不需要給結(jié)束位置的終點(diǎn)賦值 是因?yàn)?，它現(xiàn)在是作為結(jié)束位置，它作為初始位置又還沒(méi)有跟別的頂點(diǎn)連線被我們選擇，那么這個(gè)時(shí)候它對(duì)應(yīng)的endlist就為0
#這時(shí)候返回的是它本身，所以就不需要賦值了。因?yàn)樽鳛榻Y(jié)束位置你賦值也是賦值它本身。
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()
結(jié)果
8 迪杰斯特拉算法
1 迪杰斯特拉(Dijkstra)算法介紹
迪杰斯特拉(Dijkstra)算法是典型最短路徑算法，用于計(jì)算一個(gè)結(jié)點(diǎn)到其他結(jié)點(diǎn)的最短路徑。它的主要特點(diǎn)是以
起始點(diǎn)為中心向外層層擴(kuò)展(廣度優(yōu)先搜索思想)，直到擴(kuò)展到終點(diǎn)為止。
2 迪杰斯特拉(Dijkstra)算法過(guò)程
- 設(shè)置出發(fā)頂點(diǎn)為v，頂點(diǎn)集合V{v1,v2,vi...}，v 到V 中各頂點(diǎn)的距離構(gòu)成距離集合Dis，Dis{d1,d2,di...}，Dis集合記錄著v 到圖中各頂點(diǎn)的距離(到自身可以看作0，v 到vi 距離對(duì)應(yīng)為di)
- 從Dis 中選擇值最小的di 并移出Dis 集合，同時(shí)移出V 集合中對(duì)應(yīng)的頂點(diǎn)vi，此時(shí)的v 到vi 即為最短路徑
- 更新Dis 集合，更新規(guī)則為：比較v 到V 集合中頂點(diǎn)的距離值，與v 通過(guò)vi 到V 集合中頂點(diǎn)的距離值，保留值較小的一個(gè)(同時(shí)也應(yīng)該更新頂點(diǎn)的前驅(qū)節(jié)點(diǎn)為vi，表明是通過(guò)vi 到達(dá)的)
-
重復(fù)執(zhí)行兩步驟，直到最短路徑頂點(diǎn)為目標(biāo)頂點(diǎn)即可結(jié)束
3 迪杰斯特拉代碼實(shí)現(xiàn)
class Dijkstra():
def __init__(self,vertix,martix,ch):
#頂點(diǎn)
self.vertix = vertix
#鄰接矩陣
self.martix = martix
#已訪問(wèn)
self.already_arr = [0 for i in range(len(self.vertix))]
#前序
self.pre_visited = []
#到start頂點(diǎn)的距離
self.distance = []
self.inf = float("inf")
#廣度遍歷第幾層
self.index = 0
#起點(diǎn)結(jié)點(diǎn)
self.start = ch
#廣度遍歷的樹
self.tree = []
self.tree.append(list(self.start))
#為起點(diǎn)初始化
self.visit(self.start)
self.Print()
#通過(guò)起點(diǎn)更新
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)
#傳進(jìn)來(lái)一個(gè)字符，返回其在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
#傳進(jìn)來(lái)一個(gè)字符，會(huì)以當(dāng)前字符為頂點(diǎn)，廣度遍歷其子結(jié)點(diǎn)
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)):
#什么時(shí)候需要更新？ 第i個(gè)頂點(diǎn)未被訪問(wèn)過(guò)且len 小于出發(fā)頂點(diǎn)到第i個(gè)頂點(diǎn)的距離,
# 距離= 當(dāng)前頂點(diǎn)ch 到出發(fā)頂點(diǎn)的距離 + 當(dāng)前頂點(diǎn)到第i個(gè)頂點(diǎn)的距離
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):
#當(dāng)不是所有的already_arr里的元素都為1時(shí) 就要一直循環(huán)
while self.already_arr.count(1) != len(self.vertix):
#當(dāng)本層樹不為空時(shí)就一直循環(huán)
while (len(self.tree[self.index]) != 0):
#每次都從當(dāng)前層的樹里拿出一個(gè)值
self.curvertix = self.tree[self.index].pop()
self.treedemo = []
#遍歷當(dāng)前字符的子字符，若子字符沒(méi)有找過(guò) 且 子字符到當(dāng)前距離不為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的時(shí)候就從小到大pop，我認(rèn)為是需要排序的，不然你先加了一個(gè)進(jìn)去，結(jié)果不是最近的點(diǎn)，但是已經(jīng)標(biāo)記為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 里， 并遍歷這個(gè)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()
結(jié)果：
9 弗洛伊德算法
1 弗洛伊德(Floyd)算法介紹:
(1) 和Dijkstra 算法一樣，弗洛伊德(Floyd)算法也是一種用于尋找給定的加權(quán)圖中頂點(diǎn)間最短路徑的算法。該算法
名稱以創(chuàng)始人之一、1978 年圖靈獎(jiǎng)獲得者、斯坦福大學(xué)計(jì)算機(jī)科學(xué)系教授羅伯特·弗洛伊德命名
(2) 弗洛伊德算法(Floyd)計(jì)算圖中各個(gè)頂點(diǎn)之間的最短路徑
(3) 迪杰斯特拉算法用于計(jì)算圖中某一個(gè)頂點(diǎn)到其他頂點(diǎn)的最短路徑。
(4) 弗洛伊德算法 VS 迪杰斯特拉算法：迪杰斯特拉算法通過(guò)選定的被訪問(wèn)頂點(diǎn)，求出從出發(fā)訪問(wèn)頂點(diǎn)到其他頂點(diǎn)
的最短路徑；弗洛伊德算法中每一個(gè)頂點(diǎn)都是出發(fā)訪問(wèn)點(diǎn)，所以需要將每一個(gè)頂點(diǎn)看做被訪問(wèn)頂點(diǎn)，求出從每
一個(gè)頂點(diǎn)到其他頂點(diǎn)的最短路徑。
2 弗洛伊德(Floyd)算法圖解分析:
(1) 設(shè)置頂點(diǎn)vi 到頂點(diǎn)vk 的最短路徑已知為L(zhǎng)ik，頂點(diǎn)vk 到vj 的最短路徑已知為L(zhǎng)kj，頂點(diǎn)vi 到vj 的路徑為L(zhǎng)ij，則vi 到vj 的最短路徑為：min((Lik+Lkj),Lij)，vk 的取值為圖中所有頂點(diǎn)，則可獲得vi 到vj 的最短路徑
(2) 至于vi 到vk 的最短路徑Lik 或者vk 到vj 的最短路徑Lkj，是以同樣的方式獲得
(3) 弗洛伊德(Floyd)算法圖解分析-舉例說(shuō)明
步驟：
第一輪循環(huán)中，以A(下標(biāo)為：0)作為中間頂點(diǎn)【即把A 作為中間頂點(diǎn)的所有情況都進(jìn)行遍歷, 就會(huì)得到更新距離表 和 前驅(qū)關(guān)系】，
- 以A 頂點(diǎn)作為中間頂點(diǎn)是，B->A->C 的距離由N->9，同理C 到B；C->A->G 的距離由N->12，同理G 到C
- 更換中間頂點(diǎn)，循環(huán)執(zhí)行操作，直到所有頂點(diǎn)都作為中間頂點(diǎn)更新后，計(jì)算結(jié)束
- 最終可以獲得從任意一個(gè)頂點(diǎn)到另外一個(gè)頂點(diǎn)最短的距離為多少，并且路徑也能顯示（路徑還沒(méi)有完全實(shí)現(xiàn)，還有點(diǎn)問(wèn)題）
3 代碼實(shí)現(xiàn)
# Floyd
class Floyd():
def __init__(self,vertix,martix,ch):
#頂點(diǎn)
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)
#距離表直接拿鄰接矩陣實(shí)時(shí)更新
self.distance = self.martix
self.inf = float("inf")
#傳進(jìn)來(lái)一個(gè)字符，返回其在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):
#中間頂點(diǎn) i g 6
for i in range(len(self.vertix)):
#起始頂點(diǎn) j a 0
for j in range(len(self.vertix)):
#終止頂點(diǎn) 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] , "經(jīng)過(guò)" , 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()
結(jié)果：
10 馬踏棋盤算法
10.1 馬踏棋盤算法介紹
- 馬踏棋盤算法也被稱為騎士周游問(wèn)題
- 將馬隨機(jī)放在國(guó)際象棋的8×8 棋盤Board[0～7][0～7]的某個(gè)方格中，馬按走棋規(guī)則(馬走日字)進(jìn)行移動(dòng)。要求
每個(gè)方格只進(jìn)入一次，走遍棋盤上全部64 個(gè)方格
10.2 馬踏棋盤游戲代碼實(shí)現(xiàn) - 馬踏棋盤問(wèn)題(騎士周游問(wèn)題)實(shí)際上是圖的深度優(yōu)先搜索(DFS)的應(yīng)用。
- 如果使用回溯（就是深度優(yōu)先搜索）來(lái)解決，假如馬兒踏了53 個(gè)點(diǎn)，如圖：走到了第53 個(gè)，坐標(biāo)（1,0），發(fā)
現(xiàn)已經(jīng)走到盡頭，沒(méi)辦法，那就只能回退了，查看其他的路徑，就在棋盤上不停的回溯...... ，思路分析+代碼
實(shí)現(xiàn)
