[go: up one dir, main page]
Scribd
Upload
9 views2 pages

A1 Py

The document presents a Python implementation of a graph class that supports both Depth First Search (DFS) and Breadth First Search (BFS) algorithms for traversing an undirected graph. It includes methods for adding edges and searching for vertices recursively using DFS and iteratively using BFS. The main section demonstrates the functionality by creating a graph and performing both search algorithms from a specified starting vertex to a destination vertex.

Uploaded by

Aishwarya Salunke
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
9 views2 pages

A1 Py

The document presents a Python implementation of a graph class that supports both Depth First Search (DFS) and Breadth First Search (BFS) algorithms for traversing an undirected graph. It includes methods for adding edges and searching for vertices recursively using DFS and iteratively using BFS. The main section demonstrates the functionality by creating a graph and performing both search algorithms from a specified starting vertex to a destination vertex.

Uploaded by

Aishwarya Salunke
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as TXT, PDF, TXT or read online on Scribd
You are on page 1/ 2

implement DES and BFS algorithm use and undirected graph and develop a recursive

algorithm for
searching all the vertices of the graph or tree data structure.

from collections import defaultdict, deque

class Graph:
directed = True

def __init__(self):
self.graph = defaultdict(list)

def addEdge(self, u, v):


self.graph[u].append(v)

if not self.directed:
self.graph[v].append(u)

def DFS(self, v, d, visitSet = None) -> bool:


visited = visitSet or set()
visited.add(v)
print(v,end=" ")

if v == d:
return True

for neighbour in self.graph[v]:


if neighbour not in visited:
if self.DFS(neighbour, d, visited):
return True

return False

def BFS(self, s, d):


visited = defaultdict(bool)
queue = deque([s])
visited[s] = True

while queue:
s = queue.popleft()
print (s, end = " ")
if s == d:
return
for i in self.graph[s]:
if visited[i] == False:
queue.append(i)
visited[i] = True

# A1.png

if __name__ == '__main__':
g = Graph()

g.addEdge('H', 'A')
g.addEdge('A', 'D')
g.addEdge('A', 'B')
g.addEdge('B', 'F')
g.addEdge('B', 'C')
g.addEdge('C', 'E')
g.addEdge('C', 'G')
g.addEdge('C', 'H')
g.addEdge('G', 'H')
g.addEdge('G', 'E')
g.addEdge('E', 'F')
g.addEdge('E', 'B')
g.addEdge('F', 'A')
g.addEdge('D', 'F')

print("Following is Depth First Traversal H -> E:")


g.DFS('H', 'E')

print ("\n\nFollowing is Breadth First Traversal H -> E:")


g.BFS('H', 'E')

You might also like