definsert_vertex(self, x=None): """插入点, 返回点 Vertex 类""" v = self.Vertex(x) # 创建新点, 值为 x self._outgoing[v] = {} # 放入点集, 此时无边, 故为空
ifself.is_directed(): self._incoming[v] = {} # 如果有方向, 则入射点集也要加入 return v
definsert_edge(self, u, v, x=None): """插入边, 注意, 需要 u v 均为点 Vertex 类""" e = self.Edge(u, v, x) # 从 u 到 v, 值为 x self._outgoing[u][v] = e # 将边放入二级结构 I(u) self._incoming[v][u] = e # 将边放入二级结构 I(v) return e
print(f"Graph is directed or not: {g.is_directed()}")
print("=" * 15, "All Vertices", "=" * 15) for v in g.vertices(): print(f"Vertex: {v.element()}")
print("=" * 15, "All Edges", "=" * 15) for e in g.edges(): print(f"Edge: {e.element()}")
1 2 3 4 5 6 7 8 9 10 11 12 13
Graph is directed ornot: False =============== All Vertices =============== Vertex: 1 Vertex: 2 Vertex: 3 Vertex: 4 =============== All Edges =============== Edge: f Edge: b Edge: d Edge: c Edge: a Edge: e
2 图的遍历
图的遍历可以解决很多关于图的可达性的问题：
找到任意两个顶点间的路径（或验证两个顶点间无路径）
找到从图的一个特定顶点出发可以到达的所有顶点及相应的路径
测试图是否是连通的
找到图的所有连通分支
判断图是否为强连通的
我们常常使用如下两种算法进行图的遍历：
深度优先搜索
广度优先搜索
2.1 深度优先搜索 DFS
深度优先搜索（DFS）是一种常用的图遍历算法，可实现以下功能：
访问图 G 的所有顶点和边
判断图 G 是否是连通的
找到图 G 的所有连通分支
对图 G 的所有连通分支，计算其生成树
DFS 还可被用来解决其他问题，如：
找到两个顶点间的一条路径
找到图中的环
2.1.1 深度优先搜索算法
图的 DFS 算法使用一种记录并查询顶点和边的“标签”的方式来判断顶点和边是否被访问过，下面以无向图为例给出 DFS 算法。此算法将所有边分为 discovery 和 back 两类。
【伪代码】从图 G 的某一个顶点 v 开始深度优先搜索：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
Algorithm DFS(G, v) [Input]: graph G and a start vertex v of G [Output]: labeling of the edges of G in the connected component of v as discovery edges and back edges [Algorithm]: setLabel(v, VISITED) # v 已被访问过
forall e = G.incidentEdges(v) # v 的所有邻边 e if getLabel(e) = UNEXPLORED # 若边 e 未被访问 w = opposite(v,e) # 找到边 e 的非 v 的顶点 w if getLabel(w) = UNEXPLORED # 若点 w 未被访问 setLabel(e, DISCOVERY) # 标记边 e 为 discovery DFS(G, w) # 从点 w 继续递归探索 else setLabel(e, BACK) # 否则, 点 w 被访问过, 则标记边 e 为 back
【伪代码】图 G 每一个点都进行 DFS：
1 2 3 4 5 6 7 8 9 10 11 12 13
Algorithm DFS(G) [Input]: graph G [Output]: labeling of the edges of G as discovery edges and back edges [Algorithm]: forall u = G.vertices() setLabel(u, UNEXPLORED) # 图 G 的所有点初始化为未访问
forall e = G.edges() # 图 G 的所有边初始化为未访问 setLabel(e, UNEXPLORED) forall v = G.vertices() # 使用上面定义的 DFS(G, v) 对每个点 DFS if getLabel(v) = UNEXPLORED DFS(G, v)
defDFS(g: Graph, u: Graph.Vertex, discovered: dict) -> None: """ 图 g 中任意顶点 u 的深度优先搜索 :param g: 图 Graph 类 :param u: 顶点 Graph.Vertex 类 :param discovered: 字典, 存储探索结果 :return: None """ for e in g.incident_edges(u): # 经过顶点 u 的所有边 e v = e.opposite(u) # 获取 e 非 u 的顶点 v if v notin discovered: # 顶点 v 未被访问 discovered[v] = e # 标记边 e 为 discovery; 同时标记点 v 访问过 DFS(g, v, discovered) # 从 v 继续递归探索
Algorithm pathDFS(G, v, z) [Algorithm]: setLabel(v, VISITED) # 起始点 v 标记为已经访问 S.push(v) # 压入栈底 if v = z # 找到, 则将栈元素全部返回 return S.elements() forall e = G.incidentEdges(v) # 点 v 的所有边 e if getLabel(e) = UNEXPLORED # 若边 e 未访问 w = opposite(v,e) # 找到边 e 另一个端点 w if getLabel(w) = UNEXPLORED # 若点 w 未访问 setLabel(e, DISCOVERY) # 标记 e 为 discovery S.push(e) # 并压入栈, 作为路径的一部分 pathDFS(G, w, z) # 从 w 点继续递归探索 S.pop(e) # 从边 e 探索未找到, 则出栈 else setLabel(e, BACK) # 若点 w 被访问, 标记 e 为 back S.pop(v) # 所有点 v 的邻点都失败，则将点 v 出栈
if v in discovered: # 开始从终点 v 向前探索, 回到 u path.append(v.element()) walk = v while walk isnot u: e = discovered[walk] # 获取到点 walk 的边 e = (?, walk) parent = e.opposite(walk) # 获取路径上 walk 的上一个点 ? path.append(parent.element()) # 加入路径 walk = parent # 继续向前
forall e = G.incidentEdges(v) # 点 v 的所有边 e if getLabel(e) = UNEXPLORED # 若边 e 未访问 w = opposite(v,e) # 找到边 e 另一个端点 w S.push(e) # 边 e 压入栈 if getLabel(w) = UNEXPLORED # 若点 w 未访问 setLabel(e, DISCOVERY) # 标记 e 为 discovery pathDFS(G, w, z) # 从 w 点找到到达 z 的路径 (实现见上面代码)
S.pop(e) # 从边 e 探索未找到, 则出栈 else T = new empty stack # 新栈: 存储环的路径 repeat # 不断从栈 S 中获取点和边 o = S.pop() T.push(o) until o = w # 回到了点 w 形成了环 return T.elements() # 于是返回环所有元素 S.pop(v) # 没有环, 则将 v 出栈
Algorithm BFS(G, s) [Algorithm]: L{0} = new empty sequence L{0}.addLast(s) # 第一层 setLabel(s, VISITED) i = 0 whilenot L{i}.isEmpty() L{i+1} = new empty sequence forall v = L{i}.elements() # 遍历 L{i} 的点 v forall e = G.incidentEdges(v) # 取点 v 的所有邻边 e if getLabel(e) = UNEXPLORED # 若 e 未标记 w = opposite(v, e) # 取边 e 的另一个端点 w if getLabel(w) = UNEXPLORED # 若点 w 未访问 setLabel(e, DISCOVERY) # 标记边 e 为 discovery setLabel(w, VISITED) # 标记点 w 已访问 L{i+1}.addLast(w) # 并将 w 放入该层 L{i+1} else setLabel(e, CROSS) # 若点 w 已访问, 则标记边 e 为 cross i = i +1# 探索下一层
【伪代码】图 G 每一个点都进行 BFS：
1 2 3 4 5 6 7 8 9 10 11 12
Algorithm BFS(G) [Input]: graph G [Output]: labeling of the edges of G [Algorithm]: forall u = G.vertices() # 标记所有点未访问 setLabel(u, UNEXPLORED) forall e = G.edges() # 标记所有边未访问 setLabel(e, UNEXPLORED)
forall v = G.vertices() # 取所有点 v if getLabel(v) = UNEXPLORED # 若 v 未访问 BFS(G, v) # 进行 BFS
whilelen(level) > 0: next_level = [] # 下一层的顶点集 for u in level: # 遍历本层所有点 for e in g.incident_edges(u): # 对 u 遍历所有边 e v = e.opposite(u) # 找到边 e 的另一个端点 v if v notin discovered: # 若 v 未标记 discovered[v] = e # 则标记边 e next_level.append(v) # 且存储点 v
if __name__ == '__main__': g = Graph(directed=False) A = g.insert_vertex("A") B = g.insert_vertex("B") C = g.insert_vertex("C") D = g.insert_vertex("D") E = g.insert_vertex("E") F = g.insert_vertex("F")
AB = g.insert_edge(A, B, "(A, B)") AC = g.insert_edge(A, C, "(A, C)") AD = g.insert_edge(A, D, "(A, D)")
BC = g.insert_edge(B, C, "(B, C)") CD = g.insert_edge(C, D, "(C, D)")
BE = g.insert_edge(B, E, "(B, E)") CE = g.insert_edge(C, E, "(C, E)")
