Want to protect your cyber security and still get fast solutions? Ask a secure question today.Go Premium

x
?
Solved

Find path in a tree represented with NXN array, C code

Posted on 2009-12-28
2
Medium Priority
?
379 Views
Last Modified: 2012-05-08
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).
I have written some code, but I want something more efficient and not so "naive"...
thanks!
/*
given a MST graph[N][N]
we find the path from a node to the root
*/
#include<stdio.h>
#define N 7

int main(){
    int graph[N][N]={{0,1,1,0,0,0,0},
                     {1,0,0,1,0,0,0},
                     {1,0,0,0,1,1,0},
                     {0,1,0,0,0,0,0},
                     {0,0,1,0,0,0,0},
                     {0,0,1,0,0,0,1},
                     {0,0,0,0,0,1,0}
                     };
    int leaves[N];
    int isLeaf,count;
    //initialize
    for(int i=0; i<N;i++) leaves[i]=1;
    //find which nodes are leaves
    for(int i=0; i<N; i++){
        count=0;
        for(int j=0; j<N; j++){//check line j
                if (graph[i][j]==1) count++;
                if (count>1) {leaves[i]=0;break;}
        }
    }
    for(int i=0;i<N;i++)
      printf("%d ",leaves[i]);
    printf("\n");
    
    int path[N];
    for(int i=0;i<N;i++)
            path[N]=-1;
    int path_index=0;  
    int a=6,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(int j=0;j<N;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(int i=0;i<N;i++){
            if (path[i]!=sink) printf("%d--> ",path[i]);
            else break;
    }
       
    getchar();
    return 0;
}

Open in new window

0
Comment
Question by:xiromdim
2 Comments
 
LVL 53

Accepted Solution

by:
Infinity08 earned 2000 total points
ID: 26130384
The code as you have it now won't work in the general case. In your inner for loop, you identify two cases :

1) the current node is a leaf : there's only one way to go, so that's handled right

2) the current node is not leading to a leaf : there's more than one way to go, but you forgot a few important things :
        (a) ignore the path leading back to the parent node
        (b) make sure to investigate ALL paths completely, and not just the first step

Although the path your code will find (in your example case) is not 100% correct, it will seem to work - but that's just by chance. Try different (longer eg.) paths and see what happens.


If you want an exhaustive search of the BST, you need to make sure to check all paths.


An alternative approach could be to "trim" the branches of the tree. ie. cut off all leaves (mark them as not part of the path), except if they are either the source or destination node. Repeat until no more leaves can be cut off, and the remaining nodes should be the path you want.
Properly keep track of cut off nodes when doing this.
If you don't see how this would work, try drawing a tree on a piece of paper, and then mark any two nodes (source and destination). Then start cutting off leaves (cross them out), until you can cut no more. The only branches that should still be left are those that form the path between source and destination.
0
 

Author Comment

by:xiromdim
ID: 26134479
ok, I fixed it, with yours advice, although there is some redundant code.
/*
given a MST graph[N][N]
we find the path from a node to the root
*/
#include<stdio.h>
#define N 11

int main(){
    int graph[N][N]={//    0 1 2 3 4 5 6 7 8 9 10
                     /*0*/{0,1,1,0,0,0,0,0,0,0,1},
                     /*1*/{1,0,0,1,0,0,0,0,0,0,0},
                     /*2*/{1,0,0,0,1,1,0,0,0,1,0},
                     /*3*/{0,1,0,0,0,0,0,0,0,0,0},
                     /*4*/{0,0,1,0,0,0,0,0,0,0,0},
                     /*5*/{0,0,1,0,0,0,1,1,0,0,0},
                     /*6*/{0,0,0,0,0,1,0,0,1,0,0},
                     /*7*/{0,0,0,0,0,1,0,0,0,0,0},
                     /*8*/{0,0,0,0,0,0,1,0,0,0,0},
                     /*9*/{0,0,1,0,0,0,0,0,0,0,0},
                    /*10*/{1,0,0,0,0,0,0,0,0,0,0}
                     };
    int leaves[N];
    int isLeaf,count;
    //initialize
    for(int i=0; i<N;i++) leaves[i]=1;
    //find which nodes are leaves
    for(int i=0; i<N; i++){
        count=0;
        for(int j=0; j<N; j++){//check line j
                if (graph[i][j]==1) count++;
                if (count>1) {leaves[i]=0;break;}
        }
    }
    for(int i=0;i<N;i++)
      printf("%d ",leaves[i]);
    printf("\n");
    
    int path[N];
    for(int i=0;i<N;i++)
            path[N]=-1;
    int path_index=0;  
    int a=6,sink=2;//two nodes
    int cur=a;
    path[path_index]=a;
    path_index++;
    int parent=-1;
    while(parent!=sink){//while destination not found
         
         for(int j=0;j<N;j++){
                 if (graph[cur][j]==1 && leaves[cur]==1){//is a leaf, only for the source node
                     printf("%d is a leaf\n",cur);
                     parent=j;
                     printf("parents changes...");
                     printf("parent=%d",parent);
                     printf("\ncur: %d",cur);getchar();
                     if (parent==sink) break;
                     break;
                     }
                     else if (graph[cur][j]==1&& !(leaves[j])){//is inetrmediate node
                     printf("%d is NOT a leaf\n",j);
                     parent=j;
                     printf("parents changes...");
                     printf("parent=%d",parent);
                     printf("\ncur: %d",cur);getchar();
                     if (parent==sink) break;
                     break;
                     
                 }
         }
         cur=parent;
         path[path_index]=parent;
         path_index++;
         printf("parent=%d",parent);
         printf("\ncur: %d",cur);getchar();
         printf("loop ends...\n\n");
               
    }            
    path[path_index]=sink;
    for(int i=0;i<path_index;i++){
            if (path[i]!=sink)
             printf("%d--> ",path[i]);
            else printf("%d\n",path[i]);
    } 
    
    getchar();
    return 0;
}      

Open in new window

0

Featured Post

Technology Partners: We Want Your Opinion!

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Preface I don't like visual development tools that are supposed to write a program for me. Even if it is Xcode and I can use Interface Builder. Yes, it is a perfect tool and has helped me a lot, mainly, in the beginning, when my programs were small…
Summary: This tutorial covers some basics of pointer, pointer arithmetic and function pointer. What is a pointer: A pointer is a variable which holds an address. This address might be address of another variable/address of devices/address of fu…
The goal of this video is to provide viewers with basic examples to understand how to use strings and some functions related to them in the C programming language.
The goal of this video is to provide viewers with basic examples to understand how to create, access, and change arrays in the C programming language.

577 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question