5.2 Articulation Point and Biconnected Components
ฝัง
- เผยแพร่เมื่อ 23 ก.พ. 2018
- Articulation point is a vertex in a graph, if it is removed, graph will split into components.
PATREON : www.patreon.com/bePatron?u=20...
Courses on Udemy
================
Java Programming
www.udemy.com/course/java-se-...
Data Structures using C and C++
www.udemy.com/course/datastru...
C++ Programming
www.udemy.com/course/cpp-deep...
Even my grandma would understand this topic with your explanation
lmao sir yea his explanation is so clear
By seeing your dp, you may have the age around 25, therefore your grandma age may be around 60-70. So, the people who is having age around this range can't know English, therefore how can you say that your grandma can understand this without knowing English? Don't try to impress or show off here.....
@@vinayak12746 By seeing your long message we can say that you have wasted time by typing comment, therefore Don't try to waste your time again ok?....
@@saikarthik559 😂 I do fast typing, is there any problem for you???
@@vinayak12746 that'll better help you in competitive programming... not commenting vague here. ☮
One of the reasons why i feel youtube is a boon is that it gets us to amazing teachers like you, which otherwise will be rare. I am in my 30s but students in this generations are really blessed. Hope they make use of it.
Wow, this was really clear -- I'd gone through 4 different explanations prior to watching this video, and this is the first time I actually understand what was going on! Great job!!
Thank you so much! I spent way too long trying to solve this problem for my class and to no avail, but when I watched this video I found the solution right away! Thank you!
Hats off to you ...
Really great explanation.
Appreciate your hardwork.
You and Ravindra Ravula sir are shaping many computer Engineers in our country 🇮🇳.
thanks for making the Video Sir, it was difficult for me to grasp this Algo at first,
I watched ur explanation twice to get a better understanding.
keep on posting such videos.
Dear Abdul Bari Sir
Please KEEP UPLOADING more lectures to be honestly your videos make more sense and are very simple please keep up the good work.
:)
When an eight minute TH-cam video is better than a whole lecture on the subject.
Finally a great explanation, not those freaking recursive formulas
best explanation, algorithms are really hard but with your explanation who will not understand, thank you
But why this algorithm works? I mean why there is an articulation point when L(v)>=d[u]? Any explanation for this is highly appreciated?🙏
cp-algorithms.com/graph/cutpoints.html
I'm still trying to understand it, but I understand it as this: We root the graph arbitrarily, creating a tree-like structure (i think it's called a dfs-tree), then notice 2 observations:
A node is an articulation point if: it's the root and has more than 1 child OR
A node is not the root and none of it's children have a back edge to the node's ancestors (aka. there's no cycles that lead back)
To efficiently check if a node meets the second observation, we use the L and d arrays. Instead of thinking of L as low, think of it as the earliest time we visited a node. If the earliest time we visited a child (aka. L[v]) is less than the time we visited our current node (d[u]) then that means in our dfs, we visited v from an ancestor, which means v has a back-edge to an ancestor.
More formally: iff L[v] < d[u], u is not an articulation point. Therefore, if L[v] >= d[u], u is an articulation point.
Hope that helped!
@@raywang999 Great effort! It's Crystal clear now! Since we have an back edge means that the "Earliest time of child (aka L[v]) is already visited from ancestor, so will not become articulation point" ! Thank You! 🙌🙌
@@raywang999 where you understood it so deep any source?
@@raywang999 Thank you SO much!!!
Thank u so much sir ,Your videos in algorithms is very helpful to me and it also arouses an interest.Finally ur way of teaching is mesmerising!!
Sir thank u so much for this video ......I searched at many places .....but u r crystal clear and at the point.....
Simple ,clean ,neat .
Thanks a lot 😊 sir ...
Sir, what do we do if we have to find cut vertices/articulation points bw a unique source and a unique sink in a DAG (Directed Acyclic Graph)?
Here, once we have found the articulation point. How do we know from which vertex to vertex do we have to draw an edge so that it is bi-connected? Thanks once again.
Excellent explanation, props to you, sir!
Awesome! Thank you, Sir! :)
Thank you very much, sir, your explanation about all the topics is very simple and understandable.
really appreciate your efforts to explain things so lucidly!
I didnot understand the lower dfs number was derived. what path is being taken. How are those determined as back edge. I can go from 5 -> 6 -> 3 -> 2 -> 1. Why are we determining 3 is lower dfs number?
I was soo confused about this topic but your explanation is amazing Sir. Thanks a lot
Really good explanation, thank you.
Best explanation possible for this algorithm
Thank You So Much for this wonderful video........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Wow, great explanation, really helpful! thank you!
Classic explanation, hats off to you
Great! Really helpful! Thank you very much!
Dear Abdul Bari, thanks to you I like the algorithms! Thanks so much!
This is a very good explanation, thank you.
How has the formula been derived?
Tarjan's Algorithm
A very clear explanation sir.
thanks a lot.
Thank you! That was super helpful
is the lowest number the lowest vertex value or the lowest discovery time?
abdul bhai ki jai ho. shukriya bhai......(x100)
Sir what happens if the graph has only one back edge ?
will the values of L of those corresponding vertices be 0 ?
Can you please clarify how one algorithmically finds the "first backedge"? Based on what you show, where the root vertex resolves to the backedge from vertex 2, it seems like it must be level-synchronized BFS, where we compare all backedges in a given level and resolve to the highest reaching backedge. Is that what you would envision?
One other thing I've noticed while implementing this is that there might be parts of the spanning tree that don't encounter any backedges when traversing downwards(e.g. 5 if we were to delete the backedge from 6). It seems that we could remove 6 without problem, but removing 5 would make 6 it's own graph. I think the way to get around that is to label vertices at having an L of MAX_INT to make sure the formula finds those as well, but ignore vertices iwth MAX_INT that are also leat nodes on the spanning tree.
Thanks man, thanks alot
May GOD protect u and guide u❤️❤️❤️❤️❤️❤️
Ur unbelievable sir!!
Thanks again... ❤️❤️❤️🌹🌹🌹🌹🌹🌹🌹🌹🌹
Keep it going... Your explanation is awesome
🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌THE GOD MR ABDUL BARI 🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌🙌
in finding the least path L can we assume the path as 5->3->2->1 as it is a undirected graph?
Find lest path in spanning tree
you can't do that, d[3]
Really good lecture for free, thank you sir.
how this algorithm will work for undirected linear graph (i.e. no cycle) ?
In that graph all of the vertices are articulation points exept the ones at the bottom of the dfs tree
Here there are no directed edges so why lowest for 6 is 3 ,we can still go from 3 to 1 ?
Sir, what if we take an array of size equal to that the number of vertices and insert the total number of incident edges per vertex( like we can calculate the indegree and outdegree of a directed graph), then input the adjacent matrix of the corresponding graph, the vertex having highest number of incident edges will be the articulation point in most cases! Sir, I don't have much knowledge regarding that, just asking can we do that?
Sir what if back edge is not present for last number in spanning tree?what is lowest discovery number
Instead of L[v] >= d[u] , i wrote L[v]>=L[u]
It passes most of the test cases but obviously some are failing. I am not able to draw any graph for which L[v]>=L[u] produces incorrect result. Can anybody help?
Thank you! Also, I have found something related to the last statement: when is node/point 1 an articulation point (8:05). Maybe it helps somebody.
First time this was confusing for me because I thought that if node 1 has more than 1 neighbor then 1 is an articulation point, but that is not true. For instance, if node 1 belongs to a cycle, then he has more than 1 neighbor, therefore he is not an articulation point.
However, I found that 1 is an articulation point if he belongs to more than 1 biconex components. That is how I check if 1 is or not an articulation point.
sir ,at 3:33 why 2 is visited at 6th? why not at 2nd?generally in for loop ,we start from 1 to n,so 2 will come first,right?
Teacher ho toh Abdul sir jesa vrna na ho :)
What would be the time complexity of this approach? Is it O(V*E)?
The time complexity is the same as DFS which is O(V + E) according to: www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/
This explanation is 🔥..by the way that formula is derived from tarjan algorithm right?....
Thank you sir, very clear explanation🥰🥰
How does this work for 3 as the parent and 2 as the child? I mean the formula L[v] >= d[u] where u = 3 and v = 2. L[2] = 1 and d[3] = 3 thus this shows 3 is not an articulation point
---------------------------------------Credits: Ray Wang-------------------------------------------------------
cp-algorithms.com/graph/cutpoints.html
I'm still trying to understand it, but I understand it as this: We root the graph arbitrarily, creating a tree-like structure (i think it's called a dfs-tree), then notice 2 observations:
A node is an articulation point if: it's the root and has more than 1 child OR
A node is not the root and none of it's children have a back edge to the node's ancestors (aka. there's no cycles that lead back)
To efficiently check if a node meets the second observation, we use the L and d arrays. Instead of thinking of L as low, think of it as the earliest time we visited a node. If the earliest time we visited a child (aka. L[v]) is less than the time we visited our current node (d[u]) then that means in our dfs, we visited v from an ancestor, which means v has a back-edge to an ancestor.
More formally: iff L[v] < d[u], u is not an articulation point. Therefore, if L[v] >= d[u], u is an articulation point.
Hope that helped!
For 5 and 6
Why cant we go from 3 to 2 and then 1
Like 5->6->3->2->1
Exam today, this saved me
and for a non bicconected graph?
Sir , best explanation
very clear explanation, thank you so much!!
soothu
Tnq Soo much sir for u r valuable explanation.
Beautifully explained
Semma sir.continue
what a concise explanation
low [6] can be 1 also, why is it 3? we can go 1 via 3, right? I know it should be 3 but why? what's the definition
By seeing your demonstration style i just want to buy your complete course.
Is there any coupon available please .
Vishal there no other course on algorithms
Wow, simply amazing !!
Finally I get it, thanks man.
Awesome explaination sir
The back edges how are they used and how to connect them to find L. For one of the question there were only 2 back edges and thus i got L value 1 for all vertices. I didn't understand about L.
@@abdul_bari sir suppose if the node is far from a back edge then what to do how to traverse that and get L for it
Okay sir got it. Thank you :)
--------------------------------------- Credits: Ray Wang -------------------------------------------------------
cp-algorithms.com/graph/cutpoints.html
I'm still trying to understand it, but I understand it as this: We root the graph arbitrarily, creating a tree-like structure (i think it's called a dfs-tree), then notice 2 observations:
A node is an articulation point if: it's the root and has more than 1 child OR
A node is not the root and none of it's children have a back edge to the node's ancestors (aka. there's no cycles that lead back)
To efficiently check if a node meets the second observation, we use the L and d arrays. Instead of thinking of L as low, think of it as the earliest time we visited a node. If the earliest time we visited a child (aka. L[v]) is less than the time we visited our current node (d[u]) then that means in our dfs, we visited v from an ancestor, which means v has a back-edge to an ancestor.
More formally: iff L[v] < d[u], u is not an articulation point. Therefore, if L[v] >= d[u], u is an articulation point.
Super understandable !
Thank you ^^
Dr. Abdul, there seems to be a confusion here Sir. What if we evaluate L[2] and its parent is V(3) which has a D[3] = 1. But V(3) is definitely an articulation point but this scenario i have just mentioned will evaluate to False. Can you clarify Sir?
d[3] is 3..not 1
sir please upload videos for decrease and conquer, transform and conquer
nice video thanks
Alhamdulillah, Very nice exxplanation
Does articulation point and biconnected components mean the same ?
What if there in no back edges??
I am a little confused. If we take the parent-child pair of [1,4] then L[4] = 1 = d[1] then L[4] >= d[1]. Does that mean that 1 is also a articulation point?
the formula isn't valid for root node (node from which we started the dfs).
Exception in the root node
nice! but why not from 1 first to 2? i learned that its normal to do it in order. so 1-->2-->3-->5-->6-->3-->4-->1
@@abdul_bari THX=)
The general algorithm for DFS visit is: while not visited, do DFS visit. So it doesn't matter where you start. You will get a diff DFS tree based on where you start and the order of nodes in the adj list.
Thank you for your efforts
sir, is there any getting the chance of 2 or more articulations points in a single graph
>>>IF ANYONE KNOW PLEASE TELL ME
I watch his videos as brahmastra, when I didnt understood concept reading everywhere😅
Great explanation looking toward more videos about data structures
why the L(6), i.e. L of vertex 6 isn't 1?
we can use the path 6->3->2->1 and because L(1)=1 we can say that L(6)=L(1)=1
We can only go down on the tree, and ONCE we can go on a back-edge.
Thankyou.
What if the vertex chosen when comparing has no back edge? What would be his Lowest Number? Should it be its discovery time? or the discovery time from its last descendant?
@@abdul_bari Thank you very much!! You are the best
--------------------------------------- Credits: Ray Wang -------------------------------------------------------
cp-algorithms.com/graph/cutpoints.html
I'm still trying to understand it, but I understand it as this: We root the graph arbitrarily, creating a tree-like structure (i think it's called a dfs-tree), then notice 2 observations:
A node is an articulation point if: it's the root and has more than 1 child OR
A node is not the root and none of it's children have a back edge to the node's ancestors (aka. there's no cycles that lead back)
To efficiently check if a node meets the second observation, we use the L and d arrays. Instead of thinking of L as low, think of it as the earliest time we visited a node. If the earliest time we visited a child (aka. L[v]) is less than the time we visited our current node (d[u]) then that means in our dfs, we visited v from an ancestor, which means v has a back-edge to an ancestor.
More formally: iff L[v] < d[u], u is not an articulation point. Therefore, if L[v] >= d[u], u is an articulation point.
@@satishchandramedi9729 Thanks for the reply! I already passed the exams though. It was hard but this channel basically helped me a lot!
@@PBNinja That's great! But it might help you during campus recruitment hiring questions!
Best explanation.
Thank you.
a goldmine in youtube
sir can plz take session about strongly connected complet.
jaii Bari sirrrrrrrrrrrrr💥
Are articulation point and biconnected components same..??
Articulation points are the vertexes which when deleted from a graph yields two (or bi) connected components. They are not same but the latter is a consequence of removal of former.
what if there's no back edge from a vertex?
assume there is no 6 vertex so now acc to formula 5>=3 so we still know that the d[3]=3 is still a articulation point. try it.
Sir you are a living legend Your videos are awesome one thing that you should also add code in your videos of algorithms and explain it.Hope you will look into this matter.Lots of love from Pakistan
can we arbitrarily choose any vertex as the root for our DFS?
@@abdul_bari thanks!
Why is vertex 1 not considered an articulation point since the low(4) = 1 and the num(1) = 1 -> 1>=1 ???
1 is Root here and root is only considered as an articulation point if it has multiple children. But here it has just 1
how do those conditions work?
--------------------------------------- Credits: Ray Wang -------------------------------------------------------
cp-algorithms.com/graph/cutpoints.html
I'm still trying to understand it, but I understand it as this: We root the graph arbitrarily, creating a tree-like structure (i think it's called a dfs-tree), then notice 2 observations:
A node is an articulation point if: it's the root and has more than 1 child OR
A node is not the root and none of it's children have a back edge to the node's ancestors (aka. there's no cycles that lead back)
To efficiently check if a node meets the second observation, we use the L and d arrays. Instead of thinking of L as low, think of it as the earliest time we visited a node. If the earliest time we visited a child (aka. L[v]) is less than the time we visited our current node (d[u]) then that means in our dfs, we visited v from an ancestor, which means v has a back-edge to an ancestor.
More formally: iff L[v] < d[u], u is not an articulation point. Therefore, if L[v] >= d[u], u is an articulation point.
This is a great video.