Breadth-first-search implementation

bfs.py

RandomGraph(Graph):
    
    
    def bfs(self, v):
        """search graph by a BFS: breadth-first-search"""
        worklist = [v]
        closed = []
        while worklist: # order of growth is O(n)
            visited = worklist.pop(0) # O(n)
            closed.append(visited) #
            vs = self.out_vertices(visited) 
            vs = [v for v in vs if not (v in closed or v in worklist)] # ~O(n)
            worklist.extend(vs)
        return closed




    def better_bfs(self, v):
        """order of growth is linear: O(n)"""
        worklist = deque([v])
        closed = set()
        while worklist: # order of growth is O(n)
            visited = worklist.popleft() # O(1)
            if visited in closed:continue
            closed.add(visited)
            vs = self.out_vertices(visited)
            worklist.extend(vs)
        return closed