6.12 Bridges(Cut Edge) in a Graph | Find All Bridges in a Graph | Graph Theory
ฝัง
- เผยแพร่เมื่อ 23 ก.ย. 2024
- In this video I have explained how to find all Bridges in a Graph using DFS Traversal. Bridge is also known as Cut Edge.
DSA Full Course: https: • Data Structures and Al...
******************************************
See Complete Playlists:
C Programming Course: • Programming in C
C++ Programming: • C++ Complete Course
Python Full Course: • Python - Basic to Advance
Printing Pattern in C: • Printing Pattern Progr...
DAA Course: • Design and Analysis of...
Placement Series: • Placements Series
Dynamic Programming: • Dynamic Programming
Operating Systems: // • Operating Systems
DBMS: • DBMS (Database Managem...
********************************************
Connect & Contact Me:
Facebook: / jennys-lectures-csit-n...
Quora: www.quora.com/...
Instagram: / jayantikhatrilamba
#graphtheory #bridgeinGraph #datastructures #jennyslectures
can't be better explained watched take u forward video techdose video and love babbar video no video comes close to this . This video even beingg so old explains the concept clearly. Really old is gold. Keep up the good work mam.
Best Explanation till now on TH-cam for Finding Bridges in Graph!! Thanks a lot, Ma'am.
I watched 10 different videos and understood only yours! Thank you SOOO MUCH!!! Greetings from Sydney :)
Very well explained with thought process & intuition, struggled with other videos on youtube.
Great explaination. I have seen so many videos. Yours was the simplest and the clearest. Can you also write the code?
I don't think that the explanation for this concept can be better than this .. If you watch any of the others youtube channel no one has explained this concept in such a beautiful wayy..... Salute to your Knowledge mam
this is by far the best explanation of this topic i have found online
I approach a girl,
she : 6:46
haha
Happens with me every-time when I approach any girl x(
I was stressing out for the exam. Thanks for your comment haha
i don't think i will ever forget this algorithm - thanks to this :)
🤣😆
your way of teaching is good thank for this vedio
thank you so much, most detailed explanation on this topic all over youtube is here
Apologies, I never refer your videos to study. But from this video, I became your fan.
Such a tough concept is explained beautifully.
Here is Java code, did what Jenny said.
```
class Solution {
private int currTime;
Solution(){
this.currTime = 0;
}
public List criticalConnections(int n, List connections) {
List[] graph = new ArrayList[n];
// Construction of graph
for(int i = 0; i < n; i++){
graph[i] = new ArrayList();
}
for(List connection : connections){
int first = connection.get(0);
int second = connection.get(1);
graph[first].add(second);
graph[second].add(first);
}
int[] tIn = new int[n];
Arrays.fill(tIn, -1);
List result = new ArrayList();
findBridges(graph, 0, -1, tIn, result);
return result;
}
private int findBridges(List[] graph, int node, int parent, int[] tIn, List result){
tIn[node] = ++currTime;
List nbrs = graph[node];
int min = tIn[node];
for(int nbr : nbrs){
int val = tIn[nbr];
if(val == -1){
val = findBridges(graph, nbr, node, tIn, result);
if(parent != nbr)
min = Math.min(val, min);
if(val > tIn[node]){
result.add(Arrays.asList(node, nbr));
}
}
if(nbr != parent){
min = Math.min(min, tIn[nbr]);
}
}
return min;
}
}
```
Thank you so much ma'am. You taught this complex topic so easily.
she teaches so amazingly , wondering why she has so less subs ? She deserves way more
imo, This is one of the most Well Explained YT Video of all time.
Hats off to you Maam ❤❤
okk let's be true, i am completing my DSA from love babbar playlist, although i've watched several of your videos earlier but it was mainly for my college subjects. And by god, this algo is so freaking hard, couldn't understand it by love babbar or any other video on youtube, but the way you presented it, it's just phenomenal. Hats off to you, you're the best. RESPECT++.
This is such a great video and hats of to your explanation. Please keep up the good work and I must tell you that you are doing a great job :)
What a Fantastic Explanation!!! Thanks Jenny, you're an Angel.
After seeing many videos for this problem...Only yours gave answer to my desperation .. thank you so much Jenny..
Excellent work Jenny !!!!!
A little correction. At 4:00, you said B can go to A only. But it can go to E too.
a comprehensive video that contains all the details, ++rep
ma'am you're fabulous. I watched so amny videos of tarjan's algo as well but couldn't understand. The way you explained. Hats off. You're the best
I don't know how can i thank you mam . know one in yt explain this concept perfect just like you
Understood it in one go...Amazing🔥🔥
this is fabulous, most precise n clear explanation for Tarjan's algorithm
Mam, nobody explained the way you explained this bridges concept clearly. I was soo confused but you explained soo well. Thankyou soo much mam
Ahh....Finally I understood the concept with your video. Thanks!!
8:56 is the min discovery time 2 from edge F. You said its 1 from edge E but discovery time of edge E is 7. Kindly explain what did i miss here?
It should be 2 only from edge F.
best explanation till now on youtube for finding bridges in graph....Thanks a lot ma'am....ma'am please also do with the code as if possible so that we don't need to find of its code . if we get confused some how ..?
After trying to understand it so many times I came to youuu , explanation is best!!
And we meet again!! 😂
Thank you for this lecture.... well explained
Jenny! mai to tharro fan ban gaya!!! Thank you!
hello mam ye starting time or ending time lena jaruri hai kya simple visited array bna kr nhi kr skte kya?
Best explanation till now on TH-cam
no doubt this is the best explanation of finding bridge on youtube
5:19 "What is the FANDA" XD
Well Explained!!!
You may call it "concept behind it"
Very good explanation. Understood very well, and am able to write program all by myself. Thanks Mam.
Wonderful explanation!
Well explained ! It would be nice to have the entire video in English! This can attract lot of international candidates.
I came here after more than 1 yr , you again rock ma'am 🤟 ..
Thanks a lot for all your wonderful lectures
It was an amazing explanation mam. Love u😊
Thanks Pankaj.... Thank you for the support. It’s great to be part of your success.
@@JennyslecturesCSIT Can I have the code?
Your Explanation is awesome
Very nice mam Now I able to understand intitution and logic of this algorithm
Very nice explanation ma'am. I don't understood about this find all bridges algo on other yt channels.
Great explanation! Thank you.
TIP: Reason why we need to check of the current min time is greater than the next vertex :- If a vertex is having a child such that the earliest discovered vertex that can be reached from the vertices in the subtree rooted at has a discovery time greater than or equal to , then does not have a back edge, and thus will be an articulation point. where back edge is an edge which can connect to the parent of parent.
Now I got the real intuition behind , why are we keep tracking of lowest visited time of adjacent vertices .Thanks for explanation.
But ma'am i don't know anyone who is better than you... love your lectures
Thanks a lot, i have spent more time on that but now i got it.
Best and clearest explanation!
What an awesome explanation!
great explanation
Brilliant Explanation
Thank you understood the concept very well. 🙏
Underrated!
Thank you for the detailed explaination
Thanks for such a brilliant explanation!
Your video is awesome. Thanks for helping us out.
wow vey well explained
is this video a bit erroneous ? At 18:25 , starting time of node c is told to be 1 not 4 .
Can you please extend this video to explain articulation nodes and how to eliminate articulation from the graph -> can we add any edge from the articulation point.
coming here after watching striver/take u forward's video
nice explanation!!
Thanks for this amazing explanation...
very well done , explain was simple and lucid
Nice explanation mam
Thank You Ma'am
Plz mam explain it's algo with code🙏🙏
wow this took a while to abosrb. Its a mental gymnastic in my head at start
Best Explanation 👍
Thank you! Very good explanation!!!
Amazing explanation!!
Great Explanation!
Jenny: "I know someone who is better than you because he came before you"
Me: *crying in the corner*
Good explanation. Very Useful. Thanks a lot. :)
Very good explanation.
Great explanation.
It was Very helpful 😍
well explained
I don't know someone whose explanation on this topic is better than you.
Thank you !
Amazing explanation
Very well explained :D Thanks!
which book is best for graph algorithm , please tell me
best explanation
Amazing Mam
superb explanation !!!
Good explanation. Thanks
Thanks alot mam❤❤
really very nice explaination
Thank you so much!! Your videos have helped me alot :-). You are beauty with brains :--)
excellent explanation 💯
A lot of thanks, I was struggling to understand it.
Thanks 🙏🏽👍
awesome explanation maam
Thanks
wew the best explanation.
Tq so muchh mam 💖
Thank you :)