Grokking the Coding Interview: Patterns for Coding Questions
Vote

0% completed

​

Introduction to Articulation Points and Bridges Pattern

You are given a network of servers and the links between them. Which single server, if it fails, splits the network into disconnected parts?

0 -- 1 -- 2 -- 3 -- 4
 \       /
  -------

Removing server 2 leaves 3 and 4 cut off from 0 and 1. Removing server 1 leaves everything connected, because 0 and 2 still have a direct link.

A node whose removal disconnects the graph is called an articulation point. An edge whose removal does the same is called a bridge.

The direct method removes each node in turn, runs a traversal, and counts the pieces. That is O(V) traversals, so

.....

.....

.....

Like the course? Get enrolled and start learning!

Reading Progress

0%

Vote for new content