iframe-proxy | Sunbelt Computer Software

History

59 lines (45 loc) · 1.55 KB

Raw

#!/usr/bin/python

""" Author: OMKAR PATHAK """

class Graph:

def __init__(self):

self.vertices = {}

def printGraph(self):

"""prints adjacency list representation of graaph"""

for i in self.vertices.keys():

print(i, " : ", " -> ".join([str(j) for j in self.vertices[i]]))

def addEdge(self, fromVertex, toVertex):

"""adding the edge between two vertices"""

if fromVertex in self.vertices.keys():

self.vertices[fromVertex].append(toVertex)

else:

self.vertices[fromVertex] = [toVertex]

def BFS(self, startVertex):

# initialize set for storing already visited vertices

visited = set()

# create a first in first out queue to store all the vertices for BFS

queue = []

# mark the source node as visited and enqueue it

visited.add(startVertex)

queue.append(startVertex)

while queue:

vertex = queue.pop(0)

# loop through all adjacent vertex and enqueue it if not yet visited

for adjacent_vertex in self.vertices[vertex]:

if adjacent_vertex not in visited:

queue.append(adjacent_vertex)

visited.add(adjacent_vertex)

return visited

if __name__ == "__main__":

g = Graph()

g.addEdge(0, 1)

g.addEdge(0, 2)

g.addEdge(1, 2)

g.addEdge(2, 0)

g.addEdge(2, 3)

g.addEdge(3, 3)

g.printGraph()

# 0 : 1 -> 2

# 1 : 2

# 2 : 0 -> 3

# 3 : 3

assert sorted(g.BFS(2)) == [0, 1, 2, 3]

Sunbelt Computer Software

PL/B Language Development and Support

Navigation Menu

Sunbelt Computer Software

PL/B Language Development and Support

FilesExpand file tree

breadth_first_search.py

Latest commit

History

breadth_first_search.py

File metadata and controls