forked from HarshCasper/NeoAlgo
-
Notifications
You must be signed in to change notification settings - Fork 0
/
dfs.py
165 lines (133 loc) · 6.26 KB
/
dfs.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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
# Depth First Search Traversal in Graphs
# Graph class created
class Graph:
def __init__(self):
# graph declared to a dictionary
self.graph = {}
# visited nodes are maintained in this set
self.visited = set()
def add_vertex(self, vertex):
# vertex is added to the graph dictionary and it's adjacency list is declared
self.graph[vertex] = []
def add_edge(self, source, destination):
# directional edges are added in this function
# the edge is directional, i.e., going from source to destination
# conditional statements in case the vertex aren't present in the graph
if destination not in self.graph or source not in self.graph:
if source not in self.graph:
print(str(source)+' is not a vertex')
# 1 is returned to avoid stopping the running of the program allows the user to re-enter values
return 1
if destination not in self.graph:
print('\n'+str(destination)+' is not a vertex.')
# 1 is returned to avoid stopping the running of the program allows the user to re-enter values
return 1
# edge is added to the graph, from source to destination
self.graph[source].append(destination)
def add_edge_bidirected(self, vertex1, vertex2):
# bidirectional graph edges are added in this function
# the edge is bidirectional, i.e., the edge goes both ways
# conditional statements to check if the vertices are present
if vertex2 not in self.graph or vertex1 not in self.graph:
if vertex1 not in self.graph:
print('\n'+str(vertex1)+' is not a vertex'+'\n')
return 1 # 1 is returned to avoid stopping the running of the program allows the user to re-enter values
if destination not in self.graph:
print('\n'+str(vertex2)+' is not a vertex.'+'\n')
return 1 # 1 is returned to avoid stopping the running of the program allows the user to re-enter values
# edges are added to the adjacency list
self.graph[vertex1].append(vertex2)
self.graph[vertex2].append(vertex1)
def dfs_helper(self, start):
# function to assist in calling dfs
# also prints the final dfs traversal
# checks if the start node is in the graph
if start not in self.graph:
print('\n'+str(start)+' not in graph.'+'\n')
# 1 is returned to avoid stopping the running of the program,
# allows the user to re-enter the start vertex
return 1
# dfs implementation starts
print('\n'+'Implementing DFS...')
# the dfs traversal is appended to the list at each visit
self.traversal = []
self.dfs(start)
traversal_length = len(self.traversal)
# prints the dfs implementation neatly
for i in range(traversal_length):
if i == (traversal_length-1):
print(str(self.traversal[i]))
else:
print(str(self.traversal[i])+' -> ',end="")
def dfs(self, node):
# dfs function
if node not in self.visited: # checks if the node was already visited
self.traversal.append(node) # if the node wasn't visited, it's added to the traversal
self.visited.add(node) # the node is marked visited
for neighbour in self.graph[node]: # neighbouring vertices are explored one after the other
self.dfs(neighbour)
# Code Implementation starts here
if __name__ == "__main__":
# To Implement Depth-First Search for Bi-Directional Graphs,
# replace G.add_edge in lines 99 and 105 with G.add_edge_bidirectional
# Graph instance is created
G = Graph()
# Number of vertices in the graph is read from user input
number_of_vertices = int(input('How many vertices are in the graph? '))
# vertices are added to the graph
for v in range(number_of_vertices):
G.add_vertex(str(input("Enter Vertex: ")))
# Number of edges in the graph read from user input
number_of_edges = int(input('\n'+'How many edges are in the Graph? '))
# edges are added to the graph
for e in range(number_of_edges):
source, destination = input("Enter Source and Destination vertices separated by a space: ").split()
val = G.add_edge(source, destination)
# If the incorrecct vertex was given, the values are taken again for this iteration
# This is added to not skip over a count of the edge
while val == 1:
source, destination = input("Enter Source and Destination vertices separated by a space: ").split()
val = G.add_edge(source, destination)
# start node for the dfs traversal is taken from the user
start_node = input('\n'+"Enter the Start Node for traversal: ")
# dfs is implemented
return_value = G.dfs_helper(start_node)
# If the user entered a non-existent vertex as start node, the following is implemented
# 1 is returned if the vertex is non existent
while (return_value == 1):
start_node = input('\n'+"Enter the Start Node for traversal: ")
return_value = G.dfs_helper(start_node)
# Complexity of Depth-First Search Algorithm
# Time Complexity: O(V+E)
# V is the number of vertices and E is the number of edges
# Space Complexity: O(V)
# V is the number of vertices
# Example Test Case
# DFS Implementation for the Adjacency List Given Below
# {
# 'A': ['B','C'],
# 'B': ['D'],
# 'C': ['F'],
# 'D': ['E'],
# 'E': [],
# 'F': [],
# }
#
"""
How many vertices are in the graph? 6
Enter Vertex: A
Enter Vertex: B
Enter Vertex: C
Enter Vertex: D
Enter Vertex: E
Enter Vertex: F
How many edges are in the Graph? 5
Enter Source and Destination Vertices separated by a space: A B
Enter Source and Destination Vertices separated by a space: A C
Enter Source and Destination Vertices separated by a space: B D
Enter Source and Destination Vertices separated by a space: C F
Enter Source and Destination Vertices separated by a space: D E
Enter the Start Node for traversal: A
Implementing DFS...
A -> B -> D -> E -> C -> F
"""