classical demonstration of breadth-first

bfs-classical

#!/usr/python
#example relationships to graph
"""
        A -> B
        A -> C
        B -> C
        B -> D
        C -> D
        D -> C
        E -> F
        F -> C
"""

#example graph
graph = {'A':['B','C'],
         'B':['C','D'],
         'C':['D'],
         'D':['C'],
         'E':['F'],
         'F':['C']
         }   

#First setup arrays to hold prcessed and discovered vertices
processed = {}
discovered = {}
parent = {}

def initialize_search(graph):
     
        for v in graph:
                processed[v]=0
                discovered[v]=0
def bfs(graph,start):
        # Vertices to visit
        queue = graph.keys()
        # Discoverer vertex
        v = 0 
        # Discovered vertex
        y = 0
        while(len(queue)>0):
                v=queue.pop()
                #process discoverer vertex function before anything happens - todo: write function
                processed[v]=1
                #now we explore the edges and find the children vertexes
                for y in graph[v]:
                        if processed[y]==0:
                                #process discovered vertex function - todo: write function
                        if discovered[y]==0:
                                discovered[y]=1
                                parent[y]=v
                #process discoverer vertex function after everything happens - todo: write function

initialize_search(graph)
bfs(graph,0)