Algorithms Homework 16



Homework 16

A tree is a connected, acyclic graph (i.e., no cycles). Describe an algorithm
to determine whether a given undirected graph with n vertices and m edges is
a tree in O(n + m) time.
Hint: be careful when detecting cycles—it’s easy to “detect” cycles that
aren’t actually cycles. You may wish to simulate your algorithm on a two- or
three-vertex tree to make sure it is correct.


There are no reviews yet.

Be the first to review “Algorithms Homework 16”

Your email address will not be published.