LEVEL 4 OF 5

Graph Algorithms

Explore connections and find your way.

DFS

Explore one branch as far as possible before returning to other frontier entries.

Explore vertices in increasing number of edges from the start, using a queue to finish one distance layer before the next.

Resolve a directed dependency graph by repeatedly removing vertices with no remaining incoming edges.

Represent disjoint components by rooted parent forests and merge components by linking their roots.

Finalize the nearest unfinished vertex, then relax outgoing edges to improve tentative distances to other vertices.

Associate each vertex with the least cost of reaching it under the problem's allowed moves.