Graph Theory37 sections · 1633 units
Open in Course

DFS Tree Example

(Tree edges vs back edges)

Graph: 1−21-2, 2−32-3, 3−13-1, 2−42-4. Start DFS at 11. Tree edges: 1−21-2, 2−32-3, 2−42-4. Back edge: 3−13-1 (connects 33 back to ancestor 11). Edge 2−42-4 is a bridge because there is no back edge providing an alternate path to 44.

Vertex 44 is a dead end. Edges 1−21-2 and 2−32-3 are not bridges because back edge 3−13-1 creates a cycle, providing an alternate path between any two vertices in the triangle.