1.二叉樹
1.1 二叉樹類的實(shí)現(xiàn)
首先構(gòu)造節(jié)點(diǎn)類，它的屬性包括元素、左孩子、右孩子。然后構(gòu)造二叉樹類，它的屬性有根節(jié)點(diǎn)。
class Node(object):
def __init__(self, item):
self.elem = item
self.lchild = None
self.rchild = None
class Tree(object):
'''二叉樹類， 需要指定一個(gè)根節(jié)點(diǎn)'''
def __init__(self):
self.root = None
1.2 二叉樹添加元素
首先將新元素構(gòu)造為一個(gè)新的節(jié)點(diǎn)類的實(shí)例，然后根據(jù)廣度優(yōu)先原則首先找到添加節(jié)點(diǎn)的位置，添加節(jié)點(diǎn)。
# 偽代碼如下
def add(self, item):
新節(jié)點(diǎn)node = 新節(jié)點(diǎn)類的實(shí)例
如果根節(jié)點(diǎn)為空，self.root = node.
queue = [self.root] # 用隊(duì)列來存放遍歷的節(jié)點(diǎn)
當(dāng)隊(duì)列不為空：
當(dāng)前節(jié)點(diǎn) = queue 隊(duì)首的節(jié)點(diǎn)，并在queue中刪除該節(jié)點(diǎn)
如果當(dāng)前節(jié)點(diǎn)的左孩子為空：
新節(jié)點(diǎn)賦值給當(dāng)前節(jié)點(diǎn)左孩子
否則：
將當(dāng)前節(jié)點(diǎn)的左孩子加入到隊(duì)列中
如果當(dāng)前節(jié)點(diǎn)的右孩子為空：
新節(jié)點(diǎn)賦值給當(dāng)前節(jié)點(diǎn)右孩子
否則：
將當(dāng)前節(jié)點(diǎn)的右孩子加入到隊(duì)列中
def add(self, item):
node = Node(item)
if self.root is None:
self.root = node
return
queue = [self.root] # 用來存放要處理的東西
while queue:
cur_node = queue.pop(0)
if cur_node.lchild is None:
cur_node.lchild = node
return
else:
queue.append(cur_node.lchild)
if cur_node.rchild is None:
cur_node.rchild = node
return
else:
queue.append(cur_node.rchild)
1.3 二叉樹的廣度優(yōu)先遍歷
廣度優(yōu)先遍歷即先遍歷兄弟節(jié)點(diǎn)，再遍歷孩子節(jié)點(diǎn)。
# 偽代碼
def breadth_travel(self):
如果根為空，直接返回
queue = [self.root] # 將根節(jié)點(diǎn)添加到隊(duì)列
當(dāng)隊(duì)列不為空：
當(dāng)前節(jié)點(diǎn) = queue 隊(duì)首的節(jié)點(diǎn)，并在queue中刪除該節(jié)點(diǎn)
打印出該節(jié)點(diǎn)的元素值
如果當(dāng)前節(jié)點(diǎn)的左孩子非空：
將當(dāng)前節(jié)點(diǎn)的左孩子添加到隊(duì)列中
如果當(dāng)前節(jié)點(diǎn)的右孩子非空：
將當(dāng)前節(jié)點(diǎn)的右孩子添加到隊(duì)列中
def breadth_travel(self):
if self.root is None:
return
queue = [self.root]
while queue:
cur_node = queue.pop(0)
print(cur_node.elem, end=' ')
if cur_node.lchild is not None:
queue.append(cur_node.lchild)
if cur_node.rchild is not None:
queue.append(cur_node.rchild)
1.4 二叉樹的深度優(yōu)先遍歷
深度優(yōu)先遍歷即先遍歷孩子節(jié)點(diǎn)，再遍歷兄弟節(jié)點(diǎn)。這里實(shí)現(xiàn)的深度優(yōu)先遍歷是“中序遍歷”，即“左孩子——根節(jié)點(diǎn)——右孩子”。運(yùn)用遞歸的思想，只需不斷調(diào)用自身函數(shù)就能遍歷完。
# 偽代碼
# 調(diào)用時(shí)需要傳入二叉樹的根節(jié)點(diǎn)，不斷遞歸調(diào)用
def preorder_travel(self, node):
如果node為空，直接返回
打印node的元素值
preorder_travel(self, node的左孩子)
preorder_travel(self, node的右孩子)
def preorder_travel(self, node):
if node is None:
return
print(node.elem, end=' ')
self.preorder_travel(node.lchild)
self.preorder_travel(node.rchild)
2.圖
2.1 圖的實(shí)現(xiàn)
圖作為數(shù)據(jù)結(jié)構(gòu)由 “字典” 實(shí)現(xiàn)，字典的鍵為“點(diǎn)”，值為“與鍵相鄰的點(diǎn)”。
class Gragh():
def __init__(self,sequense):
'''sequense是一個(gè)集合，key是點(diǎn)，value是與key相連接的點(diǎn)'''
self.sequense = sequense
在實(shí)例化一個(gè)圖的時(shí)候，需要傳入如下所示的集合，表示 'A' 與 'B', 'C'相鄰。
sequense = {'A': ['B'],
'B': ['C', 'D'],
'C': ['E'],
'D': [],
'E': ['A']}
2.2 圖的廣度優(yōu)先遍歷
圖的遍歷需要指定一個(gè)節(jié)點(diǎn)，將圖轉(zhuǎn)化為以這個(gè)節(jié)點(diǎn)為根的樹，沿著樹的廣度進(jìn)行遍歷。
（1）頂點(diǎn)v入隊(duì)列。
（2）當(dāng)隊(duì)列非空時(shí)則繼續(xù)執(zhí)行，否則算法結(jié)束。
（3）出隊(duì)列取得隊(duì)頭頂點(diǎn)v；訪問頂點(diǎn)v并標(biāo)記頂點(diǎn)v已被訪問。
（4）查找頂點(diǎn)v的第一個(gè)鄰接頂點(diǎn)col。
（5）若v的鄰接頂點(diǎn)col未被訪問過的，則col入隊(duì)列。
（6）繼續(xù)查找頂點(diǎn)v的另一個(gè)新的鄰接頂點(diǎn)col。
（7）直到頂點(diǎn)v的所有未被訪問過的鄰接點(diǎn)處理完。
def BFS(self, source):
frontiers = [source] # 前驅(qū)節(jié)點(diǎn)
traveled = [source] # 遍歷過的節(jié)點(diǎn)
while frontiers:
nexts = []
for frontier in frontiers:
for cur in self.sequense[frontier]:
if cur not in traveled:
traveled.append(cur)
nexts.append(cur)
frontiers = nexts # 更新一層前驅(qū)節(jié)點(diǎn)
return traveled
2.3 圖的深度優(yōu)先遍歷
指定一個(gè)節(jié)點(diǎn)，將圖轉(zhuǎn)化為以這個(gè)節(jié)點(diǎn)為根的樹，沿著樹的深度進(jìn)行遍歷。
（1）訪問初始頂點(diǎn)v并標(biāo)記頂點(diǎn)v已訪問。
（2）查找頂點(diǎn)v的第一個(gè)鄰接頂點(diǎn)w。
（3）若頂點(diǎn)v的鄰接頂點(diǎn)w存在，則繼續(xù)執(zhí)行；否則回溯到v，再找v的另外一個(gè)未訪問過的鄰接點(diǎn)。
（4）若頂點(diǎn)w尚未被訪問，則訪問頂點(diǎn)w并標(biāo)記頂點(diǎn)w為已訪問。
（5）繼續(xù)查找頂點(diǎn)w的下一個(gè)鄰接頂點(diǎn)wi，如果v取值wi轉(zhuǎn)到步驟（3）。
（6）直到所有頂點(diǎn)訪問完。
def DFS(self, source):
traveled = []
stack = [source]
while stack:
cur = stack.pop()
if cur not in traveled:
traveled.append(cur)
for next_adj in self.sequense[cur]:
if next_adj not in traveled:
stack.append(next_adj)
return traveled
3.圖的最小生成樹
所有節(jié)點(diǎn)分成兩個(gè)group，一個(gè)為已經(jīng)選取的selected_node（用python中的list實(shí)現(xiàn)），一個(gè)為candidate_node。
首先任取一個(gè)節(jié)點(diǎn)加入到selected_node，然后遍歷頭節(jié)點(diǎn)在selected_node，尾節(jié)點(diǎn)在candidate_node的邊，選取符合這個(gè)條件的邊里面權(quán)重最小的邊，加入到最小生成樹，選出的邊的尾節(jié)點(diǎn)加入到selected_node，并從candidate_node刪除。直到candidate_node中沒有備選節(jié)點(diǎn)。
在這里的圖的每條邊是有權(quán)重的，所以需要實(shí)現(xiàn)一個(gè)新的圖的類，不同于 章節(jié)2 中通過點(diǎn)與點(diǎn)的臨接關(guān)系確定圖，而是用鄰接矩陣描述圖。
class Graph(object):
def __init__(self, maps):
self.maps = maps
self.nodenum = self.get_nodenum()
self.edgenum = self.get_edgenum()
def get_nodenum(self):
return len(self.maps)
def get_edgenum(self):
count = 0
for i in range(self.nodenum):
for j in range(i):
if self.maps[i][j] > 0 and self.maps[i][j] < 9999:
count += 1
return count
def prim(self):
res = []
if self.nodenum <= 0 or self.edgenum < self.nodenum-1:
return res
res = []
seleted_node = [0]
candidate_node = [i for i in range(1, self.nodenum)]
while len(candidate_node) > 0:
begin, end, minweight = 0, 0, 9999
for i in seleted_node:
for j in candidate_node:
if self.maps[i][j] < minweight:
minweight = self.maps[i][j]
begin = i
end = j
res.append([begin, end, minweight])
seleted_node.append(end)
candidate_node.remove(end)
return res
構(gòu)建一個(gè)如下圖所示的圖的實(shí)例
max_value = 9999
row0 = [0,7,max_value,max_value,max_value,5]
row1 = [7,0,9,max_value,3,max_value]
row2 = [max_value,9,0,6,max_value,max_value]
row3 = [max_value,max_value,6,0,8,10]
row4 = [max_value,3,max_value,8,0,4]
row5 = [5,max_value,max_value,10,4,0]
maps = [row0, row1, row2,row3, row4, row5]
graph = Graph(maps)
print(graph.prim())
輸出為：[[0,5,5], [5,4,4], [4,1,3], [4,3,8], [3,2,6]]
其中每一項(xiàng)前兩位為點(diǎn)，第三位為這兩個(gè)點(diǎn)連邊的權(quán)重
最小生成樹為：0——5——4——1
4——3——2
