inf = float("inf") # inf的值大于任何float类型的值
class GraphError(ValueError):
pass
邻接矩阵实现
class Graph:
def __init__(self, mat, unconn=0):
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
def vertex_num(self):
return self._vnum
def _invalid(self, v):
return 0 > v or v >= self._vnum
def add_vertex(self):
raise GraphError( \
"Adj-Matrix dose not support 'add_vertex' . ")
def add_edge(self, vi, vj, val=1):
if self._invalid(vi) or self._invalid(vj):
raise GraphError(str(vi) + 'or' + str(vj) + /
" is not a valid verdex. ")
self._mat[vi][vj] = val
def get_edge(self, vi, vj):
if self._invalid(vi) or self._invalid(vj):
raise GraphError(str(vi) + 'or' + str(vj) + /
" is not a valid verdex. ")
return self._mat[vi][vj]
def out_edges(self, vi): # 获得从v出发的所有边
raise GraphError( \
"Adj-Matrix dose not support 'add_vertex' . ")
return self._out_edges(self._mat[vi], self._unconn)
@staticmethod
def _out_edges(row, unconn):
edges = []
for i in range(len(row)):
if row[i] != unconn:
edges.append((i, row[i]))
return edges
def __str__(self):
return "[\n" + ",\n".join(map(str, self._mat)) + "\n"\
+ "\nUnconnected: " + str(self._unconn)
邻接表实现
class GraphAL(Graph):
def __init__(self, mat=[], unconn=0):
vnum = len(mat)
for x in mat:
if len(x) != vnum:
raise ValueError("Argument for 'GraphAL' .")
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 GraphError("Cannot add edge to empty graph.")
if self._invalid(vi) or self._invalid(vj):
raise GraphError(str(vi) + 'or' + str(vj) + /
" is not a valid verdex. ")
row = self._mat[vi]
i = 0
while i < len(row):
if row[i][0] == vj:
self._mat[vi][i] = (vj, val)
return
if row[i][0] > vj:
break
i += 1
self._mat[vi].insert(i, (vj, val))
def get_edge(self, vi, vj):
if self._invalid(vi) or self._invalid(vj):
raise GraphError(str(vi) + 'or' + str(vj) + /
" is not a valid verdex. ")
for i, val in self._mat[vi]:
if i == vj:
return val
return self._unconn
def out_edges(self, vi):
if self._invalid(vi):
raise GraphError(str(vi) + \
" is not a valid vertex. ")
return self._mat[vi]
深度优先遍历的非递归算法
def DFS_graph(graph, v0):
vnum = graph.vertex_num()
visited = [0]*vnum
visited[v0] = 1
DFS_seq = [v0]
st = SStack()
st.push((0, graph.out_edges(v0)))
while not st.is_empty():
i, edges = st.pop()
if i < len(edges):
v, e = edges[i]
st.push((i+1, edges))
if not visited[v]:
DFS_seq.append(v)
visited[v] = 1
st.push((0, graph.out_edges(v)))
return DFS_seq
最小生成树
'''
Kruskal
T = (v, {})
while T中所含边数小于n-1
从E中选取当前最小边(u, v), 将它从E中删除
if (u, v)两端点属于T的不同连通分量：
将边(u, v)加入T
'''
def Kruskal(graph):
vnum = graph.vertex_num()
reps = [i for i in range(vnum)]
mst, edges = [], []
for vi in range(vnum): # 所有边加入edges
for v, w in graph.out_edges(vi):
edges.append((w, vi, v))
edges.sort() # 边按权值排序， O(nlogn)
for w, vi, vj in edges:
if reps[vi] != reps[vj] # 两端点属于不同连通分量
mst.append(((vi, vj), w)) # 记录边
if len(mst) == vnum - 1:
break
rep, orep = reps[vi], reps[vj]
for i in range(vnum): # 合并连通分量， 统一代表元
if reps[i] == orep:
reps[i] = rep
return mst
'''
Prim
*初始吧(0,0,0)放入优先队列，表示从顶点0到其自身的长为0的边
*循环在第一次迭代中先把顶点0记入最小生成树顶点集U,方法是设置元素
mst[0] = ((0,0),0). 然后把顶点0到其余顶点的边按权值存入优先
队列cands，表示待考察的候选边集合
*随后的循环执行中反复选择cands里记录的最短边(u, v)。 如果确定了它
是连接U中顶点与V-U顶点的边，就把这条边及其权重记入mst[v], 并
把v的出边存入cands；否则直接丢掉。
'''
def Prim(graph):
vnum = graph.vertex_num()
mst = [None]*vnum
cands = PrioQueue([(0, 0, 0)])
count = 0
while count < vnum and not cands.is_empty():
w, u, v = cands.dequeue() # 取当时的最短边
if mst[v]:
continue # 邻接点v已经在mst上，继续
mst[v] = ((u, v), w) # 记录新的MST边和顶点
count += 1
for vi, w in graph.out_edges(): # 考虑v的邻接顶点vi
if not mst[vi]:
cands.enqueue((w, v, vi))
return mst
最短路径
'''
Dijkstra算法
找图G中从顶点v0到其余顶点最短路径
初始：
1.在集合U中放入顶点v0,v0到v0的距离为0
2.对V-U里的每个顶点，如果(v0, v)属于E(即存在直接的边),则到v的已知最短路径
长度设为w(v0,v)，否则令v的已知最短路径长度为无穷大。这里的w(v0,v)是从v0到v
的边的权值
反复做：
1.从V-U中选出当时已知最短路径长度最小的顶点vmin加入U,因为这时间到vmin的已知
最短路径长度cdis(v0,vmin)就是v0到vmin的距离
2.由于vmin的加入，V-U中某些顶点的已知最短路径可能改变。如果从v0经过vmin到v`
的路径比原来已知的最短路径更短，就说明发现了到v`的新的已知最短路径(及其长度)
该路径经过vmin到v`。在这种情况下更新到v`的已知最短路径以及距离的记录，保证下
面能正确地继续从V-U中选择顶点。
反复选择顶点并更新到所有非U顶点的最短路径信息，直到从v0可达的所有顶点都在集合U中
为止。如果这时还存在未加入U的顶点，就说明被处理的图不连通(对于有向图，是存在从v0
出发不可达的顶点)
'''
def dijkstra_shortest_paths(graph, v0):
vnum = graph.vertex_num()
assert 0 <= v0 < vnum
paths = [None]*vnum
count = 0
cands = PrioQueue([(0, v0, v0)]) # 初始优先队列
while count < vnum and not cands.is_empty():
plen, u, vmin = cands.dequeue() # 取路径最短顶点
if paths[vmin]: # 如果其最短路径已知则继续
continue
paths[vmin] = (u, plen) # 记录新确定的最短路径
for v, w in graph.out_edges(vmin): # 考察经由新U顶点的路径
if not paths[v]: # 是到尚未知最短路径的顶点的路径，记录它
cands.enqueue((plen + w, vmin, v))
count += 1
return paths
拓扑排序算法
'''
1.从N中选出一个入度为0的顶点作为序列的下一个顶点
2.从N网中删除所选顶点及其所有的出边
3.反复执行上面的操作，直到已经选出了图中的所有顶点，或者再也找不到入度非0的顶点时算法结束
'''
def toposort(graph):
vnum = graph.vertex_num()
indegree. toposeq = [0]*vnum, []
zerov = -1
for vi in range(vnum): # 建立初始的入度表
for v, w in graph.out_edges(vi):
indegree[v] += 1
for vi in range(vnum): # 建立初始的0度表
if indegree[vi] == 0:
indegree[vi] = zerov
zerov = vi
for n in range(vnum):
if zerov == -1: # 不存在拓扑序列
return False
vi = zerov # 从0度表弹出顶点vi
zerov = indegree[zerov]
toposeq.append(vi) # 把一个vi加入拓扑序列
for v, w in graph.out_edges(vi):
indegree[v] -= 1
if indegree[v] == 0:
indegree[v] == zerov
zerov = v
return toposeq
