Graph Traversal Applications: Testing for Cycles and Connectedness

Data Structures and Algorithms with Object-Oriented Design Patterns in C#

Graph Traversal Applications:
Testing for Cycles and Connectedness

This section presents several graph algorithms that are based on graph traversals. The first two algorithms test undirected and directed graphs for connectedness. Both algorithms are implemented using the depth-first traversal. The third algorithm tests a directed graph for cycles. It is implemented using a topological-order traversal.

Connectedness of an Undirected Graph
Connectedness of a Directed Graph
Testing Strong Connectedness
Testing for Cycles in a Directed Graph