Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I have a non-binary tree.
I want to find all "sub-trees" that are connected to root.

Sub-tree is a a link group of tree nodes.

enter image description here

every group is colored in it's own color.

What would be be the best approach? Run recursion down and up for every node?

The data structure of every treenode is a list of children, list of parents. (the type of children and parents are treenodes)

Clarification:

Group defined if there is a kind of "closure" between nodes where root itself is not part of the closure.
As you can see from the graph you can't travel from pink to other nodes (you CAN NOT use root).
From brown node you can travel to it's child so this form another group.

Finally you can travel from any cyan node to other cyan nodes so the form another group

share|improve this question
    
Are you looking for just the child trees of the root, or all descendents? –  AndyBursh Jan 10 '12 at 9:59
    
yes,child trees of the root –  kenny Jan 10 '12 at 10:50
1  
Kenny, please add any clarifications to the question itself (edit & update) and not in comments. –  Yannis Rizos Jan 10 '12 at 12:22
9  
The thing in the picture is not a tree. Tree ≡ graph without circles. Your graph has circles (if it didn't the answer would have been trivial). –  Jan Hudec Jan 10 '12 at 12:50
2  
So what you want is connected components after removal of root. Well, that should give you the algorithm. –  Jan Hudec Jan 10 '12 at 12:58

1 Answer 1

You could use a BFS algorithm (a graph algorithm explained on Wikipedia), starting from the node you want to make root.

The algorith behaves like this:

procedure BFS(G,v,btree):
      create a queue Q
      enqueue v onto Q
      mark v
      btree = new Tree(v);//Create a tree structure with v as root
      while Q is not empty:
          t ← Q.dequeue()
          btree.add(t) // Here its where you add elements to your tree
          for all edges e in G.incidentEdges(t) do
             o ← G.opposite(t,e)
             if o is not marked:
                  mark o
                  enqueue o onto Q

When Q is empty means you processed all the possible nodes and all of them have been added to your binary tree (btree).

Once you have your btree you can apply any simple algorithm to obtain what you need

share|improve this answer
    
What exactly do you mean by Graph.opposite(Vertex, Edge): Vertex? –  Jan Hudec Jan 10 '12 at 14:50
    
@Jan_Hudec The node in the other side of the edge. I mean, each vertex has two sides, the one your are standing and the one you are not ( lets imagine its not an edge to ourself) Edge y --- Vertex ---- Edge o , so that way you have the vertex on the "opposite" side of the edge –  guiman Jan 10 '12 at 14:57
    
An, normally I'd just either say e.second, or for all u: (t, u) in E(G). Anyway. –  Jan Hudec Jan 10 '12 at 15:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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