Skip to content

Instantly share code, notes, and snippets.

@hold7door
Created July 8, 2018 12:16
Show Gist options
  • Save hold7door/3ea70f8a803725fa952f1a1511cf0579 to your computer and use it in GitHub Desktop.
Save hold7door/3ea70f8a803725fa952f1a1511cf0579 to your computer and use it in GitHub Desktop.
Print Level of each vertex from source
#Breadth-First-Search
#Unweighted Directed/Undirected graphs
class Node:
def __init__(self , val):
self.val = val
self.next = None
class LinkedList:
def __init__(self , head = None):
self.head = head
def insert(self , data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def display(self):
p = self.head
while p != None:
print ("{0} ".format(p.val))
p = p.next
def bfs(adj , s):
level = { s : 0}
parent = {s : None} #Recursively traversing parent of any node gives the shortest to that node from source
frontier = [s]
i = 1
while frontier:
next = []
for u in frontier:
l = adj[u].head
while l != None:
if l.val not in level:
level[l.val] = i
parent[l.val] = u
next.append(l.val)
l = l.next
i+=1
frontier = next
for i in level:
print (str(i) , str(level[i])) #Level of each node from source
if __name__ == '__main__':
adj = []
mod_v = int(input("Number of Vertices"))
for i in range(mod_v):
finish = "n"
list = LinkedList()
print ("All adjacent vertices of vertex {0}".format(i))
try:
while True:
vertex_data = int(input())
list.insert(vertex_data) #Press Ctrl-C to loop to next vertex
except KeyboardInterrupt:
pass
adj.append(list)
bfs(adj , 0)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment