how to determine the level of each node in the given tree 3f

Solutions on MaxInterview for how to determine the level of each node in the given tree 3f by the best coders in the world

showing results for - "how to determine the level of each node in the given tree 3f"
Carlene
29 May 2017
1void bfs (int start)
2{
3            deque <int > Q;     //Double-ended queue
4            Q.push_back( start); 
5            distance[ start ] = 0;       
6            while( !Q.empty ())
7            {
8                int v = Q.front( );
9                Q.pop_front(); 
10                for( int i = 0 ; i < edges[v].size(); i++)
11               {
12
13
14/* if distance of neighbour of v from start node is greater than sum of distance of v from start node and edge weight between v and its neighbour (distance between v and its neighbour of v) ,then change it */  
15
16
17                    if(distance[ edges[ v ][ i ].first ] > distance[ v ] + edges[ v ][ i ].second ) 
18                {
19
20                    distance[ edges[ v ][ i ].first ] = distance[ v ] + edges[ v ][ i ].second;
21
22                /*if edge weight between v and its neighbour is 0 then push it to front of
23        double ended queue else push it to back*/
24
25                    if(edges[ v ][ i ].second == 0)
26                    {
27                        Q.push_front( edges[ v ][ i ].first);
28                    }
29                    else
30                    {
31                            Q.push_back( edges[ v ][ i ].first);
32
33                    }
34                }
35              }
36           }
37    }
Ailsa
09 Jul 2018
1   vector <int> v[10] ;   //Vector for maintaining adjacency list explained above
2    int level[10]; //To determine the level of each node
3    bool vis[10]; //Mark the node if visited 
4    void bfs(int s) {
5        queue <int> q;
6        q.push(s);
7        level[ s ] = 0 ;  //Setting the level of the source node as 0
8        vis[ s ] = true;
9        while(!q.empty())
10        {
11            int p = q.front();
12            q.pop();
13            for(int i = 0;i < v[ p ].size() ; i++)
14            {
15                if(vis[ v[ p ][ i ] ] == false)
16                {
17            //Setting the level of each node with an increment in the level of parent node
18                    level[ v[ p ][ i ] ] = level[ p ]+1;                 
19                     q.push(v[ p ][ i ]);
20                     vis[ v[ p ][ i ] ] = true;
21      }
22            }
23        }
24    }
Mattia
10 Oct 2018
1          node                            level [node]   
2
3              s (source node)               0  
4              1                            1  
5              2                            1  
6              3                            2  
7              4                            2  
8              5                            2  
9              6                            2  
10              7                            3 
similar questions