Determining whether or not a directed or undirected graph is a tree

Question

I would like to know of a fast algorithm to determine if a directed or undirected graph is a tree.

This post seems to deal with it, but it is not very clear; according to this link, if the graph is acyclic, then it is a tree. But if you consider the directed and undirected graphs below: in my opinion, only graphs 1 and 4 are trees. I suppose 3 is neither cyclic, nor a tree.

What needs to be checked to see if a directed or undirected graph is a tree or not, in an efficient way? And taking it one step ahead: if a tree exists then is it a binary tree or not?

Answer 1

For a directed graph:

• Find the vertex with no incoming edges (if there is more than one or no such vertex, fail).

• Do a breadth-first or depth-first search from that vertex. If you encounter an already visited vertex, it's not a tree.

• If you're done and there are unexplored vertices, it's not a tree - the graph is not connected.

• Otherwise, it's a tree.

• To check for a binary tree, additionally check if each vertex has at most 2 outgoing edges.

For an undirected graph:

• Check for a cycle with a simple depth-first search (starting from any vertex) - "If an unexplored edge leads to a node visited before, then the graph contains a cycle." If there's a cycle, it's not a tree.

• If the above process leaves some vertices unexplored, it's not a tree, because it's not connected.

• Otherwise, it's a tree.

• To check for a binary tree, if the graph has more than one vertex, additionally check that all vertices have 1-3 edges (1 to the parent and 2 to the children).

  Checking for the root, i.e. whether one vertex contains 1-2 edges, is not necessary as there has to be vertices with 1-2 edges in an acyclic connected undirected graph.

  Note that identifying the root is not generically possible (it may be possible in special cases) as, in many undirected graphs, more than one of the nodes can be made the root if we were to make it a binary tree.