In a Depth-First Search (DFS) forest, what type of edge connects a vertex to an ancestor in the same DFS tree?
Show answer
Back edge
Back edges are crucial in graph analysis because their presence in a directed or undirected graph indicates the existence of a cycle. They connect a node to one of its ancestors in the DFS tree.
Also asked as:
- In a DFS tree, what is the term for an edge that points from a node to one of its ancestors?