Skip to content

Instantly share code, notes, and snippets.

@manojnaidu619
Last active February 22, 2020 05:48
Show Gist options
  • Save manojnaidu619/ffcbab8e1162b7a7a44a7d559a8d03e5 to your computer and use it in GitHub Desktop.
Save manojnaidu619/ffcbab8e1162b7a7a44a7d559a8d03e5 to your computer and use it in GitHub Desktop.
Interactive BFS on graphs in python
import queue
class Node:
def __init__(self):
self.data=None
self.neighbors=[]
class Graph:
def __init__(self):
self.root=None
self.nodes=[]
def NodeExists(self, SearchNodeData, SearchNode):
for x in self.nodes:
if x.data==SearchNodeData:
x.neighbors.append(SearchNode)
return True
return False
def getNeighborNodes(self, nodes):
nodesList = ""
for x in nodes:
nodesList += str(x.data + " ")
return nodesList
def buildGraph(self):
nodesToAdd=queue.Queue()
rootData = input("Enter root data : ")
rootNode = Node()
rootNode.data = rootData
self.root = rootNode
nodesToAdd.put(rootNode)
while not nodesToAdd.empty():
node = nodesToAdd.get()
self.nodes.append(node)
if not node.neighbors:
neighborCount = int(input("Enter no of neighbors of node {} : ".format(node.data)))
else:
nodesList = self.getNeighborNodes(node.neighbors)
neighborCount = int(input("Enter no of neighbors of node {} other than node(s) {} : ".format(node.data, nodesList)))
for _ in range(neighborCount):
neighborData = input("Enter neighbor data : ")
if not self.NodeExists(neighborData, node):
newNode = Node()
newNode.data = neighborData
newNode.neighbors.append(node)
node.neighbors.append(newNode)
nodesToAdd.put(newNode)
self.nodes.append(newNode)
def bfs(self):
root = self.root
visited,temp = [],queue.Queue()
temp.put(root)
print("BFS : ")
while not temp.empty():
node = temp.get()
visited.append(node)
print(node.data, end=" ")
for x in node.neighbors:
if x not in visited:
temp.put(x)
graph = Graph()
graph.buildGraph()
graph.bfs()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment