Find Bridges in a graph using Tarjans Algorithm | Cut Edge
Vložit
- čas přidán 15. 09. 2020
- This video explains what is a bridge along with its application and how to find all the bridges in a graph using tarjans algorithm.I have first explained the concept of bridges and then showed the observations needed to understand the algorithm.I have shown all the required conditions using simple examples.I have also shown the dry run explanation for finding bridges.At the end of the video, I have also shown the code for this algorithm.CODE LINK is present below as usual. 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 :)
========================================================================
Join this channel to get access to perks:
/ @techdose4u
INSTAGRAM : / surya.pratap.k
SUPPORT OUR WORK: / techdose
LinkedIn: / surya-pratap-kahar-47b...
WEBSITE: techdose.co.in/
TELEGRAM Channel LINK: t.me/codewithTECHDOSE
TELEGRAM Group LINK: t.me/joinchat/SRVOIxWR4sRIVv5...
=======================================================================
CODE LINK: gist.github.com/SuryaPratapK/...
USEFUL LINKS:-
Tarjans strongly connected components algorithm: • Tarjans strongly conne...
Find Articulation Points using Tarjans Algorithm: • Find Articulation Poin...
Codeforces: codeforces.com/blog/entry/71146
all 3 videos of tarjans algo are perfectly explained!!Thanks . You made them simple.
I am glad that you found it helpful 😃
Such a good explanation.This videos made me saw your entire series..
Awesome detailed explanation! Thank you so much!! :D
All three videos of tarjan (cut edge, cut vertex and scc) are top quality.
Thanks 😊
Another top level video! Love your channel!
❤️
Initially at the SCC I struggled to understand that concept, once that is done... Next both the videos are literally easy and simple bcz, u have teached that much level 😅 in SCC. Thank you sir for delivering these algorithms.
Hands down the best source for graphs. Thanks a lot
Welcome 🤗
This is the best explanation I have seen on this topic.
Thanks
Great Video thanks a lot for making these things simple.
Welcome
Best explanation ever seen! Great work ,huge respect!!
google company deserves you 😀
Company deserves good students. Some should be teachers too 😁
@@techdose4u now you are in Google
😀😀😀 Congrats
Now he is in Google 🔥🔥
Having knowledge and delivering knowledge are two different things which can be proved by Tech Dose . People are out there who have tons of programming skills but they dont have the way to deliver that.
😅
NICE Explaination.
Muchas Gracias
Very nice explanation. Can you please clarify this..
After giving low[] values for all nodes, then by checking each edge(u,v) in graph if low[u]!==low[v] it is a bridge.
In APs video the condition for a node to not have a back edge and be an AP was disc[u]
Best explanation
You are a genius.
Very well done
Amazing 😍
sir please its my humble request to make video on " 78. Subset problem of leetcode" .please sir.
Big fan of urs ..thankyou
Good Workkkk!!
Thanks
A great Teacher
:)
Awesome
Do this works for directed graph too?
you are champion sir....
😊
@TECH DOSE, Thanks, it was a very good tutorial. There is an issue i found in your code. Your code gives the incorrect ans for below test
adj[1].pb(3);
adj[1].pb(4);
adj[2].pb(1);
adj[3].pb(2);
adj[4].pb(2);
adj[4].pb(3);
Here there should be no bridge, but your algo returns one bridge, 1->4. Could, i be missing something ?
Excellent explaination
Thanks
very nice
great Content🔥
Thanks
Can someone please explain, what exactly is low[ ]. Am not able to figure it out?
can we also go for this algo
1.for each src vertex find if there is an cycle(cycle detection in undirected graph) that reaches itsef.
2.if(true) then it is not a part of bridge
else all vertex connected to src vertex will be a bridge.
Even I have the same doubt.
I think all the edges that does not lie in a cycle are the only bridges. Please correct us if we are wrong.
Thanks for the video! Do we really need parents array? Can it be replaced by an int param that identifies who is this vertex's parent?
Try it :)
@@techdose4u I havent tried that yet, but my java version of your code passing all cases on leetcode.
Do you have a java version please?
Mine fails the case with 1000 inputs and 0 expected, but I am returning these: [[880,975],[618,86],[256,52],[214,104],[718,543],[591,412]]
Do you see anything wrong with it please?
class Solution {
// trajans
Map adj = new HashMap();
List toReturn = new ArrayList();
int time = 0;
public List criticalConnections(int n, List connections) {
int[] discoverys = new int[n];
int[] lows = new int[n];
int[] parents = new int[n];
// init adj garph
for (int i = 0; i < n; i++){
adj.put(i, new ArrayList());
discoverys[i] = -1;
lows[i] = -1;
parents[i] = -1;
}
for (List edge : connections){
adj.get(edge.get(0)).add(edge.get(1));
adj.get(edge.get(1)).add(edge.get(0));
}
// for (int i = 0; i < n; i++){
// if (discoverys[i] == -1){
// dfs(discoverys, lows, parents, i);
// }
// }
dfs(discoverys, lows, parents, 0);
return toReturn;
}
// returns the low value at edge
// parents array is not relaly needed
private void dfs(int[] discoverys, int[] lows, int[] parents, int edge){
discoverys[edge] = time;
lows[edge] = time;
time++;
for (int neighbour: adj.get(edge)){
// not visited yet
if (discoverys[neighbour] == -1){
// set this edge as neighbours parent
parents[neighbour] = edge;
// dont dfs on nodes already visiting/visited
if (discoverys[neighbour] == -1){
dfs(discoverys, lows, parents, neighbour);
}
// its a regular tree edge, therefore its not explored yet
lows[edge] = Math.min(lows[edge], lows[neighbour]);
// possibly update the list of bridges
// neighbour has greated discovery # than our vertex, means this is a bridge
if (lows[neighbour] > lows[edge]){
List toAdd = Arrays.asList(edge, neighbour);
toReturn.add(toAdd);
}
} else if (neighbour != parents[edge] ){ // neighbour is already visited, its a backedge
// dont do calculation on backedge
lows[edge] = Math.min(lows[edge], discoverys[neighbour]);
}
}
}
@@allen724 Your implementation is wrong. The condition to add the bridge is low[neighbour] > disc[edge] but you have written low[neighbour] > low[edge].
Should time be declared outside function? Because it gets back to 0 every DFS call
While dfs, if we found any visited node, then we update the low value of current node as minimum betwn low of current and discovery time of visited node. I think it could be good if we compare betwn low values of both nodes (current and visited) and assign minimum from them. Plz reply me if I am wrong..Caz I found correct results so in dry run
I think the values of discovery time and low value for the ancestor will be the same since the ancestor is the start node in the strongly connected component. Therefore, I think both would give a correct result.
big fan
nice video!! only one question, if v has been visited before, why is low[u] = min(low[u], disc[v]). why is it not low[u] = min(low[u][, low[v])?
Coz only 1 back edge is taken and not multiple back edges.
Sir are you also going to cover *network flows* ? btw thanx a lot for the videos :)
Umm....I will just put one more video for Eulerian path and circuit. After that I will solve leetcode questions.
@@techdose4u Yes sir, that is the good decision u thought. thanks a lot sir...
Why are we not differentiating between back edge and cross edge in the case of Articulation Points and finding bridges?
Because in case of Undirected graph cross edge doesn't exist
i just have one question, why are we checking parent when we do not check in Tarjan's Algorithm ?
why isn't it low[v]>low[u], that should also work right? But it doesnt i guess. Can someone explain pls
Best always
Thanks
Great Great 😀
Thanks 😊
R a Sujoy, Wang ma'am er project krli?
@@43shubhashisdey76 na re korini...shuru korbo😁
Great video!! But why the condition is (low[v] > disc[u]) in case of Bridge but (low[v] >= disc[u]) in case of Articulation Point?
because back-edge can't be bridge-edge.
because, low[v]==disc[u] means that there is a backedge from "child subgraph of u"(i.e. either v or node ahead) to the node u itself. So, in articulation point, we are removing nodes, therefore all the associated edges (wheter backedge to itself or simple tree edge to subgraph) are removed, resulting in disconnected graph.
Whereas, in edge cut, we are not removing node (i.e. removing tree edge only), so if there is low([v]==dis[u], a backedge to u is present. So removing tree edge doesn't disconnect the graph (as it is still connected using backedge to u).
Hope it helps!!!!!!!!
Hello Surya - I left you a comment on the GItHub repo, would appreciate if you could look at it - Thank you for all that you are doing for us!
I am really not getting time for any replies currently otherwise I would have 😅
@@techdose4u No worries, please get to it if and when you can!
here is bit confusion that i want to state . This is in regard to a node that's already been visited and is neighbour of our current node and NOT PARENT . THE CODE SAYS FOR THIS -> lowtime[curNode]=min(lowtime[curNode] , desctime[neighbourNode]) . Now suppose the neighbour node is connected to start node so its lowtime=0 and desctime some +ve val . so shouldn't our current nodes low time be 0 rather then some +ve val less then its current low time . // lowtime[curNode]=min(lowtime[curNode] ,lowtime[neighbourNode])
Tarjans is arguably the toughest concept in DSA.
Sir reply please
To remove an articulation point from a graph we need to ?
A: remove an edge
B: add an edge
C: both a and b
D: none of the above
optiion B add abackedge to be specific
why we have taken low[v]>disc[u] condition check instead of low[v]>=disc[u] as discussed in articulation points video
Because in a bridge, we have a line which has two ends U and V, whereas an articulation point has only 1 point.
because in articulation point when we remove the point we remove all of its adjacent edges so even if low[v]==disc[u] then its valid , here however if low[v]==disc[u] , that means even if we remove current edge , everythings gonna be connected by that back edge , hope i am making sense :)
Sir please make a video on 1192. Critical Connections in a Network. I am preparing for amazon interview.
I will do it.
Finding bridges is same as critical connections in a network man
@@harishwarreddy9114 yes but maybe just for an example solution :)
@@techdose4u okay , btw your video made complex topic so easy for me Thank you . You are the best in explaining any topic
Thanks for your appreciation ❤️
The video really helped me understand. But I'm still unable to understand why are we not caring about crossedges here?
They won't alter your result in any way
Why we are not considering child to parent edge? I think the reason behind not taking child to parent edge because as it is undirected graph, where each and every edges are bi directional in nature. Please tell me one specific reason so if someone ask me about it i can easily explain him.
bro u are famous ..my roommate knows u already
why low[u]=time,i couldn't understood that?help anyone please
Watch Tarjan's SCC video
To remove an articulation point from a graph we need to ?
A: remove an edge
B: add an edge
C: both a and b
D: none of the above
Please sir reply
add back edge
Sirji pranam 🙏🏻
🙏
Sir....please make videos on coding questions for tcs digital and ncr corporation....only 10 days left for the exam...please help sir.....
What videos ?
@@techdose4u videos suggesting some coding questions related to these exams....which could practiced in this short span of time...
Sir, I really request you to make a video for students in 7th sem, and cover every student (whether his preparation level is 20 percent or he has just started)
TRUST ME, THIS IS THE MOST WATCHED VIDEO ON CODING BLOCKS CHANNEL, and unfortunately that video is not worth
watching..:/
Sir, please consider this..and try to make a video on it asap..
Because we need you the most..this time..
How will we strategise our preparation..
Only you can help
This solution is giving Time Limit Exceeded Error on leetcode
Which problem ?
@@techdose4u 1192. Critical Connections in a network
@@nitishgoyal9910 there was no problem. I solved that yesterday. I will make that video today. You can see the code.
@UCP3oO5eS2kWCKGs5H86FlyQ thanks
To remove an articulation point from a graph we need to ?
A: remove an edge
B: add an edge
C: both a and b
D: none of the above
We could also use just single integer as parent and pass "u" every time in DFS function and check this parent with "v". First call to function pass -1 as parent
To hard for me
😅