Back Edge

There's a total of 1 notes tagged with "Back Edge".

Wed, Jun 24, 2015

Traversal of graphs

There are many ways to traverse a graph. For example, through breadth-first search and depth-first search. Exploring it with a breadth-first search has interesting properties, like implicitly computing the distance from a source $s$ to all the reachable vertices. Exploring it with a depth-first search has properties related to edges, like finding back edges, forward edges, and cross edges. This article has implementations for both BFS and DFS.