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.
Counting trees in a graph
algorithms;graphs
One way to approach the problem is through Euler Tour for Trees and hashing.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;Sum all the number of subtrees obtained in step 1.