What's the difference? g[at] seems more confusing to me as the letter "g" does not really mean anything and one has to think about what it is whereas "graph" clearly conveys what the variable is about.
great video. jutst a gotacha for future learners, the dfs findComponents algo only works well for undirected graphs and will give weird results with directed graphs. ex. in directed graphs if you take the picture 7:25 the for loop first sees node#2. however there is no path from 2 to 3 even tho they are in the same component. so instead of the answer which is 5 you get 6 Excellent video tho and thanks for the explanation
I think you confuse reachability with connectedness. Two nodes can be connected but unreachable in directed graph. In order to ensure the connected components you need to loop over each node and see if a path exists which connects all the components and there can be a scenario where nodes would be connected but you wont have a path. In order to know the graph is connected or not, it need to be undirected.
Thank you very much for such an amazing video series, the content of the video is so organized that whenever I think of some scenario that scenarios explanation comes to next. Amazing :)
You can reverse the order of calling the neighbours in this implementation, so the output will the same as You would use stack dfs algorithm - the one that uses stack instead of recursion. Because if You add neighbours to the stack the last one will be called first since it will be popped first.
It shouldn't matter. The idea is to give every component a unique id at the end of the day. However, labeling components starting at 1 instead of 0 is handy for debugging because by default the 'components' array has all values initialized to 0 so it's hard to tell whether a node was marked by the DFS method or simply initialized that way.
For the pseudo code: for next in neighbors should have an additional line below it that goes like this: if visited[next] = false In Python he did write it correctly though.
It will give 6 not 5 as the answer because in for loop we visit each node from 0 to n so when i=2 it will visit all the neighbours of 2 but not 3 because there is no outgoing edge to 3.so when i=3 it will also count it as a individual node. And hence the number of connected components would be 6 not 5. Correct me if i am wrong.
Hey are you sure DFS can be used to find the minimum spanning tree? Pretty sure that it wont give a linear time solution. Prims or Kruskals will probably be better suited for this
In the pseudo-code for DFS, the variable g is initialized to be the adjacency list representing the graph. However, in the dfs function, this variable is called "graph". Or am I missing something? Also, n is initialized to be |V| but this variable is then never actually used, other than implicitly to initialize the "visited" list of booleans.
Just to clarify this is the python code I wrote using the graph example given in video. Is it okay? g = {0:[1,9],9:[0,8],1:[0,8],8:[1,9,7],7:[8,10,3],10:[7,11],11:[7,10],6:[5,7],5:[6,3],3:[2,4,5],2:[3],4:[3]} n = 12 visited = n*[False] def dfs(at): at = at[0] if visited[at]: return visited[at] = True
neighbours = g[at] for nex in neighbours: dfs([nex]) start_node = g[0] dfs(start_node)
in the beginning you explain that after the first traversal the dfs is over but you didn't visit the #12 node, dfs beside of coloring from white to gray to black also uses a counter to mark in each node when was that node firs found and when did the algorithm leave the node, you finished the traversal on the big graph but dfs start another traversal , you should have visit 12 also and mark it as a second component of the graph meaning the number of nils in the graph is 2
The animation doesn't visit node 12 because it's trivial, but for completeness sake it should. When I said the dfs was finished I was referring to the large component.
"the nice thing about dfs is that is really easy to code". THE AMOUNT OF ITERATORS, POINTERS AND VECTORS INSIDE THE GRAPH, VERTEX AND EDGE CLASS SAY OTHERWISE!! Sometimes I really hate c++
Vertices could be computers, websites or programs. Edges then could be network connections, website links etc etc. I'm not a computer scientist but I do know that edges and vertices can be anything as long as they are connected or linked in some way in a system.
Think of edges as routes and vertices as cities. Check this awesome playlist about Graph Theory from the beginning th-cam.com/play/PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P.html
Can I ask something, I know you entered icpc, and I really want to get ready when I'm entering it, so can you tell what I need to know about number theories for competitive programming, thank you very much
4:55 It is pretty clear, but if anyone is wondering, "graph[at]" shuld be "g[at]" in the DFS pseudo-code. Great video!
Thank you, I was wondering what that was
What's the difference? g[at] seems more confusing to me as the letter "g" does not really mean anything and one has to think about what it is whereas "graph" clearly conveys what the variable is about.
@@hasnaindev the point is that the variable g is defined earlier in the video, whereas graph was not defined as a variable
@@nmamano Ooh.
it wasn't pretty clear for me, thanks
this is way better than a 2-hour lecture from a CS professor with multiple PhD's explanation. Thank God I found your video.
Guess what ? My prof literally took screenshots of SCC from this channel and used it as his ppt lol
The best explanation a developer could ever ask for. You have cut out all the possible crap and got to the point.
An explanation with the help of a good example > A CS professor with 2 PHD's explaining it in sheer theory
So basically Google's notorious "Number of islands" problem is basic graph theory == Finding connected components using DFS! Thank you William
Finding 'disconnected components' . That's the number of island
this visualization is so clear and william is so good at explaining omg, thx for saving my algo exam
You are the best in the entire youtube for Algo and DS!
I was scared of graph and you made it so easy.Thanks a lot.
Thank god for this man, the best explanation with visuals a comp sci major could ask for.
That's such a great video! I loved the minimalist visual and explanation!
great video. jutst a gotacha for future learners, the dfs findComponents algo only works well for undirected graphs and will give weird results with directed graphs.
ex. in directed graphs if you take the picture 7:25 the for loop first sees node#2. however there is no path from 2 to 3 even tho they are in the same component. so instead of the answer which is 5 you get 6
Excellent video tho and thanks for the explanation
I think you confuse reachability with connectedness. Two nodes can be connected but unreachable in directed graph. In order to ensure the connected components you need to loop over each node and see if a path exists which connects all the components and there can be a scenario where nodes would be connected but you wont have a path. In order to know the graph is connected or not, it need to be undirected.
These videos are awesome so far... will watch them through, undoubtedly multiple times!
So happy I found your channel. Thanks for your efforts and quality content. Short, to the point, and the animation done just right. :-)
Thank you very much for such an amazing video series, the content of the video is so organized that whenever I think of some scenario that scenarios explanation comes to next. Amazing :)
Waaaay better than leetcode explanation. Thanx!
You can reverse the order of calling the neighbours in this implementation, so the output will the same as You would use stack dfs algorithm - the one that uses stack instead of recursion. Because if You add neighbours to the stack the last one will be called first since it will be popped first.
I understand the visual example for DFS, but I struggle with understanding the pseudo code. However, this is a great video!
Best Explanation ever!
bought the course, thanks for all the help.
Thank you sir, your explanations are always very clean and simple
Awesome explanation. Thanks.
You made my concept crystal clear. :) Thanks
Made it easy to understand and also the listing use cases, great !!! Thanks !!!
Excellent Clarity
Great explanation!
If the graph is cyclic one then inside dfs method you also need to check if current node visited or not
i love your channel, thanks soo much for these good videos🥰
Very clear, thank you so much!
Very helpful, thank you!
Great video once again.
Amazing video!
thank god you exist
Thank you Sir
In your first example, you forgot to cover the subsequent call to DFS to explore the other component that contains exactly one node (e.g., node 12).
thank you, now to find those islands 🏝 🏝 🏝
8:52 ??
Count++ ; // should be implemented later after implementing the DFS( i) ; right ?
It shouldn't matter. The idea is to give every component a unique id at the end of the day. However, labeling components starting at 1 instead of 0 is handy for debugging because by default the 'components' array has all values initialized to 0 so it's hard to tell whether a node was marked by the DFS method or simply initialized that way.
@@WilliamFiset-videos cool , gotcha, thanks man !!
For the pseudo code:
for next in neighbors should have an additional line below it that goes like this:
if visited[next] = false
In Python he did write it correctly though.
the exclamation mark "!" means the same thing as if visited[next] = false
It will give 6 not 5 as the answer because in for loop we visit each node from 0 to n so when i=2 it will visit all the neighbours of 2 but not 3 because there is no outgoing edge to 3.so when i=3 it will also count it as a individual node.
And hence the number of connected components would be 6 not 5.
Correct me if i am wrong.
Where does the backtracking occur in the pseudo code snippet?
When you return from a recursive call
3:35 is `neighbours = graph[at]` supposed to be `neighbours = g[at]`?
Hey are you sure DFS can be used to find the minimum spanning tree? Pretty sure that it wont give a linear time solution. Prims or Kruskals will probably be better suited for this
Thank you!
very well explained )--
Great job, TY!
Excellent
That you for using that visual aid.
very helpful!
thank you!
3:30 Is this a DP implementation?
No
Can you visit all the neighbors of 7 in any direction no matter the order (preorder, inorder, postorder)? or that only applies to trees?
In the pseudo-code for DFS, the variable g is initialized to be the adjacency list representing the graph. However, in the dfs function, this variable is called "graph". Or am I missing something? Also, n is initialized to be |V| but this variable is then never actually used, other than implicitly to initialize the "visited" list of booleans.
thats not an implict use tho - its very important
Just to clarify this is the python code I wrote using the graph example given in video. Is it okay?
g = {0:[1,9],9:[0,8],1:[0,8],8:[1,9,7],7:[8,10,3],10:[7,11],11:[7,10],6:[5,7],5:[6,3],3:[2,4,5],2:[3],4:[3]}
n = 12
visited = n*[False]
def dfs(at):
at = at[0]
if visited[at]: return
visited[at] = True
neighbours = g[at]
for nex in neighbours:
dfs([nex])
start_node = g[0]
dfs(start_node)
9:24 aren't count and components global?
in the beginning you explain that after the first traversal the dfs is over but you didn't visit the #12 node, dfs beside of coloring from white to gray to black also uses a counter to mark in each node when was that node firs found and when did the algorithm leave the node, you finished the traversal on the big graph but dfs start another traversal , you should have visit 12 also and mark it as a second component of the graph meaning the number of nils in the graph is 2
The animation doesn't visit node 12 because it's trivial, but for completeness sake it should. When I said the dfs was finished I was referring to the large component.
visitad[at], obviusly everybody miss the part on how to associate the node with his corresponding visited value... probably because nobody knows
"the nice thing about dfs is that is really easy to code".
THE AMOUNT OF ITERATORS, POINTERS AND VECTORS INSIDE THE GRAPH, VERTEX AND EDGE CLASS SAY OTHERWISE!!
Sometimes I really hate c++
How to create that visual representation?
Is this Graph series helpful for competitive programming??
can someone help me how to write a complete code for this? using c language
If I wanted to find the number of paths between two nodes in a DAG, would I use a DFS or BFS? Nice video, thanks.
Probably a BFS with some DP? I haven't solved it yet but you might want to try: open.kattis.com/problems/walkforest
WilliamFiset thanks
Why is there no return value in depth first search?
You are awesome!!!
DId you slowmo your presentation?
can we use this for nba fan duel? what the sharks use
I love you man !!!!!!!!
What are edges & vertices in computer science?
Vertices could be computers, websites or programs. Edges then could be network connections, website links etc etc. I'm not a computer scientist but I do know that edges and vertices can be anything as long as they are connected or linked in some way in a system.
Think of edges as routes and vertices as cities. Check this awesome playlist about Graph Theory from the beginning th-cam.com/play/PLDV1Zeh2NRsDGO4--qE8yH72HFL1Km93P.html
This is how my brain works
No goal node???
Why zero doesn't go to node 1
Can I ask something, I know you entered icpc, and I really want to get ready when I'm entering it, so can you tell what I need to know about number theories for competitive programming, thank you very much
if you got any new or path to study for acm please tell me
Pro tip: set playback speed to 1.5
thanks a lot
cool
This is the least confused I have ever felt hearing about DFS.
3;59 [0, n) not understand
here for advent of code 2024 day 10
You kinda sound like the guy from Brackeys
104 Isidro Road
This guy sounds like Brackeys
function findComponents():
invalid syntax is coming sir
what
Dude sound like @ penguinz
even at 2x speed you talk slow, good tut
not useful. no complete example. many variables not declared. cannot understand.
dude, use less my imagination, show me, aka 3b1b
You randomly switch between saying "dep" "defp" "def" and "defth" when you are trying to say "depth" lol.
6674 Swift Via
siimiii.trii/catholicc'ica'mois'pentaocsiacal/o //nd.D
Thanks!
Great video. Thank you so much.