This guide explains Articulation Points from first principles. The goal is to understand the problem it solves, why the algorithm works, how to implement it, and where it appears in real software systems.
What problem does it solve?
Articulation Points belongs to the graph-algorithm toolbox. Before coding, define what the vertices represent, what an edge means, and what result the system actually needs.
The core idea in simple terms
با DFS و مقادیر discovery/low میفهمیم کدام رأس نقش نقطه شکست دارد.
Step-by-step process
- DFS و discovery time را ثبت میکنیم.
- low هر رأس را محاسبه میکنیم.
- ریشه با بیش از یک child بحرانی است.
- برای غیرریشه اگر low[child] >= disc[node] باشد، node بحرانی است.
JavaScript example
// Tarjan idea: a non-root u is critical when low[v] >= disc[u]
// for one of its DFS children v. A DFS root is critical with >1 child.
function isArticulation(discU, lowChild) {
return lowChild >= discU;
}Real-world and workplace examples
- روتر بحرانی
- Single Point of Failure
- ایستگاه کلیدی حملونقل
- سرویس مرکزی زیرساخت
Time and space complexity
O(V + E) time و O(V) space
When should you use it?
Use it when the problem matches this condition: تحلیل نقاط شکست شبکه.
When is it not a good fit?
It is usually not the best choice when: برای یال بحرانی باید Bridges را بررسی کرد..
Summary
Do not choose an algorithm by name alone. First identify whether the graph is directed or undirected, weighted or unweighted, and whether the goal is traversal, reachability, shortest path, connectivity, spanning structure, or combinatorial optimization.