Skip to content

Instantly share code, notes, and snippets.

@spolezhaev
Last active September 6, 2018 19:14
Show Gist options
  • Save spolezhaev/90034947e429ee5811940a00243bafb1 to your computer and use it in GitHub Desktop.
Save spolezhaev/90034947e429ee5811940a00243bafb1 to your computer and use it in GitHub Desktop.
Python implementation of dfs and bfs
from collections import defaultdict
class Graph:
def __init__(self):
self.graph = defaultdict(list)
def addEdge(self,u,v):
self.graph[u].append(v)
def RecurDFS(self,v,visited):
visited[v]= True
#showing visited vertex
print(v + ' ')
for i in self.graph[v]:
if visited[i] == False:
self.RecurDFS(i, visited)
def DFS(self,v):
visited = [False]*(len(self.graph))
self.RecurDFS(v,visited)
#Creating a graph
randomGraph = Graph()
randomGraph.addEdge(0, 3)
randomGraph.addEdge(2, 0)
randomGraph.addEdge(3, 1)
randomGraph.DFS(2)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment