3. DFS: Depth First Search Implementation in Python | Graph Data Structure

Depth First Search Implementation (DFS) in Python,
The time complexity for DFS if O(|V| + |E|), where |V|, |E| are the no of vertices and Edges in the graph respectively.
Explore a graph using DFS traversal,
Complete Algorithm of DFS including visiting and finished time tracking of vertices during DFS.
Author: Shahrukh Khan
Links
Blog: pytech-solutio...
#datastructures
#Graph Traversal
#DFS

[@ayushijain7892]

Super easy explanation

[@PyTechVision]

Thank you, Ayushi Jain

[@sheikhsafoan4537]

@@PyTechVision brother your explanation and implementation is so easy. Can you kindly make a video on djkastra, prims and krushkal algorithms please!!

[@titusyesurajj760]

This guy deserves more subs and likes.Perfect explanation ever

[@AshutoshKumar-lp5xl]

bahut tagda....!!!!!!

[@fmitesh007]

great work easy explanation

[@annepuvijay3743]

Excellent Explanation... You will live on in this video forever.... 👏

[@bouncingquarks6037]

dude your voice is asmr ! calmness is much needed while coding.

[@bouncingquarks6037]

why don't you do more videos on dsa in python.. it's much needed all other folks just do it in c++

[@shashankseethu7812]

Sir pls post video on topological sort .... U have explained this in a best way !💕

[@PyTechVision]

Sure I will

[@optimistichomosapien7484]

Great explanation..

[@PyTechVision]

Glad it was helpful!

[@hamzahamr2284]

brother I wished you have explained MinMax Algo, A*, Alpha-Beta and Bayseain because your explanation are the best.

[@ayushganvir2721]

Cool video! Keep Up the good work!! Its odd that only Indian viewers are only watching/commenting.

[@PyTechVision]

Yeah thanks

[@umeloonyejiaka1255]

@@PyTechVision nigerian here watching lol

[@uttarakhandwala8745]

Fantastic explanation

[@ghanalkaushik2058]

Really good explanation brother.
Thanks for the video.

[@kanchidoshi6907]

For stack, does it have to be directed graph example only?

[@jtommyboi]

From movie star to youtube code tutorials. Didn't know Shahrukh Khan was so diverse

[@AISHAIKSAMEERUDDIN]

Please continue making video lectures

[@powersparkmotivation]

in the case of undirected graph, when u add code to traverse each node that is not visited then why the node 'C' was traversed first (start time of c node is 0). Node 'A' should be traversed first or else i am missing something. The output should be [A,B,D E,C,F]

[@patriciaasiimire5490]

dfs_util("A")
print(dfs_traversal_output)
are giving me a type error 'dict is not callable'

[@emeemmanuel9250]

Bro nice work, why don't you upload more videos??

[@zefanyasoplantila1430]

Sir can i insert the end target node? So we can traverse just to the target? The problem is in recursion whenever i try to stop at the target node, the other node also appended to the dfsoutput can u explain plz?

[@vijaybabaria3253]

Using bfs, can I print all *possible* paths to undirected graph node from start to end?

[@ashwinib.bharmnaikar376]

Super explanation. Can i get to know the time & space complexity of this algorithm?

[@PyTechVision]

Thanks Ashwini, The time complexity for DFS if O(|V| + |E|), where |V| , |E| are the no of vertices and Edges in the graph respectively.
I will also update this in video description.

[@ashwinib.bharmnaikar376]

@@PyTechVision okay thank-you

[@ashwinib.bharmnaikar376]

@@PyTechVision though we consider 2 extra dictionaries, that won't affect space complexity right?

[@PyTechVision]

@@ashwinib.bharmnaikar376 that will add an extra constant space, overall space complexity should remain same.

[@534A53]

does this work if you start from any node? (i.e. what if there is no root or its not obvious what the root is - can you just pick a node at random to start?)

[@prashantbisht2219]

Yes, it will.

[@AISHAIKSAMEERUDDIN]

For the function dfs_util what is the need for writing time+=1 why do we increment after completion of the function? It is unnecessary i think sir can u explain plz!!?

[@PyTechVision]

In general DFS it is not needed, but for topological sorting or other application u may need it. I tried to cover all possible cases ( for details you can refer to Introduction to Algorithms by Cormen)

[@varshinisalian3214]

Super explanation......❤️

[@PyTechVision]

Thank you 🙂

[@DrIlyas-sq7pz]

Sir, How to visualize this graph as a diagram?

[@BalaguruS-zp5qf]

no one can explain this topic better than u ......

[@PyTechVision]

Thanks @4017 Balaguru

[@vinoddiwan5792]

Can you suggest some books on Python for problem-Solving?

[@ShivamSharma-cc7mc]

elements of programming interview in python

[@rebazabbas4873]

thanks for video

[@PyTechVision]

Most welcome @Rebaz Abbas

[@sachinchandela7754]

hlo sharukh sir , i try to write some code for dfs only ; is it also giving write output ; but still dont know if it pass all cases or not ; can you please check ?

[@sachinchandela7754]

#code ; here root means starting vertex
#adjacency list using set
class Graph :
def __init__(self , isdirected = False):
self.graph = {}
self.isdirected = isdirected
self.parent = {}
self.level = {}

def add_vertix(self,vertex):
self.graph[vertex] = set({})
def add_edge(self,u,v):
self.graph[u].add(v)
if self.isdirected == False :
self.graph[v].add(u)
def find_degree(self,vertex):
return len(self.graph[vertex])
def printgraph(self):
for x in self.graph :
print(str(x) + ' --> ' + str(self.graph[x]))
def bfs(self,root = None):
ans = []
if root is None :
for x in self.graph :
root = x
break
q = [root] ; self.level[root] = 0
while q :
vertex = q.pop(0)
ans.append(vertex)
for x in self.graph[vertex] :
if (x not in q) and (x not in ans):
self.parent[x] = vertex
self.level[x] = self.level[vertex] + 1
q.append(x)
return ans
def dfs(self,root = None ):
if root is None :
for x in self.graph :
root = x
break
stack = [root] ; v = root ; ans = [v]
while stack :
bool1 = True
for x in self.graph[v] :
if (x not in stack) and (x not in ans) :
bool1 = False
self.parent[x] = v
v = x
ans.append(v)
stack.append(v)
break
if bool1 :
v = stack.pop(-1)
return ans


g = Graph(True)
g.add_vertix('a') ; g.add_vertix('b') ; g.add_vertix('c') ; g.add_vertix('d') ;
g.add_vertix('e') #; g.add_vertix('b')
g.add_edge('b' , 'a') ;
g.add_edge('a' , 'e') ; g.add_edge('b' , 'c') ; g.add_edge('b' , 'e')
g.add_edge('e' , 'c') ; g.add_edge('c' , 'd') ; g.add_edge('d' , 'e')
g.printgraph()
#print(g.find_degree('d'))
#print(g.bfs())
#print(g.level)
print(g.dfs())
print(g.parent)

[@sivasankarreddy8442]

How you are compiling the code... In which software

[@shrikantbidgar8191]

he is using Jupiter notebook on anaconda software

[@PyTechVision]

jupyter.org/

[@befake5430]

what does ".append" work?? For what ".append" is used??

[@moulshreerana5760]

used to add something to a list at the end. Here, adj_list.append(whatever you wanna add to the list)

[@ShubhamPatil-bv6mk]

can we use same code
for undirected graph ?

[@PyTechVision]

Yes

[@rachanayadav9004]

Can you please upload implementation of Dijkstra algo and Floyd warshall algo also.

[@PyTechVision]

Sure Rachana, I will upload soon

[@markmariscal5397]

Great stuff!

[@PyTechVision]

Thanks Mark.

[@angelc9557]

One word.perfect.

[@PyTechVision]

Thanks

[@rohitdeepakphadke9442]

You are awesome brother!!!!!

[@PyTechVision]

You too!!

[@imrulemon4016]

plz give the code file.......I have done same to same like your code but error showing

[@laughterdose6545]

i am getting error
NameError: name 'dfs_transversal_output' is not defined

[@callm3pc]

Spell check, it's dfs_traversal_output as opposed to dfs_transversal_output

[@rejithist]

very nice!

[@PyTechVision]

Thanks Pangea

[@rajkumarm526]

Make video on how to delete node in a tree in python bro !!!

[@shashankseethu7812]

Seriously ... Just now I wanted to ask ... Please make it bro !

[@PyTechVision]

Sure, I will start Tree Data Structure soon.

[@ujjwalshrivastava6003]

Thank you so much

[@PyTechVision]

Welcome!

[@rebazabbas4873]

you can send face book for me