2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Perhaps you should give it a few more days. $\endgroup$ – Yuval Filmus Jan 18 '17 at 21:23
  • $\begingroup$ Find cicles, remove all nodes that are in the cicles. Then count trees starting from a leaf for each Island. Keep in mind that number of trees grow very fast. a "V" (with 3 nodes) has 6 trees! You should define more precisely what trees are because it is likely you will run out quickly of 64 bit integer field even for modestly sized graphs. $\endgroup$ – GameDeveloper Jan 19 '17 at 23:08
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$
-2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ I'm sorry but I don't understand this at all. What do you mean by "check if the nodes in the above list has a leaf node"? A leaf in what? How do I determine that? How do you propose to manage backtracking? What's the relevance of linking to the root? Why do you need to visit every node? The question doesn't ask about spanning trees. $\endgroup$ – David Richerby Jan 18 '17 at 20:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.