Breadth First Search

Graph Search, why?

we can explore a graph!


  • Web Crawling
  • Social Networking
  • Solving Puzzles and Games

inserting an Image inserting an Image inserting an Image inserting an Image inserting an Image inserting an Image inserting an Image inserting an Image

Example Code:

Queue Code:

class Queue:

    def __init__(self):
        self.queue = []
        self.size = 0;

    def enqueue(self, item):
        """Add to Queue"""
        self.size += 1

    def dequeue(self):
        """pop/remove from Queue"""
        if len(self.queue) < 1:
            return None
        return self.queue.pop(0)
        self.size -= 1
    def is_empty(self):
        "Return True if the queue is empty"
        return self.size == 0

Graph Code:

class Graph:
    def __init__(self, Nodes, is_directed = False):
        self.nodes = Nodes
        self.adj_list = {}
        self.is_directed = is_directed
        for node in self.nodes:
            self.adj_list[node] = []
    def add_edge(self, u, v):
        if not self.is_directed:
    def degree(self,node):
        '''Total number of edges coming out a given node'''
        deg = len(self.adj_list[node])
        return deg
    def print_adj_list(self):
        for node in self.nodes:
            print(node, "->", self.adj_list[node])
    def __getitem__(self, node):
        """retrives items from out Node/vertex"""
        return  self.adj_list[node]

Lets created a Graph instance and the Vertex/Nodes and Edges

all_edges = [ 
    ("A","B"), ("A","E"), ("B","E"), ("E","D"), ("B","D"), ("A","C"), ("C","F"), ("C","G")
nodes = ["A","B","C","D","E", "F", "G"]

graph1 = Graph(nodes)

for u,v in all_edges:


Here is out Graph:

A -> ['B', 'E', 'C']
B -> ['A', 'E', 'D']
C -> ['A', 'F', 'G']
D -> ['E', 'B']
E -> ['A', 'B', 'D']
F -> ['C']
G -> ['C']

Breadth-First Search

def bfs(graph, start):
    # keep track of all visited nodes
    visited = []
    queue = Queue()
    # keep looping until there are nodes still to be checked
    while not queue.is_empty():
        node = queue.dequeue()
        if node is None:
        if node not in visited:
            neighbours = graph[node]
            for neighbour in neighbours:
    return visited

print("Breadth First Search, Nodes visited: ")
print(bfs(graph1,'A') )


Breadth First Search, Nodes visited: 
['A', 'B', 'E', 'C', 'D', 'F', 'G']