图的广度优先搜索 （参考算法导论）

#__author__=lx
#__date__=2011-10-03
#__brief__=BFS

from collections import deque

def BFS( G, s ):
        d = []
        color = []
        p = []
        L = deque()

        for i in range( len( G ) ):
                if i != s:
                        color.append( 'white' )
                        d.append( 'helloworld' )
                        p.append( None )
                else:
                        color.append( 'gray' )
                        d.append( 0 )
                        p.append( None )

        L.append( s )

        while ( len( L ) != 0 ):
                u = L.popleft()
                
                for v in G[u]:
                        if cmp( color[v-1],'white' ) == 0:
                                color[v-1] = 'gray'
                                d[v-1] = d[u] + 1
                                p[v-1] = u
                                L.append(v-1)
                color[u] = 'black'
                print u + 1

if __name__ == "__main__":
        l1 = [ 2, 3 ]
        l2 = [ 4, 5, 1 ]
        l3 = [ 6, 7, 1 ]
        l4 = [ 2, 8 ]
        l5 = [ 2, 8 ]
        l6 = [ 3, 7 ]
        l7 = [ 3, 6 ]
        l8 = [ 4, 5 ]

        l = [ l1, l2, l3, l4, l5, l6, l7, l8 ]

        BFS( l, 1 )