算法导论第二十二章习题解答

def ENQUEUE(Q, s): Q.append(s) def DEQUEUE(Q): r = Q.pop(0) return r WHITE, GRAY, BLACK = (0, 1, 2) class Vertex: def __init__(self, u): self.value = u self.color = WHITE self.d = float("inf") self.f = float("inf") self.pi = None self.num = 0 class Edge: def __init__(self, u, v): self.fromV = u self.toV = v class EdgeList: def __init__(self, v): self.vertex = v self.connectedV = [] class Graph: def __init__(self): self.vertexs = {} def CONNECT(u, v): return Edge(u, v) def INITGRAPH(G, edges): for e in edges: if not e.fromV.value in G.vertexs: G.vertexs[e.fromV.value] = EdgeList(e.fromV) if not e.toV.value in G.vertexs: G.vertexs[e.toV.value] = EdgeList(e.toV) G.vertexs[e.fromV.value].connectedV.append(e.toV) #G.vertexs[e.toV.value].connectedV.append(e.fromV) def PRINTLIST(el): print(el.vertex.value, ":") for v in el.connectedV: print(v.value) def PRINTGRAPH(G): for v in G.vertexs: PRINTLIST(G.vertexs[v]) print("-----") global time time = 0 def DFS(G, TG): for u in sorted(G.vertexs.keys()): G.vertexs[u].vertex.color = WHITE G.vertexs[u].vertex.pi = None global time time = 0 for u in sorted(G.vertexs.keys()): if G.vertexs[u].vertex.color == WHITE: DFS_VISIT(G, G.vertexs[u].vertex, TG) def DFS_VISIT(G, u, TG): global time time = time + 1 u.d = time u.color = GRAY for v in G.vertexs[u.value].connectedV: if v.color == WHITE: v.pi = u DFS_VISIT(G, v, TG) u.color = BLACK time = time + 1 u.f = time TG.append(u) #print(u.value, u.d, u.f) def TOPOLOGICAL_SORT(G): TG = [] DFS(G, TG) return TG def SIMPLE_PATH_NUM(G, s, e): TG = TOPOLOGICAL_SORT(G) s.num = 1 TG.reverse() for v in TG: if v.num > 0: for u in G.vertexs[v.value].connectedV: u.num = v.num + u.num if v == e: return e.num if __name__ == "__main__": m = Vertex('m') n = Vertex('n') o = Vertex('o') p = Vertex('p') q = Vertex('q') r = Vertex('r') s = Vertex('s') t = Vertex('t') u = Vertex('u') v = Vertex('v') w = Vertex('w') x = Vertex('x') y = Vertex('y') z = Vertex('z') edges = [] edges.append(CONNECT(m, q)) edges.append(CONNECT(m, r)) edges.append(CONNECT(m, x)) edges.append(CONNECT(n, o)) edges.append(CONNECT(n, q)) edges.append(CONNECT(n, u)) edges.append(CONNECT(o, r)) edges.append(CONNECT(o, s)) edges.append(CONNECT(o, v)) edges.append(CONNECT(p, o)) edges.append(CONNECT(p, s)) edges.append(CONNECT(p, z)) edges.append(CONNECT(q, t)) edges.append(CONNECT(r, u)) edges.append(CONNECT(r, y)) edges.append(CONNECT(s, r)) edges.append(CONNECT(u, t)) edges.append(CONNECT(v, w)) edges.append(CONNECT(v, x)) edges.append(CONNECT(w, z)) edges.append(CONNECT(y, v)) G = Graph() INITGRAPH(G, edges) PRINTGRAPH(G) print("===========") TG = TOPOLOGICAL_SORT(G) for u in TG: if u.pi != None: print(u.value, u.d, u.f, u.pi.value) else: print(u.value, u.d, u.f) print("===========") count = SIMPLE_PATH_NUM(G, p, v) print(count)