ฝัง
- เผยแพร่เมื่อ 1 ส.ค. 2024
- In this video, I have discussed about finding articulation points in a graph. Also known as cut vertices, these have many real life applications and are a important topic in graph study. I have explained two algorithms for finding articulation point:
1. Brute Force Algorithm
2. Tarjan's algorithm : It is an efficient graph algorithm to find the strongly connected components in a directed graph in linear time by utilizing Depth First Search traversal of a graph. The key idea used is that nodes of strongly connected component form a subtree in the DFS spanning tree of the graph.
I have explained both the algorithms using an example and have implemented in C++ as well.
Source Code: github.com/fit-coder/fitcoder...
00:00 Introduction
00:26 Articulation point
01:57 Biconnectivity
02:42 Brute force algorithm
04:32 Tarjan's algorithm
13:15 Algorithm Pseudo Code
26:03 C++ Implementation
-------------------------------------------------------------
I live in New Delhi and love explaining programming concepts. I have done M.Tech(BITS Pilani) + B.Tech(PEC, Chandigarh) in Computer Science and am currently working as a software engineer in a MNC.
If you like my content, please like, share my videos and subscribe to the channel.
-------------------------------------------------------------
For in-depth Graph theory and implementation details, please refer to the below videos:
Graphs Introduction: • Introduction to Graphs...
Graph representation:
Adjacency Matrix: • Graph representation I...
Adjacency List: • Graph representation I...
Incidence Matrix: • Graph representation I...
Traversal techniques:
BFS, Breadth First Search: • BFS Breadth First Sear...
DFS, Depth First Search: • DFS Depth First Search...
Shortest Path algorithms:
Dijkstra algorithm: • Dijkstra Algorithm | S...
Bellman Ford algorithm: • Bellman Ford Algorithm...
Floyd Warshall algorithm: • Floyd Warshall Algorit...
Minimum Spanning Tree:
Kruskal algorithm: • Kruskal Algorithm | Mi...
Prim algorithm: • Prim Algorithm | Minim...
Topological sort (Kahn algorithm): • Topological Sort | Kah...
Articulation points / Cut vertices:
Tarjan algorithm: • Articulation Points | ...
Disjoint Set / Union Find: • Disjoint Set | Union F...
Maximum Flow Problem:
Ford Fulkerson algorithm: • Ford Fulkerson Algorit...
Graph coloring / Chromatic number: • Graph Coloring | Chrom...
Hamiltonian cycle: • Hamiltonian Cycle (Cir...
Euler cycle (Fleury algorithm): • Euler Cycle (Circuit) ...
#DataStructure,#Graphs,#FitCoder,#Algorithm,#competitiveprogramming
This is one of the best explanation of Tarjan’s algorithm. Very well explained 👌🏻 Keep up the good work 👍🏻
thank you :)
That was the best video about Tarjan , seriously
Thank you for your efforts
Welcome :)
Finally understood this algo...watched many videos but this one was the best....keep up the good work
thank you :)
Great work sir 👍
thanks :)
this playlist has helped me gain confidence in graph algorithms .
can you also please attach a list of problems from basics to advanced of graph algorithms so that we can be more confident in graph
There is a video named Graph questions on the channel...please also check that out
Thank you so much. I know how Torjan's algorithm work now.
thank you :) Please like, share and subscribe if you haven't already.
This has cleared my many doubts about the algo 👍
Glad to hear that :)
Nicely explained the concept !!!
thank you :)
So far best explaination👍
thank you :)
00:00 Introduction
00:26 Articulation point
01:57 Biconnectivity
02:42 Brute force algorithm
04:32 Tarjan's algorithm
13:15 Algorithm Pseudo Code
26:03 C++ Implementation
Very well explained
thank you :)
Great explanation
thank you :)
4:02 in brute force pseudocode I think there must be append v after remove it.
Right. Thanks for pointing out, I missed it 👍
@@FitCoder yes sir i have also seen that one , but now it's clear from comment.
great explanation
thank you :)
Nice explaination
thank you :)
Great explanation. Had to refer to this video many times for clearing any doubts.
Also, I have a query regarding Tarjan's algortihm. On wiki, it is presented with a stack invariant for getting SCCs.
en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm
Is there anyway we can modify it to find out the bridges in graph ?
Very nice explanation, one comment, try to use u & v instead of v and av
Thanks for the feedback :)
NICE BRO :3
thank you :)
12:30 why C is compared with low time of G that is 7 and not with the low Time of D that is 1 ?
If for any child that condition is true, that means vertex is an AP
Why G has low time 7 but not 1?
Low time is minimum of 3 values. Since there are no back edges from G and G has no subtree, so low time of G is equal to discovery time of G which is 7
💖,..
Fit Coder - at this time th-cam.com/video/qNVNoZJFp_g/w-d-xo.html , when we calculate the low time for B, do we need to consider all the childs, like you have considered D and used low value of it to node B.
You are explaining the path vary good. We have to do this, that, and that. But you do not explain why we do that. For doing that what is the effect for it. An example you said for low time = min(disc[u],disc[backedge],low[v]) but why low time is that? What we try to achieve with low time? those are the questions that are not addressed. without knowing those a learner can not remember it properly. He/she will forget every time because he/she just knows a path but doesn't know why they go on this path?
Thanks for the feedback. I got your point. Noted.
But on the second condition,in my opinion,you just write statement incorrectly.If you pay attention,you can see that here you should write "ancestor of u",shouldn't write "ancestor of v"
.If it is correct what i said,please say to me,I just wanna be sure