from linkedlist import *
UNTOUCHED = 0
FRONTIER = 1
VISITED = 2
class Vertex:
def __init__(self, label):
self.label = label
self.neighbs = set([])
self.state = UNTOUCHED
def __repr__(self):
return "{}".format(self.label)
class Graph:
def __init__(self):
# Key: Vertex to look up
# Value is the object encapsulating
# information about that vertex
self.vertices = {}
def add_vertex(self, u):
self.vertices[u] = Vertex(u)
def add_edge(self, u, v):
self.vertices[u].neighbs.add(self.vertices[v])
self.vertices[v].neighbs.add(self.vertices[u])
def explore(self, start, bfs=True):
"""
Given V vertices and E edges in the graph
Total Time Complexity is O(V + E)
Run BFS or DFS starting at the vertex "start"
DFS uses frontier like a stack (last in first out)
BFS uses frontier like a queue (first in first out)
"""
frontier = DoublyLinkedList()
frontier.add_first(self.vertices[start])
# Each vertex passes through the frontier exactly once
while len(frontier) > 0: # O(V) iterations
if bfs:
v = frontier.remove_first() #O(1)
else:
v = frontier.remove_last() #O(1)
v.state = VISITED # O(1)
print(v)
# Look at each neighbor of v
for n in v.neighbs: # 2E, or O(E) iterations over all
# iterations of the outer loop
# As many iterations as neighbors of v
# Put a neighbor on the frontier
# if it hasn't been visited yet
if n.state != FRONTIER and n.state != VISITED:
# Switch to being on frontier, and add
# to the back of the frontier
n.state = FRONTIER # O(1)
frontier.add_last(n) # O(1)
print("Frontier", frontier)
graph = Graph()
for v in range(8):
graph.add_vertex(v)
graph.add_edge(0, 1)
graph.add_edge(1, 4)
graph.add_edge(1, 2)
graph.add_edge(1, 3)
graph.add_edge(3, 4)
graph.add_edge(3, 7)
graph.add_edge(2, 5)
graph.add_edge(5, 6)
graph.explore(1, bfs=True)
1 Frontier DoublyLinkedList: 3 ==> 4 ==> 2 ==> 0 ==> 3 Frontier DoublyLinkedList: 4 ==> 2 ==> 0 ==> 7 ==> 4 Frontier DoublyLinkedList: 2 ==> 0 ==> 7 ==> 2 Frontier DoublyLinkedList: 0 ==> 7 ==> 5 ==> 0 Frontier DoublyLinkedList: 7 ==> 5 ==> 7 Frontier DoublyLinkedList: 5 ==> 5 Frontier DoublyLinkedList: 6 ==> 6 Frontier DoublyLinkedList: