You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
37 lines
753 B
37 lines
753 B
from collections import defaultdict
|
|
|
|
class Graph:
|
|
|
|
def __init__(self):
|
|
|
|
self.graph = defaultdict(list)
|
|
|
|
def addEdge(self,u,v):
|
|
self.graph[u].append(v)
|
|
|
|
def DFSUtil(self,v,visited):
|
|
|
|
visited[v]= True
|
|
print v,
|
|
|
|
for i in self.graph[v]:
|
|
if visited[i] == False:
|
|
self.DFSUtil(i, visited)
|
|
|
|
|
|
def DFS(self,v):
|
|
|
|
visited = [False]*(len(self.graph))
|
|
|
|
self.DFSUtil(v,visited)
|
|
|
|
|
|
g = Graph()
|
|
edges = input("input the number of edges : ")
|
|
print "enter nodes with zero based indexing : "
|
|
for i in range(edges):
|
|
a, b = map(int, raw_input().split())
|
|
g.addEdge(a, b)
|
|
|
|
check = input("DFS check from node : ")
|
|
g.DFS(check)
|