代碼來自《數(shù)據(jù)結(jié)構(gòu)與算法Python語言實現(xiàn)》裘宗燕著
# 圖的生成樹
#----------圖的鄰接矩陣實現(xiàn)--------------------
class Graph:
def __init__(self,mat,unconn = 0):
# 頂點個數(shù)
vnum = len(mat)
# 檢查是否為方陣
for x in mat:
if len(x) != vnum:
raise ValueError("Argument for 'Graph'.")
# 拷貝
self._mat = [mat[i][:] for i in range(vnum)]
self._unconn = unconn
self._vnum = vnum
# 返回頂點個數(shù)
def vertex_num(self):
return self._vnum
# 驗證序號v是否有效
def _invalid(self,v):
return 0>v or v>=self._vnum
# 添加頂點
def add_vertex(self):
raise ValueError("Adj-Matrix does not support 'add_vertex'.")
# 添加邊雕欺，即添加兩個點之間的關(guān)聯(lián)線段
def add_edge(self,vi,vj,val=1):
# 先檢查vi和vj是否有效
if self._invalid(vi) or self._invalid(vj):
raise ValueError(str(vi) + 'or' + str(vj) + 'is not a valid vertex.')
# 為線段附加權(quán)重
self._mat[vi][vj] = val
# 獲取邊的權(quán)重
def get_edge(self,vi,vj):
if self._invalid(vi) or self._invalid(vj):
raise ValueError(str(vi) + 'or' + str(vj) + 'is not valid vertex.')
return self._mat[vi][vj]
# 獲取指定結(jié)點的所有相連邊
def out_edges(self,vi):
if self._invalid(vi):
raise ValueError(str(vi) + 'is not a valid vertex.')
return self._out_edges(self._mat[vi],self._unconn)
@staticmethod # 靜態(tài)方法恋沃，無需實例化即可調(diào)用
def _out_edges(row,unconn):
edges = []
for i in range(len(row)):
if row[i] != unconn:
edges.append((i,row[i]))
return edges
# 將矩陣轉(zhuǎn)化為字符串模式
def __str__(self):
return "[\n" + ".\n".join(map(str,self._mat)) + "\n]" + "\nUnconnected:" + str(self._unconn)
#----------圖的鄰接矩陣實現(xiàn)--------------------
#----------圖的壓縮鄰接矩陣實現(xiàn)-----------------
class GraphAL(Graph):
# GraphAL繼承自Graph
def __init__(self,mat = [],unconn = 0):
vnum = len(mat)
# 檢查是否為方陣
for x in mat:
if len(x) != vnum:
raise ValueError("Argument for 'Graph'.")
# 只復制帶有權(quán)重的邊
self._mat = [Graph._out_edges(mat[i],unconn) for i in range(vnum)]
self._vnum = vnum
self._unconn = unconn
# 添加一個頂點
def add_vertex(self):
self._mat.append([])
self._vnum += 1
return self._vnum - 1
# 添加一個邊
def add_edge(self,vi,vj,val=1):
if self._vnum == 0:
raise ValueError("Cannot add edge to an empty Graph!")
if self._invalid(vi) or self._invalid(vj):
raise ValueError(str(vi) + 'or' + str(vj) + 'is not valid vertex!')
row = self._mat[vi]
i = 0
while i < len(row):
# 尋找vj對應(yīng)的權(quán)重
if row[i][0] == vj:
self._mat[vi][i] = [vj,val]
return None
# 如果沒有找到vj對應(yīng)的值，說明vi和vj不相連
# 則退出循環(huán)边翁，添加vi與vj的關(guān)聯(lián)邊
if row[i][0] > vj:
break
i += 1
# 添加vi與vj的關(guān)聯(lián)邊
self._mat[vi].insert(i,(vj,val))
def get_edge(self,vi,vj):
if self._invalid(vi) or self._invalid(vj):
raise ValueError(str(vi) + 'or' + str(vj) + 'is not valid vertex!')
# 尋找對應(yīng)vi和vj的邊的權(quán)重
if i,val in self._mat[vi]:
if i == vj:
return val
# 如果沒有匹配到啼肩，則返回0
return self._unconn
#----------圖的壓縮鄰接矩陣實現(xiàn)-----------------
#----------棧的實現(xiàn)---------------------------
class Node:
def __init__(self):
self.val = val
self.next = None
class SStack:
def __init__(self):
self.top = None
# 獲取棧頂?shù)脑? def peek(self):
if self.top != None:
return self.top.val
else:
return None
# 將新元素壓入到棧中
def push(self,n):
n = Node(n)
n.next = self.top
self.top = n
return n.val
# 退出棧
def pop(self):
if self.top == None:
return None
else:
tmp = self.top.val
self.top = self.top.next
return tmp
#----------棧的實現(xiàn)---------------------------
#----------1. 非遞歸DFS遍歷--------------------
def DFS_graph(graph,v0):
# 頂點個數(shù)
vnum = graph.vertex_num()
# 為每個頂點打上未訪問的標記
visited = [0] * vnum
# 遍歷序列
DFS_seq = [v0]
# 棧橄妆、用于存儲每個頂點的邊信息
st = SStack()
st.push((0,graph.out_edges(v0))) # 壓入與起始結(jié)點相連的邊中的第一條
while not st.is_empty():
# 取出頂點序號i與邊列表
i,edges = st.pop()
if i < len(edges):
# v是頂點，e是邊
v,e = edges[i]
# 壓入與該頂點相連的下一個邊
# 待前一個邊下面的所有結(jié)點都訪問完了之后再訪問
st.push((i+1,edges))
# 如果沒有訪問過這個頂點
if not visited[v]:
# 將頂點加入列表中
DFS_seq.append(v)
# 訪問過之后將標記置為1
visited[v] = 1
# 將與搜索到的頂點相連的頂點壓入棧中祈坠，以備下次訪問害碾，這個比163行的更先訪問到
st.push((0,graph.out_edges(v)))
return DFS_seq
#----------1. 非遞歸DFS遍歷--------------------
#---------2. DFS生成樹-------------------------
def DFS_span_forest(graph):
# 頂點個數(shù)
vnum = graph.vertex_num()
# 記錄路徑信息
span_forest = [None] * vnum
def dfs(graph,v):
# 需要修改非局部變量，所以將之聲明為nonlocal
nonlocal span_forest
# 遍歷頂點v連接的所有路徑赦拘，u是頂點慌随，w是權(quán)重
for u,w in graph.out_edges(v):
# 如果這個頂點尚未加入span_forest
if span_forest[u] is None:
# 將結(jié)點u的上一結(jié)點和連接權(quán)重記錄下來
span_forest[u] = (v,w)
dfs(graph,u)
# 避免還有不連通的點，所以要遍歷到每個頂點
for v in range(vnum):
if span_forest[v] is None:
span_forest[v] = [v,0]
dfs(graph,v)
return span_forest
#---------2. DFS生成樹-------------------------
#---------3. Kruskal最小生成樹-----------------
def Kruskal(graph):
# 基本思路：設(shè)G = (V,E) 是一個網(wǎng)絡(luò)躺同，其中|V|（頂點數(shù)量）為n阁猜，則Kruskal的基本思路為：
# （1）取包含G的所有n個頂點但是沒有任何邊的孤立點子圖T = (V,{})
# T中的每個頂點自稱一個連通分量，下面將通過不斷擴充T的方式構(gòu)造G的最小生成樹蹋艺；
# （2）將邊集E按照權(quán)值遞增的順序排序剃袍，在構(gòu)造中的每一步按順序地檢查這個邊序列
# 找到最短的且兩端位于T的兩個不同的連通分量的邊e，將e加入T捎谨，這樣兩個連通分量
# 就在e的作用下連接成了一個連通分量民效；
# （3）每次操作使T減少一個連通分量憔维。不斷重復這個動作，往T中加入新邊畏邢，直到T中所有頂點
# 都包含在一個連通分量為止业扒，這個連通分量就是G的一棵最小生成樹。
# 獲取頂點個數(shù)
vnum = graph.vertex_num()
# 將各頂點的代表元初始化舒萎，代表元代表了頂點所屬的連通分量
reps = [i for i in range(vnum)]
# mst記錄最小生成樹的邊程储，edges記錄graph所有的邊
mst,edges = [],[]
# 將所有的邊加入edges
for vi in range(vnum):
for v,w in graph.out_edges(vi):
edges.append((w,vi,v))
# 按權(quán)重排列
edges.sort()
for w,vi,vj in edges:
# 如果vi和vj屬于兩個不同的連通分量
if reps[vi] != reps[vj]:
mst.append(((vi,vj),w))
# 如果有n-1條邊代表已經(jīng)構(gòu)造完成
if len(mst) == vnum - 1:
break
# 修改代表元，將所有與vj在同一連通分量的頂點歸入vi所在的連通分量中
rep,orep = reps[vi],reps[vj]
for i in range(vnum):
if reps[i] == orep:
reps[i] = rep
return mst
#---------3. Kruskal最小生成樹-----------------
