1

Since i am new to graph, i am not getting algorithm that can can clearly explain how to find articulation point in graph. Please anyone explain? thanx in advance

user2263604
  • 11
  • 1
  • 3
  • Does this answer your question? [Explanation of Algorithm for finding articulation points or cut vertices of a graph](https://stackoverflow.com/questions/15873153/explanation-of-algorithm-for-finding-articulation-points-or-cut-vertices-of-a-gr) – KGhatak Apr 29 '21 at 06:30

2 Answers2

0

A simple algorithm:

For each Node N so: 1. Take it away 2. Count the number of connected components. Either by dfs or bfs. If that's still one, continue with the loop. If it is two, you have found an articulation point. Mark and continue with the loop.

This will run in quadratic time. Not sure whether there is a better algorithm.

Edit: i found some java source code on this site: http://algs4.cs.princeton.edu/41undirected/Biconnected.java.html

DasKrümelmonster
  • 5,816
  • 1
  • 24
  • 45
  • thanks for replying. Actually i am looking for some linear time algorithm, it is mentioned in many sites but it is too complicated to understand! The algorithm which you told is just simple brute force approach. – user2263604 Apr 09 '13 at 21:06
0

Refer to this explanation. I hope you would find it useful.

http://www.geeksforgeeks.org/articulation-points-or-cut-vertices-in-a-graph/

Shivam Dixit
  • 318
  • 4
  • 13