Dynamic Programming -- Independent sets in tree

Let's talk about algorithms!

Moderator: Board moderators

Post Reply
Rinoaheartilly
New poster
Posts: 9
Joined: Thu Oct 14, 2004 6:37 am
Location: North Carolina

Dynamic Programming -- Independent sets in tree

Post by Rinoaheartilly »

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

Code: Select all

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.
marcadian
New poster
Posts: 45
Joined: Sun Jun 26, 2005 6:21 am
Contact:

Re: Dynamic Programming -- Independent sets in tree

Post by marcadian »

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)
}
Post Reply

Return to “Algorithms”