Explanation of Algorithm for finding articulation points or cut vertices of a graph

by

Finding articulation vertices is an application of DFS.

In a nutshell,

  1. Apply DFS on a graph. Get the DFS tree.
  2. A node which is visited earlier is a “parent” of those nodes which are reached by it and visited later.
  3. If any child of a node does not have a path to any of the ancestors of its parent, it means that removing this node would make this child disjoint from the graph.
  4. There is an exception: the root of the tree. If it has more than one child, then it is an articulation point, otherwise not.

Point 3 essentially means that this node is an articulation point.

Now for a child, this path to the ancestors of the node would be through a back-edge from it or from any of its children.

All this is explained beautifully in this PDF.

More Related Contents:

  1. How to implement depth first search for graph with a non-recursive approach
  2. Why is depth-first search claimed to be space efficient?
  3. Complexity of absolute difference and sum
  4. What is a plain English explanation of “Big O” notation?
  5. Big O, how do you calculate/approximate it?
  6. How can building a heap be O(n) time complexity?
  7. How to find the lowest common ancestor of two nodes in any binary tree?
  8. Millions of 3D points: How to find the 10 of them closest to a given point?
  9. What would cause an algorithm to have O(log log n) complexity?
  10. Programmatically obtaining Big-O efficiency of code
  11. What is the best way to get the minimum or maximum value from an Array of numbers?
  12. Find connected components in a graph [closed]
  13. Finding all the shortest paths between two nodes in unweighted undirected graph
  14. Algorithm for “nice” grid line intervals on a graph
  15. Longest acyclic path in a directed unweighted graph
  16. help in the Donalds B. Johnson’s algorithm, i cannot understand the pseudo code (PART II)
  17. Why use Dijkstra’s Algorithm if Breadth First Search (BFS) can do the same thing faster?
  18. How does Dijkstra’s Algorithm and A-Star compare?
  19. What are the differences between segment trees, interval trees, binary indexed trees and range trees?
  20. Big-oh vs big-theta [duplicate]
  21. Why DFS and not BFS for finding cycle in graphs
  22. Time Complexity of two for loops [duplicate]
  23. graph – Dijkstra for The Single-Source Longest Path
  24. Why does Dijkstra’s algorithm use decrease-key?
  25. Algorithm to simplify a weighted directed graph of debts
  26. Why is bubble sort O(n^2)?
  27. Finding connected components of adjacency matrix graph
  28. Computational complexity of base conversion
  29. How to apply binary search O(log n) on a sorted linked list?
  30. Appointment scheduling algorithm (N people with N free-busy slots, constraint-satisfaction)

Leave a Comment