图

1.邻接矩阵

class GraphTable: def __init__(self, mat, unconn=0): # unconn表示选择有无权重 vnum = len(mat) for x in mat: if len(x) != vnum: #检查是否时方阵 print('No square matrix') return 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): print('it does no support this method') return def add_edge(self, vi, vj, val=1): if self._invalid(vi) or self._invalid(vj): print('it not a valid vertex') return self._mat[vi][vj] = val def get_edge(self, vi, vj): if self._invalid(vi) or self._invalid(vj): print('it not a valid vertex') return return self._mat[vi][vj] def out_edges(self, vi): #输出某顶点的所有出边 if self._invalid(vi): print('it not a valid vertex') return edges = [] temp = self._mat[vi] for i in range(len(temp)): if temp[i] != unconn: edges.append((i, temp[i])) return edges

2.邻接表

class GraphAL: def __init__(self, mat, unconn=0): vnum = len(mat) for x in mat: if len(x) != vnum: #检查是否时方阵 print('No square matrix') return self._mat = [] for j in range(len(mat)): edges = [] temp = mat[j] for i in range(len(temp)): if temp[i] != unconn: edges.append((i, temp[i])) self._mat.append(edges) 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: print('Cannot add edge to empty graph.') return if self._invalid(vi) or self._invalid(vj): print('it not a valid vertex.') return row = self._mat[vi] i = 0 while i < len(row): if row[i][0] == vj: # 修改mat[vi][vj]的值 self._mat[vi][i] = (vj,val) return if row[i][0] > vj: # 原来没有到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): print('it not a valid vertex.') return for i, val in self._mat[vi]: if i == vj: return val

3.DFS

mat1 = [ # 0,1,2,3,4四个点的矩阵表示 [0,0,1,1,0], [0,0,1,0,0], [1,1,0,1,1], [1,0,1,0,1], [0,0,1,1,0], ] print(mat1) graph = GraphAL(mat = mat1) #dfs visited = [0 for i in range(0,25)] #访问标记 def DFS(G, vi): visited[vi] = 1 print('点',vi) edges = G._mat[vi] for i in range(0,len(edges)): if(visited[edges[i][0]] == 0): DFS(G,edges[i][0]) def DFSTraverse(G): for i in range(0,G._vnum): if(visited[i] == 0): #未被访问过则深度搜索 DFS(G, i) DFSTraverse(graph) [[0, 0, 1, 1, 0], [0, 0, 1, 0, 0], [1, 1, 0, 1, 1], [1, 0, 1, 0, 1], [0, 0, 1, 1, 0]] 点 0 点 2 点 1 点 3 点 4

4.BFS

import queue mat1 = [ # 0,1,2,3,4四个点的矩阵表示 [0,0,1,1,0], [0,0,1,0,0], [1,1,0,1,1], [1,0,1,0,1], [0,0,1,1,0], ] print(mat1) graph = GraphAL(mat = mat1) #dfs visited = [0 for i in range(0,25)] #访问标记 q = queue.Queue() def BFS(G, vi): visited[vi] = 1 print('点',vi) q.put(vi) while(not q.empty()): v = q.get() edges = G._mat[v] for i in range(0,len(edges)): if(visited[edges[i][0]] == 0): visited[edges[i][0]] = 1 print('点',edges[i][0]) q.put(edges[i][0]) def BFSTraverse(G): for i in range(0,G._vnum): if(visited[i] == 0): #未被访问过则搜索 BFS(G, i) BFSTraverse(graph) [[0, 0, 1, 1, 0], [0, 0, 1, 0, 0], [1, 1, 0, 1, 1], [1, 0, 1, 0, 1], [0, 0, 1, 1, 0]] 点 0 点 2 点 3 点 1 点 4

5.最小生成树

5.1 kruskal算法

mat1 = [ # 0,1,2,3,4四个点的矩阵表示,值为权重 [0,0,2,3,0], [0,0,5,0,0], [2,5,0,1,4], [3,0,1,0,1], [0,0,4,1,0], ] print(mat1) graph = GraphAL(mat = mat1) # 按照连通分量的思想来实现的 def kruskal(G): vnum = G._vnum reps = [i for i in range(vnum)] #连通分量 mst, edges = [],[] # mst为最终结果，edges为新的边集 for vi in range(vnum): #将所有边加入edges列表 for edge in G._mat[vi]: edges.append((edge[1], vi, edge[0])) edges.sort() #按权值排序 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 mst = kruskal(graph) print(mst) [[0, 0, 2, 3, 0], [0, 0, 5, 0, 0], [2, 5, 0, 1, 4], [3, 0, 1, 0, 1], [0, 0, 4, 1, 0]] [(2, 3, 1), (3, 4, 1), (0, 2, 2), (1, 2, 5)]

5.2 Prim算法

用了一个优先队列cands记录候选边，mst的作用与前面算法相同。开始将边（0，0，0）压入队列，表示从顶点0到自身的长度为0的边，第一个元素是权值。然后执行算法的主循环，直到mst 记录了n个顶点（成功构造出最小生成树）或优先队列空（说明图graph不连通，没有最小生成树）时结束。

import queue mat1 = [ # 0,1,2,3,4四个点的矩阵表示,值为权重 [0,0,2,3,0], [0,0,5,0,0], [2,5,0,1,4], [3,0,1,0,1], [0,0,4,1,0], ] print(mat1) graph = GraphAL(mat = mat1) def prim(G): vnum = G._vnum mst = [None]*vnum cands = queue.PriorityQueue() cands.put((0, 0, 0)) count = 0 while count<vnum and not cands.empty(): w, vi, vj = cands.get() if mst[vj] != None: # 如果顶点vj以及有边了就跳过 continue mst[vj] = (vi, vj, w) count += 1 edges = G._mat[vj] #获取下一个点的所有出边，加入到conds for v, w in edges: if mst[v] == None: cands.put((w, vj, v)) #去掉一开始的[0,0,0] mst.remove((0,0,0)) return mst mst = prim(graph) print(mst) [[0, 0, 2, 3, 0], [0, 0, 5, 0, 0], [2, 5, 0, 1, 4], [3, 0, 1, 0, 1], [0, 0, 4, 1, 0]] [(2, 1, 5), (0, 2, 2), (2, 3, 1), (3, 4, 1)]

6.最短路径

6.1 Dijkstra算法

用一个vnum元的表paths记录路径，其元素paths【v】的形式为（v，p），说明从vo到顶点v的最短路径上的前一顶点是v，该最短路径的长度是p。此外，函数里还用paths【v】取值None 表示v还不在U里。
求解最短路径的候选边集以路径长度作为排序码记录在优先队列cands里，队列元素形式为（p，v，V’），表示从v0经v到v’的已知最短路径的长度为p。根据p的值在cands里排序，保证总选出最近的未知距离顶点。
 每次选出的具有最小p值的边。如果其终点v’在V-U，就将其加入 paths，并将经由v’可达的其他顶点及其路径长度记人cands。显然，如果cands已有到某顶点的路径，但后来发现的新路径更短，优先队列保证最短的路径被先行取出，满足算法的需要。

import queue mat1 = [ # 0,1,2,3,4四个点的矩阵表示,值为权重 [0,0,2,3,0], [0,0,5,0,0], [2,5,0,1,4], [3,0,1,0,1], [0,0,4,1,0], ] print(mat1) graph = GraphAL(mat = mat1) def dijkstra(G,v0): vnum = G._vnum paths = [None]*vnum count = 0 cands = queue.PriorityQueue() cands.put((0, v0, v0)) while count<vnum and not cands.empty(): p, vi, vj = cands.get() if paths[vj] != None: continue paths[vj] = (vi, p) count += 1 edges = G._mat[vj] # 获取下一个点的所有出边，加入到conds for v, w in edges: if paths[v] == None: cands.put((w, vj, v)) count+=1 return paths paths = dijkstra(graph,0) print(paths) [[0, 0, 2, 3, 0], [0, 0, 5, 0, 0], [2, 5, 0, 1, 4], [3, 0, 1, 0, 1], [0, 0, 4, 1, 0]] [(0, 0), None, (0, 2), (2, 1), None] 以上输出中None表示两点之间没有路径

6.2 Floyd算法

import queue mat1 = [ # 0,1,2,3,4四个点的矩阵表示,值为权重 [0,0,2,3,0], [0,0,5,0,0], [2,5,0,1,4], [3,0,1,0,1], [0,0,4,1,0], ] print(mat1) graph = GraphTable(mat = mat1) def floyd(G): vnum = G._vnum a = G._mat nvertex = [[-1 if a[i][j] == 0 else j for j in range(vnum)] for i in range(vnum)] #动态规划的思想，能从该数组得到路径 for k in range(vnum): for i in range(vnum): for j in range(vnum): if a[i][j] > a[i][k] + a[k][j] or (a[i][j] == 0 and a[i][k] + a[k][j] != 0) and i!=j: a[i][j] = a[i][k] + a[k][j] nvertex[i][j] = nvertex[i][k] return (a, nvertex) floyd(graph) [[0, 0, 2, 3, 0], [0, 0, 5, 0, 0], [2, 5, 0, 1, 4], [3, 0, 1, 0, 1], [0, 0, 4, 1, 0]] ([[0, 4, 2, 3, 4], [4, 0, 2, 3, 4], [2, 2, 0, 1, 2], [3, 3, 1, 0, 1], [4, 4, 2, 1, 0]], [[-1, 2, 2, 3, 2], [-1, -1, -1, -1, -1], [0, 0, -1, 3, 0], [0, 0, 2, -1, 4], [-1, -1, -1, 3, -1]])