21

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?

Tomerikoo
  • 18,379
  • 16
  • 47
  • 61
brain storm
  • 30,124
  • 69
  • 225
  • 393
  • 4
    A quick note, the linked question *does* deal with only the undirected case. My understanding is that you wanted to deal with the directed case? In the directed case, there are also other cases to worry about (is `A -> B <- C` a tree?). – Dennis Meng Dec 13 '13 at 00:27

4 Answers4

40

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.

Bernhard Barker
  • 54,589
  • 14
  • 104
  • 138
  • 1
    regarding point 1 : I could have a private `OutgoingEdge` array field in the Vertex class, such that when each edge is added to graph, I can update this field. for every vertex, I check if this array length is > 1. if it is, it is not a tree.. – brain storm Dec 13 '13 at 01:59
  • regarding point 2: this is nothing but cycle detection right? any specific reason for BFS over DFS – brain storm Dec 13 '13 at 02:06
  • regarding point 3: I can get this information from my `outgoingEdge` array field if its length is <=2 – brain storm Dec 13 '13 at 02:07
  • as you mention checking for the root in undirected acyclic connected graph is not essential, because there are possible of multiple nodes that could act as roots? – brain storm Dec 13 '13 at 02:13
  • `#1` Makes sense, this is typically how [adjacency lists](http://en.wikipedia.org/wiki/Adjacency_list) work, which is mostly used in graph implementations. `#2` Yes, I believe you can also use DFS, no particular reason for picking BFS. `#3` Yes. Yes, in many cases multiple nodes could act as the root. – Bernhard Barker Dec 13 '13 at 02:41
  • One other point is that we should consider if graph is connected or not. If it is not connected, even having n - 1 edges and no cycle, still does not necessarily mean that graph is a tree and it can be a forest. Just wanted to mention that sometimes we may need to check the number of connected components in graph to be sure that graph is connected. – Pedram Nov 06 '17 at 03:44
  • @Pedram: Should correct myself, ....."even having no cycle, still does not necessarily mean that graph is a tree and it can be a forest....." – Pedram Nov 06 '17 at 03:50
  • @Pedram Edited. – Bernhard Barker Nov 06 '17 at 14:16
  • For directed graph 1: I would say "No incoming edges"; since the trivial tree with only one node has no edges at all. "Only outgoing edges" is less clear for that case. – Hans Olsson May 07 '20 at 07:48
0

If an undirected given graph is a tree:

  • the graph is connected
  • the number of edges equals the number of nodes - 1.
weiyixie
  • 551
  • 5
  • 6
0

I can add that, in case of oriented graph where each node has at most one parent, if you already know that there is only one root, instead of implementing DFS (Depth First Search) you can:

  1. find that specific root,
  2. write a recursion that: -saves all visited nodes, -returns when it reach a leaf (node with no children), -when it reach a node that is not a leaf iterate through all children of that node (recursively).

If it's connected (all nodes have been visited) and has #(edges) = #(nodes) - 1 then its a tree If every node is at most 3-valent, then it's a binary tree.

If visited nodes are all nodes of a graph, then it is connected. If it's connected then

Piotr Michalak
  • 1
  • 1
  • As it’s currently written, your answer is unclear. Please [edit] to add additional details that will help others understand how this addresses the question asked. You can find more information on how to write good answers [in the help center](/help/how-to-answer). – Community Aug 16 '23 at 14:40
-1

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.
Joe
  • 326
  • 3
  • 11