Graph Search, why?

we can explore a graph!

Applications:

• Web Crawling
• Social Networking
• Solving Puzzles and Games        Example Code:

Queue Code:

``````class Queue:

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

def enqueue(self, item):
self.queue.append(item)
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.is_directed = is_directed

for node in self.nodes:

if not self.is_directed:

def degree(self,node):
'''Total number of edges coming out a given node'''
return deg

for node in self.nodes:

def __getitem__(self, node):

"""retrives items from out Node/vertex"""

``````

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']

``````

``````def bfs(graph, start):
# keep track of all visited nodes
visited = []
queue = Queue()
queue.enqueue(start)

# keep looping until there are nodes still to be checked
while not queue.is_empty():

node = queue.dequeue()

if node is None:
break

if node not in visited:
visited.append(node)
neighbours = graph[node]

for neighbour in neighbours:
queue.enqueue(neighbour)
return visited

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

``````

Output:

``````