import enum
import collections
class BuildGraphic:
def __init__(self):
self.G = dict()
self.G['u'] = ['v', 'x']
self.G['x'] = ['v']
self.G['v'] = ['y']
self.G['y'] = ['x']
self.G['w'] = ['y', 'z']
self.G['z'] = ['z']
def get(self):
return self.G
class DFS:
Color = enum.Enum('Color', 'WHITE GRAY BLACK')
class VInfo:
def __init__(self):
self.color = DFS.Color.WHITE
self.parent = None
self.d = int()
self.f = int()
def __repr__(self):
return '(%s, %s, %d, %d)' % (self.color, self.parent, self.d, self.f)
def __init__(self, G):
self.G = G
self.time = 0
self.VerToVInfo = { key : DFS.VInfo() for key in self.G }
def __call__(self, *args, **kwargs):
for s in self.G:
self.visit(s)
return self
def visit(self, u):
if self.VerToVInfo[u].color != DFS.Color.WHITE:
return
self.VerToVInfo[u].color = DFS.Color.GRAY
self.time += 1
self.VerToVInfo[u].d = self.time
for v in self.G[u]:
self.VerToVInfo[v].parent = u
self.visit(v)
self.time += 1
self.VerToVInfo[u].f = self.time
self.VerToVInfo[u].color = DFS.Color.BLACK
def get_vinfo(self):
return self.VerToVInfo
if __name__ == '__main__':
G = BuildGraphic()
print(DFS(G.get())().get_vinfo())
DFS 算法.png
DFS code.png
