Author |
Topic: SubGraph with sum x (Read 6203 times) |
|
A
Full Member
Perder todas as esperanças é liberdade!
Gender: 
Posts: 236
|
 |
SubGraph with sum x
« on: Feb 9th, 2012, 1:51am » |
 Quote  Modify
|
Given a connected undirected graph , print all possible connected undirected sub graphs, such that nodes sum upto x
Below is the example with binary tree
.....................7...........................
............4.......................-4..........
.......3........2.............4...........3....
.....*...1...*...1......*.....*....*........*
Possible Sub Graphs are for x = 7 are:
7
.....................7...........................
4, 3
............4..................................
.......3.......................................
................................................
4 2 1
............4...................................
................2..............................
...................1............................
4 3 1 (edit)
4 7 -4
7, 4 ,-4
and so on
|
| « Last Edit: Feb 9th, 2012, 7:54am by A » |
 IP Logged |
What Doesn't Kill Me Will Only Make Me Stronger
|
|
|
A
Full Member
Perder todas as esperanças é liberdade!
Gender:
Posts: 236
|
|
Re: SubGraph with sum x
« Reply #1 on: Feb 9th, 2012, 1:53am » |
Quote Modify
|
So there are these problems
1) Given a binary tree, find path such that root to leaf is x
2) root to non leaf is x .
I was wondering if same could be extended with good time complexity
|
|
IP Logged |
What Doesn't Kill Me Will Only Make Me Stronger
|
|
|
A
Full Member
Perder todas as esperanças é liberdade!
Gender:
Posts: 236
|
|
Re: SubGraph with sum x
« Reply #2 on: Feb 9th, 2012, 8:07am » |
Quote Modify
|
To start with, for a binary tree
Code:
findSumX (root, x) {
if (root != NULL ) {
tx = x - root->data;
if ( tx == 0) {
'found one path'
}
findpathConnected(root->left, tx);
findpathConnected(root->right, tx);
findpath(root->left,x);
findpath(root->right,x);
}
findpathConnected(root, x) {
if(root != NULL) {
x = x - root->data;
if ( x == 0) {
'found one path'
}
findpathConnected(root->left,x);
findpathConnected(root->right,x);
}
|
|
EDIT:
* Basically root to any node sum = x algorithm for every node in the tree.
* Complexity seems to be O(n^2) in average case 
* Does find path only either in left subtree or in right subtree. 
|
| « Last Edit: Feb 9th, 2012, 8:11am by A » |
IP Logged |
What Doesn't Kill Me Will Only Make Me Stronger
|
|
|
A
Full Member
Perder todas as esperanças é liberdade!
Gender:
Posts: 236
|
|
Re: SubGraph with sum x
« Reply #3 on: May 1st, 2012, 4:46am » |
Quote Modify
|
Is the question or the example s above not clear or the question is boring/difficult to solve in reasonable time.
I have been trying to solve this for a while. Every approach i try ends in O(n^2). Is there a better solution.
|
|
IP Logged |
What Doesn't Kill Me Will Only Make Me Stronger
|
|
|
birbal
Full Member
Gender:
Posts: 250
|
|
Re: SubGraph with sum x
« Reply #4 on: Dec 23rd, 2012, 10:14am » |
Quote Modify
|
on May 1st, 2012, 4:46am, R0B1N wrote:Is the question or the example s above not clear or the question is boring/difficult to solve in reasonable time.
I have been trying to solve this for a while. Every approach i try ends in O(n^2). Is there a better solution.
|
|
It can be done in one DFS with O(log n) extra memory. Do a inorder traversal and use a stack to push the elements. On every left/non-leaf check if we got the required sum and just print the stack.
Makes sense ?
|
|
IP Logged |
The only thing we have to fear is fear itself!
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print