OJ Board

Posted: **Sat Oct 04, 2008 3:57 am**

I having a problem of representing my tree. Please help!!
Let look at a graph

0----1---
|        |----4----5    
2----3---

1 connect to 4, 4 connect to 5
3 connect to 4, 4 connect to 5
If we represent this to a tree with 0 is the root then
0. 1 2
1. 4
2. 3
3. 4
4. 5
1 and 2 are the children of 0. 4 is the child of . 3 is the child of 2 and so on. Keep in mind that we can have more than 2 children (not a binary tree). So I represent this tree using adjacency list. My question is, with this same data, how do I make a tree root 1, more general., picking a number, how do I make a tree with that number is a root. What data structure do I use? I am not even sure how do I construct the input data to represent that graph above.

Posted: **Tue Oct 07, 2008 5:01 pm**

represent tree as undirected, but traverse as directed
0. 1 2
1. 0 4
2. 0 3
3. 2 4
4. 1 3 5
5. 4

Code: Select all

dfs(node,parent)
{
    foreach ( v adjacent to node)
        if (v!=parent) dfs(v)
}

OJ Board

Dynamic Programming -- Independent sets in tree

Dynamic Programming -- Independent sets in tree

Re: Dynamic Programming -- Independent sets in tree