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

user_1988876 0
Viewed 32163

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.

enter image description here

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?

tree graph algorithm
3 Answers

If an undirected given graph is a tree:

  • the graph is connected
  • the number of edges equals the number of nodes - 1.
user_72130530

An undirected graph is a tree when the following two conditions are true:

  1. The graph is a connected graph.
  2. The graph does not have a cycle.

A directed graph is a tree when the following three conditions are true:

  1. The graph is a connected graph.
  2. The graph does not have a cycle.
  3. Each node except root should have exactly one parent.
user_45232350
Related