CODEWITHSUNDEEP
algorithmgraphtree
brain storm
brain storm

Reputation: 31252

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

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?

Upvotes: 22

Views: 36592

Answers (4)

Piotr Michalak
Piotr Michalak

Reputation: 1

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

Upvotes: 0

Bernhard Barker
Bernhard Barker

Reputation: 55609

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.

Upvotes: 43

Joe
Joe

Reputation: 392

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.

Upvotes: -1

weiyixie
weiyixie

Reputation: 581

If an undirected given graph is a tree:

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

Upvotes: 0

Related Questions