How to determine if a given directed graph is a tree
algorithm, directed-graph, tree
Solution
Here's a fairly direct method. It can be done with either an adjacency matrix or an edge list.
Find the set, R, of nodes that do not appear as the destination of any edge. If R does not have exactly one member, the graph is not a tree.
If R does have exactly one member, r, it is the only possible root.
Mark r.
Starting from r, recursively mark all nodes that can be reached by following edges from source to destination. If any node is already marked, there is a cycle and the graph is not a tree. (This step is the same as a previously posted answer).
If any node is not marked at the end of step 3, the graph is not a tree.
If none of those steps find that the graph is not a tree, the graph is a tree with r as root.
It's difficult to know what is going to be efficient without some information about the numbers of nodes and edges.
Problem
The input to the program is the set of edges in the graph. For e.g. consider the following simple directed graph: ``` a -> b -> c ``` The set of edges for this graph is ``` { (b, c), (a, b) } ``` So given a directed graph as a set of edges, how do you determine if the directed graph is a tree? If it is a tree, what is the root node of the tree? First of I'm looking at how will you represent this graph, adjacency list/ adjacency matrix / any thing else? How will utilize the representation that you have chosen to efficiently answer the above questions? Edit 1: Some people are mentoning about using DFS for cycle detection but the problem is which node to start the DFS from. Since it is a directed graph we cannot start the DFS from a random node, for e.g. if I started a DFS from vertex 'c' it won't proceed further since there is no back edge to go to any other nodes. The follow up question here should be how do you determine what is the root of this tree.