Menu
What is the time complexity of the Best algorithm to determine if an undirected graph is a tree??
can we say Big-oh(n) , with n vertices??
224
In graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one path, or equivalently a connected acyclic undirected graph.
We can use a traversal algorithm, either depth-first or breadth-first, to find the connected components of an undirected graph. If we do a traversal starting from a vertex v, then we will visit all the vertices that can be reached from v. These are the vertices in the connected component that contains v.
Theorem: An undirected graph is a tree iff there is exactly one simple path between each pair of vertices. Proof: If we have a graph T which is a tree, then it must be connected with no cycles. Since T is connected, there must be at least one simple path between each pair of vertices.
Yes, it is O(n). With a depth-first search in a directed graph has 3 types of non-tree edges - cross, back and forward.
For an undirected case, the only kind of non-tree edge is a back edge. So, you just need to search for back edges.
In short, choose a starting vertex. Traverse and keep checking if the edge encountered is a back edge. If you find n-1 tree edges without finding back-edges and then, run out of edges, you're gold.
(Just to clarify - a back edge is one where the vertex at the other end has already been encountered - and because of the properties of undirected graphs, the vertex at the other end would be an ancestor of the present node in the tree that is being constructed.)
129
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
