Wednesday, March 2, 2011

WAP to Find path in a tree represented with NXN array

I have an MST(anyway a tree..) represented with a NXN array.
I want to find the path between 2 nodes source, destination (or sensor, sink in WSN).


/*
given a MST graph[N][N]
we find the path from a node to the root
*/
#include
#define N 4

int main(){
int graph[N][N]={{0,1,1,0},
{1,0,0,1},
{1,0,0,0},
{0,1,0,0},
};
int leaves[N];
int i,j;
int count;
//initialize
for( i=0; i //find which nodes are leaves
for(i=0; i count=0;
for( j=0; j if (graph[i][j]==1) count++;
if (count>1) {leaves[i]=0;break;}
}
}
for( i=0;i printf("%d ",leaves[i]);
printf("\n");

int path[N];
for( i=0;i path[i]=-1;
int path_index=0;
int a=3,sink=0;//two nodes
int cur=a;
path[path_index]=a;
path_index++;
int parent=-1;
while(parent!=sink){//while destination not found
printf("parent=%d",parent);getchar();printf("\ncur: %d",cur);getchar();
for(j=0;j {
if (graph[cur][j]==1 && leaves[cur]==1){
parent=j;path[path_index]=parent;path_index++;
if (parent==sink) break;
printf("\ncur: %d",cur);getchar();
printf("parent: %d ",parent);
}
if (graph[cur][j]==1&& !(leaves[j])){
parent=j;path[path_index]=parent;path_index++;
if (parent==sink) break;
printf("\ncur: %d",cur);getchar();
printf("parent: %d ",parent);
}

}
cur=parent;

}
for(i=0;i if (path[i]!=sink) printf("%d--> ",path[i]);
else break;
}

getchar();
return 0;
}

1 comment :

Nope said...

A minimum spanning tree is defined for a graph . There is no concept of root and/or leaf in a MST . Different configurations can give different roots .Plus the way you are selecting the leaves is also wrong (with the use of count) .You could as well describe the method instead of just the code , which is also very poortly formatted . I had to inspect the html tags to find the clear code .Blogger has an option for displaying codes

And lastly , I think a BFS/DFS will suffice , The DFS will be faster as we only need *any* path through the nodes .