Depth first search | DFS | Depth first traversal
This video explains a very important concept for graph which is depth first search also known as depth first traversal,i.e., DFS or DFT. The concept is explained for both the UNDIRECTED as well as DIRECTED graph in easiest way possible to help you grasp concepts easily. The code is explained at last after the theoretical concepts and the CODE LINK is present below. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
CODE LINK: gist.github.com/SuryaPratapK/...
Пікірлер: 82
My TECHnical knowledge is getting over DOSEd by watching your channel. Thank you Man!
@techdose4u
3 жыл бұрын
Welcome :)
I must say, it is a perfect resource to learn DFS. Keep explaining code also for each and every problem. Thanks for your efforts. Eagerly waiting to see grow your channel to 6 digit family.
@techdose4u
4 жыл бұрын
Thanks bro :)
It took me some time to implement this in C, I nearly started pulling my hair out. Without your tutorial, I would have been completely lost, such an elegant solution.
You are amazing, your channels needs a boom. Unlike other, your method of explaining is the best.
@techdose4u
4 жыл бұрын
Thanks :)
This is the simplest explanation and implementation of dfs! Great work
@techdose4u
4 жыл бұрын
Thanks
the best explanation ive ever seen,thanks man
best explanation!!! thank you
Great work brother. Respect for your efforts. Thank you so much for bringing thjs kinda content upon running.
@techdose4u
4 жыл бұрын
Welcome :)
Everyone can learn recursion and DFS from you 😄 great work brother 👏
@techdose4u
3 жыл бұрын
Thanks
At 11:29 in undirected graph what happen if we choose C vertex as starting vertex that has no path to reach other vertices ??
Awesome Work . I have seen many of your video. I am a beginner but everything is very well explained. Good work.
@techdose4u
4 жыл бұрын
Thanks
You content deserve more subscribers
@techdose4u
4 жыл бұрын
Share the video to help find some,that will be great :P How shameless of me :D
@AtulDislay
4 жыл бұрын
@@techdose4u already done😁
@techdose4u
4 жыл бұрын
@@AtulDislay Thanks bro :)
@awakashsinha9926
4 жыл бұрын
I think yeah he deserves
Please try to make more videos, Your explanation is crisp and very easy to understand.
@techdose4u
4 жыл бұрын
Thanks bro. I make videos whenever i get time from office :)
Hi..could you please help me with the explaintion of time complexity of DFS approach explained in the video
With the DFS you cannot return/read the max depth of a graph, can you?
this was excellent...can you do one dfs by iterative method too?
subscribed , you channel is gold
@techdose4u
2 жыл бұрын
Thanks 😊
what if we are at a vertex which has only incoming edges?
Really great😊
@techdose4u
3 жыл бұрын
Thanks 😃
why g[s][i] is called in dfs function as it 'll give a vertex value and not index... and if i consider it vertex value than y you passed 0 intially because maybe 0 will be not present
@aesthetic_vibes_404
4 жыл бұрын
Code wasent compiled of mine too
Is backtracking is necessary .?as we are already mking visited=1
Hi, Did I miss anything or the example is not accurate to justify the use of stack. If on backtracking we are just visiting vertex, then why keep them in stack at all? I got confused in this and I think may be the example here is not making use of stack but there could be case where stack can be used when all neighbouring vertex are not visited yet.
sweet and simple explanation..
@techdose4u
3 жыл бұрын
Thanks :)
Why we use stack here , what is the need for backtracking, we can print dfs by just visited array? Can u explain
what is Morris Transversal? There is no video available in your playlist. can you explain me a little bit.
@techdose4u
3 жыл бұрын
I will make it once start the topic :)
Thanks bro :)
@techdose4u
3 жыл бұрын
Welcome bro :)
Please also showcase the output in your videos for better understanding and visual result of the code.
@techdose4u
4 жыл бұрын
I think the code is self explanatory. In this video I dint explain it but recently I have been including code explanation in videos.
The code here is for undirected graphs?
I can see now how you are so genius , You are Itachi (11:36) 🤩😂😂😂 btw very helpful video, Thank you sir.
@techdose4u
3 жыл бұрын
😂
A follow-up question, what would be the flow if we begin from C which has no outwards edges in case of the directed graph?
@techdose4u
4 жыл бұрын
The example i explained covered all the nodes from the starting point. The graph could have been multi-component or it could have started at C as well. The answer changes according to question. If you are required to do DFS from starting point C then only 1 node will be traversed but if you are asked to visit all the nodes in a graph starting from C then you need to use a loop for all nodes and perform DFS (i think i have used the loop for traversal in code.check it once). If you don't use a loop then some nodes might get left. So, it all depends on objective of question. I think you got it now.
@khakr01
4 жыл бұрын
@@techdose4u Thank you for the explanation. Your videos are great for learning. I am happy to see your number of subscribers going up. Keep teaching. Humble request, please upload your code to Github for better access and reference. Thanks again
Thanks!
@techdose4u
2 жыл бұрын
Welcome
Does the complexity changes if we apply iterative implementation using stl stack.?
@prateekjhabak5414
3 жыл бұрын
NO if we count the stack memory. I think the only case when recursive may fail when we have n>10^6 or 10^7 something due to stack overflow,then iterative will definitely work.
it's array of vectors right?
code is not working,can you please share this code.
Bro Its very useful and informational Now I got confidence that, I can crack any DSA coding interview But. I need help in system design Do u have any reference for it
@techdose4u
3 жыл бұрын
Thanks. No
can u provide the code in java also?
where is the staack implementation
Don't you think your concept was based on stack implementation but code is based on recursion?
bro i am study in class 11 with commerce in future can i get a job in big giants company as software engineer plz give road map for me
@techdose4u
4 жыл бұрын
There are openings for commerce people as well, but they won't hire you as a software engg but only as a finance advisor, finance manager, HR, economist etc. If you wanna become a software or hardware engg then you should take science for future atleast. If you need any more advice then feel free to ask :)
@abhaytiwari6411
4 жыл бұрын
I take IT in class 11th . it can help me to get as soft engineer
@techdose4u
4 жыл бұрын
Bro you need to pursue BCA/Btech for software engg job as far as i have seen.
@abhaytiwari6411
4 жыл бұрын
thanksgiving for clearing my doubts
@randomrandom316
4 жыл бұрын
@@abhaytiwari6411 Have you taken Maths alongside Commerce? If you have then you can taken BSc IT for bachelors and then get into IT companies. Even if you haven't taken Maths but are interested in it and programming I would advise that you continue to work on your CS skills, it will surely payoff.
Time complexity of this code pls...
@techdose4u
3 жыл бұрын
This is simple solution with O(EV) if I remember correctly. You can optimize by coloring or stack to get O(E+V)
@sayantaniguha8519
2 жыл бұрын
@TECH DOSE The code using stack hasn't been taught by u
This DFS doesn't work disconnected graph .
@techdose4u
4 жыл бұрын
If you know the count of vertices then you can iterate over them to cover multiple components.
Why u write this statement while(t--)?
@sayandey4307
2 жыл бұрын
T denotes no of test cases I
Code Link : techdose.co.in/dfs/
Java code is below ============== import java.util.Iterator; import java.util.LinkedList; public class Graph { int nodes; LinkedList edges[] ; boolean visited[]; public Graph(int nodes) { this.nodes = nodes; edges = new LinkedList[nodes]; visited = new boolean[nodes]; for(int i=0;i
@techdose4u
3 жыл бұрын
👍🏼
the code you mentioned in the description is very diff from wt u explain and the fact is that you didn't show your code running . It's a SCAM!
@techdose4u
3 жыл бұрын
I think you can implement it easily :) I didn't use to show code in the past so that you learn to implement. But I have been showing code since March 2020.