Skip to content

Instantly share code, notes, and snippets.

@Madhivarman
Created January 10, 2018 15:26
Show Gist options
  • Save Madhivarman/e748ac3b9f793871d1c010e2d1cf0ad1 to your computer and use it in GitHub Desktop.
Save Madhivarman/e748ac3b9f793871d1c010e2d1cf0ad1 to your computer and use it in GitHub Desktop.
from collections import defaultdict
class Graph():
#initial declaration
def __init__(self):
self.graph = defaultdict(list)
#add edge between two vertices
def addedge(self,src,dist):
#output of the graph look like
#defaultdict(<type 'list'>, {0: [2, 1], 1: [2], 2: [0, 3, 4], 3: [3], 4: [5], 5: [6]})
self.graph[src].append(dist)
#DFS
def DFS(self,src):
#to keep track of visited list
visited = [False]*(len(self.graph))
#create queue for DFS traversal
queue = []
#main logic starts here
queue.append(src)
visited[src] = True
while queue:
src = queue.pop(0)
print(src)
for i in self.graph[src]:
#if not visited take the connection
if visited[i] == False:
queue.append(i)
visited[i] = True
if __name__ == '__main__':
#graph
g = Graph()
print("The format of the graph look like:\n")
g.addedge(0,2)
g.addedge(0,1)
g.addedge(2,0)
g.addedge(1,2)
g.addedge(2,3)
g.addedge(3,3)
g.addedge(2,4)
g.addedge(4,5)
g.addedge(5,6)
#DFS
#graph start from 2
print("Depth First Traversal Algorithm is:\n")
g.DFS(2)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment