DFS

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