Counting trees in a graph

Question

I would like to know how to modify DFS/BFS in order to return the number of the trees present in a graph. I know that a tree is an acyclic connected graph, and I think that I have to initialize a counter somewhere, but I don't know where. I made the procedure "is-tree(G)" where G is the graph. It returns true if the subprocedure "is-connected(G)" also returns true and if the number of the arcs in G = number of nodes in G - 1, otherwise the procedure returns false. At this point I don't know how to count all the possibile subgraphs which are also trees.

Answer 1

One way to approach the problem is through Euler Tour for Trees and hashing.

1. For each node in the graph:

   1.1 Perform DFS starting from this node. Store all encountered nodes in the Euler Tour Tree format ( eg., while moving from say node 3 to node 1, you add an entry [ 3 - 1 ], but dont add nodes while backtracking ) . Let's denote this by set 'S'.

   1.2 Sort 'S' and compute a unique hash for the set. If the hash has already been seen before, then ignore the set and go back to 1. . Else go to 1.3. (This step is to make sure that you are not counting isomorphic trees multiple times.)

   1.3 If size of the set(S) = N, number of subtrees = N * (N+1) / 2;

2. Sum all the number of subtrees obtained in step 1.

Answer 2

So here is a pseudo code of what i proposed. Maybe i was not clear.

1) Start with a node (Your start node)

2) For each node from root node, try to find a node (if it exists) that has atleast one node that is not visited. (If the graph is a cyclic, this condition is true). To do this, you may use a hashset of visited children for each iteration.

3) do the above till you reach a node which has no children. Thats the end of the algo where you found 1 tree in the graph. For back tracking i think you want to maintain a hashmap of all the nodes that you started with and the value field contains all the connected nodes to the graph. The point you reach a leaf node without violating point(2), you start back tracking to find the parent of the current node; ie the leaf node to the start node.

Thats your subgraph which is a tree.

PS- Leaf node in this case would be a node which has no nodes connected to it/all the other nodes connected to it are already visited previously/only inward connections

Answer 3

So for each node in the graph, initially treat it as a n-ary tree, where it contains the following class node{ int val; List<node> = [List of all connected nodes] }

Since you are doing BFS/DFS, you are sure to visit every node. - For each node Check if the nodes in the above list has a leaf node. - Keep a backtracking mechanism (using a map or any other data structure) which
links to the root from where you started. Thats your Tree inside the graph. Repeat it till all nodes are visited while updating the count when you get a tree.