Skip to content

Instantly share code, notes, and snippets.

@spolezhaev
Created September 6, 2018 19:15
Show Gist options
  • Save spolezhaev/59d3c69860a0827fee038e1dc4fa9b55 to your computer and use it in GitHub Desktop.
Save spolezhaev/59d3c69860a0827fee038e1dc4fa9b55 to your computer and use it in GitHub Desktop.
BFS Python implemetation
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def addEdge(self,u,v):
self.graph[u].append(v)
def BFS(self, s):
queue = []
visited = [False] * (len(self.graph))
# Enqueue start node
queue.append(s)
visited[s] = True
while queue:
s = queue.pop(0)
print(s, end = " ")
for i in self.graph[s]:
if visited[i] == False:
queue.append(i)
visited[i] = True
#Creating a graph
randomGraph = Graph()
randomGraph.addEdge(0, 3)
randomGraph.addEdge(2, 0)
randomGraph.addEdge(3, 1)
randomGraph.BFS(2)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment