-
Notifications
You must be signed in to change notification settings - Fork 0
/
DGraph.py
73 lines (55 loc) · 2.16 KB
/
DGraph.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
# Python program to print all paths from a source to destination.
from collections import defaultdict
# This class represents a directed graph
# using adjacency list representation
class DGraph:
def __init__(self, vertices):
# No. of vertices
self.V = vertices
# default dictionary to store graph
self.graph = defaultdict(list)
# function to add an edge to graph
def addEdge(self, u, v):
self.graph[u].append(v)
'''A recursive function to print all paths from 'u' to 'd'.
visited[] keeps track of vertices in current path.
path[] stores actual vertices and path_index is current
index in path[]'''
def printAllPathsUtil(self, u, d, visited, path):
# Mark the current node as visited and store in path
visited[u]= True
path.append(u)
# If current vertex is same as destination, then print
# current path[]
if u == d:
print(path)
else:
# If current vertex is not destination
# Recur for all the vertices adjacent to this vertex
for i in self.graph[u]:
if visited[i]== False:
self.printAllPathsUtil(i, d, visited, path)
# Remove current vertex from path[] and mark it as unvisited
path.pop()
visited[u]= False
# Prints all paths from 's' to 'd'
def printAllPaths(self, s, d):
# Mark all the vertices as not visited
visited =[False]*(self.V)
# Create an array to store paths
path = []
# Call the recursive helper function to print all paths
self.printAllPathsUtil(s, d, visited, path)
## Create a graph given in the above diagram
#g = DGraph(4)
#g.addEdge(0, 1)
#g.addEdge(0, 2)
#g.addEdge(0, 3)
#g.addEdge(2, 0)
#g.addEdge(2, 1)
#g.addEdge(1, 3)
#
#s = 2 ; d = 3
#print ("Following are all different paths from % d to % d :" %(s, d))
#g.printAllPaths(s, d)
## This code is contributed by Neelam Yadav