Graph Theory37 sections · 1633 units
Open in Course

Intro

Finding weak spots in networks

In this section, I'll teach you how to find critical edges and vertices in graphs. A bridge is an edge whose removal disconnects the graph. An articulation point is a vertex whose removal disconnects the graph. You will learn Tarjan's algorithm, which finds all bridges and articulation points in O(V+E)O(V+E) time using DFS.

The algorithm tracks discovery times and low-link values to identify critical connections. By the end, you will solve and understand how to detect network vulnerabilities.

1770082149797-01ejfnw0p31r.jpg