GeezerVison is showing github.com — Python-3/graphs/breadth_first_search.py at master · https-github-com-nzysoft/Python-3

Expand file tree

breadth_first_search.py

Copy path

More file actions

Latest commit

History

92 lines (75 loc) · 2.33 KB

breadth_first_search.py

Copy path

File metadata and controls

92 lines (75 loc) · 2.33 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

#!/usr/bin/python

""" Author: OMKAR PATHAK """

from __future__ import annotations

from queue import Queue

class Graph:

def __init__(self) -> None:

self.vertices: dict[int, list[int]] = {}

def print_graph(self) -> None:

"""

prints adjacency list representation of graaph

>>> g = Graph()

>>> g.print_graph()

>>> g.add_edge(0, 1)

>>> g.print_graph()

0 : 1

"""

for i in self.vertices:

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

def add_edge(self, from_vertex: int, to_vertex: int) -> None:

"""

adding the edge between two vertices

>>> g = Graph()

>>> g.print_graph()

>>> g.add_edge(0, 1)

>>> g.print_graph()

0 : 1

"""

if from_vertex in self.vertices:

self.vertices[from_vertex].append(to_vertex)

else:

self.vertices[from_vertex] = [to_vertex]

def bfs(self, start_vertex: int) -> set[int]:

"""

>>> g = Graph()

>>> g.add_edge(0, 1)

>>> g.add_edge(0, 2)

>>> g.add_edge(1, 2)

>>> g.add_edge(2, 0)

>>> g.add_edge(2, 3)

>>> g.add_edge(3, 3)

>>> sorted(g.bfs(2))

[0, 1, 2, 3]

"""

# initialize set for storing already visited vertices

visited = set()

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

queue: Queue = Queue()

# mark the source node as visited and enqueue it

visited.add(start_vertex)

queue.put(start_vertex)

while not queue.empty():

vertex = queue.get()

# 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.put(adjacent_vertex)

visited.add(adjacent_vertex)

return visited

if __name__ == "__main__":

from doctest import testmod

testmod(verbose=True)

g = Graph()

g.add_edge(0, 1)

g.add_edge(0, 2)

g.add_edge(1, 2)

g.add_edge(2, 0)

g.add_edge(2, 3)

g.add_edge(3, 3)

g.print_graph()

# 0 : 1 -> 2

# 1 : 2

# 2 : 0 -> 3

# 3 : 3

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