思考题:
from typing import Set
class Graph:
def __init__(self, value, nodes=None):
self._value = value
self._nodes: list = [] if nodes is None else nodes
@property
def value(self):
return self._value
@property
def nodes(self):
return self._nodes
def node_add(self, node):
self._nodes.append(node)
def node_adds(self, nodes):
self._nodes.extend(nodes)
def node_del(self, node):
self._nodes.remove(node)
def __str__(self):
return "Graph {} nodes {}".format(self._value, [node.value for node in self.nodes])
def __repr__(self):
return self.__str__()
def dfs(start: Graph, includes: Set[Graph] = None) -> Set[Graph]:
if includes is None:
includes = set()
if start in includes:
return includes
includes.add(start)
for s in start.nodes:
includes.update(dfs(s, includes))
return includes
if __name__ == '__main__':
A = Graph('A')
B = Graph('B')
C = Graph('C')
D = Graph('D')
E = Graph('E')
F = Graph('F')
has_nodes = {A, B, C, D, E, F}
# A->B->E
# ->C->E
# B->A
# D->F
# F->D
A.node_adds([B, C])
B.node_adds([A, E])
C.node_adds([E])
D.node_adds([F])
F.node_adds([D])
graph_nodes = dfs(A, set())
# OUT: {Graph B nodes ['A', 'E'], Graph E nodes [], Graph C nodes ['E'], Graph A nodes ['B', 'C']}
print(graph_nodes)
# OUT: {Graph F nodes ['D'], Graph D nodes ['F']}
print(has_nodes - graph_nodes)
展开