BFS

import enum
import collections

class BuildGraphic:
    def __init__(self):
        self.G = dict()
        self.G['r'] = ['s', 'v']
        self.G['s'] = ['r', 'w']
        self.G['v'] = ['r']
        self.G['w'] = ['s', 't', 'x']
        self.G['x'] = ['u', 't', 'y', 'w']
        self.G['t'] = ['u', 'w', 'x']
        self.G['u'] = ['t', 'x', 'y']
        self.G['y'] = ['x', 'u']

    def get(self):
        return self.G

class BFS:
    Color = enum.Enum('Color', 'WHITE GRAY BLACK')
    Nan = 1 << 32

    class VInfo:
        def __init__(self):
            self.color = BFS.Color.WHITE
            self.parent = None
            self.distance = BFS.Nan

        def __repr__(self):
            return '(%s, %s, %d)' % (self.color, self.parent, self.distance)

    def __init__(self, G):
        self.G = G
        self.VerToVInfo = { key : BFS.VInfo() for key in self.G }

    def __call__(self, *args, **kwargs):
        Q = collections.deque()

        for s in args:
            self.VerToVInfo[s].color = BFS.Color.GRAY
            self.VerToVInfo[s].distance = 0
            Q.append(s)
            while Q:
                u = Q.popleft()
                for v in self.G[u]:
                    if self.VerToVInfo[v].color == BFS.Color.WHITE:
                        self.VerToVInfo[v].color = BFS.Color.GRAY
                        self.VerToVInfo[v].parent = u
                        self.VerToVInfo[v].distance = self.VerToVInfo[u].distance + 1
                        Q.append(v)
                self.VerToVInfo[u].color = BFS.Color.BLACK

        return self

    def get_vinfo(self):
        return self.VerToVInfo

if __name__ == '__main__':
    G = BuildGraphic()
    print(BFS(G.get())('s').get_vinfo())

BFS算法.png
BFS code