ቢ.ኤፍ.ኤፍስን በመጠቀም በአንድ ዛፍ ውስጥ በተሰጠ ደረጃ የአንጓዎችን ቁጥር ይቁጠሩ


የችግር ደረጃ ቀላል
ውስጥ በተደጋጋሚ ተጠየቀ የመርጨት ባንክ ባዛር ጂፒ ሞርጋን አራት ማዕዘን ታክሲ 4 ዋስትና
ስፌት የመጀመሪያ ፍለጋ ግራፍ ዛፍ የዛፍ ተሻጋሪ

መግለጫ

ችግሩ “ቢኤፍኤፍስን በመጠቀም በአንድ ዛፍ ውስጥ በተሰጡት ደረጃዎች የአንጓዎችን ቁጥር ይቁጠሩ” የሚለው ዛፍ (አሲሲሊክ ግራፍ) እና የስር መስቀለኛ መንገድ ይሰጥዎታል ፣ በ L ኛ ደረጃ የሚገኙ የአንጓዎችን ቁጥር ይወቁ ፡፡

Acyclic Graph: እሱ የተዘጋ ዑደት በሌለው ጠርዞች በኩል የተገናኙ የአንጓዎች አውታረመረብ ነው።

ማስታወሻ: የስር መስቀለኛ መንገድ እራሱ በዛፉ 1 ኛ ደረጃ ላይ ይገኛል ፡፡

ለምሳሌ

በመስቀለኛ መንገድ 0 ላይ የተመሠረተውን ከዚህ በታች የተሰጠውን ዛፍ ተመልከት ፡፡

ቢ.ኤፍ.ኤፍስን በመጠቀም በአንድ ዛፍ ውስጥ በተሰጠ ደረጃ የአንጓዎችን ቁጥር ይቁጠሩ

በ 2 ኛ ደረጃ ላይ የአንጓዎች ብዛት = 3

ማስረጃ

ቢ.ኤፍ.ኤፍስን በመጠቀም በአንድ ዛፍ ውስጥ በተሰጠ ደረጃ የአንጓዎችን ቁጥር ይቁጠሩ

ስፌት የመጀመሪያ ፍለጋ

ቀረበ

ሀሳቡ ማከናወን ነው BFS ከስር መስቀለኛ መንገድ ጀምሮ እና በመንገዱ ላይ የእያንዳንዱ መስቀለኛ ደረጃ ዋጋን መከታተል። የስር መስቀለኛ መንገድ በ 1 ኛ ደረጃ ላይ ነው ፡፡ የልጆች አንጓዎች ደረጃ የወላጅ መስቀለኛ መንገድ + 1. ዘ ተራ በዛፉ ውስጥ ላሉት እያንዳንዱ መስቀሎች በቢኤፍኤፍኤስ ማቋረጫ መደብሮች ወቅት አንጓዎችን ለማስኬድ ይጠቀሙ {node.value, node.level} ፡፡

አልጎሪዝም

  1. እስቲ አስቡ ፣ የዛፍ ግራፍ ከደረጃ ጋር አብሮ ይሰጣል 'ኤል'.
  2. በቢኤፍኤስ ማቋረጥ ወቅት የመስቀለኛ እሴት እና የመስቀለኛ ደረጃን እንደ ጥንድ የሚያከማች የ BFS ወረፋ ይፍጠሩ ፡፡
  3. ፍጠር የሃሽ ካርታ በእያንዳንዱ ደረጃ የሚገኙትን የአንጓዎች ብዛት ያከማቻል ፡፡
  4. ከ BFS ወረፋው ጋር ካለው ደረጃ ጋር የስር መስቀለኛ መንገዱን ከጨመሩ በኋላ ተራ በተራ ቢኤፍኤስ ማቋረጥ ይጀምሩ።
  5. በእያንዲንደ የእግረኛ መንገዴ በሚ Duringረግበት ጊዜ መስቀለኛ ቦታ ብቅ ይበሉ ፊት & እሱ ከወረፋው ደረጃ ነው።
  6. እንደተጎበኘው ብቅ ያለውን መስቀለኛ መንገድ ምልክት ያድርጉ ፡፡
  7. በዚያ በተወሰነ ደረጃ የአንጓዎችን ቁጥር በ 1 ይጨምሩ።
  8. ያልታዩ የጎብኝዎች ጎብኝዎችን ጎብኝዎች ፣ እያንዳንዱን መስቀለኛ መንገድ ከደረጃው ጋር ወደ ወረፋ ያስገቡ [ማለትም (ደረጃ ፊትለፊት) + 1]።
  9. የቢ.ኤስ.ኤፍ. መተላለፊያው ካለቀ በኋላ በዛፉ ውስጥ በተጠቀሰው ደረጃ የጠቅላላውን የአንጓዎች ብዛት ይመልሱ ፡፡

ቢ.ኤፍ.ኤፍስን በመጠቀም በአንድ ዛፍ ውስጥ በተሰጠ ደረጃ የአንጓዎችን ቁጥር ይቁጠሩ

 

ኮድ

ቢ.ኤፍ.ኤፍ. በመጠቀም በዛፍ ውስጥ በተሰጠው ደረጃ የአንጓዎችን ቁጥር ለመቁጠር የ C ++ ፕሮግራም

#include <iostream>
#include <bits/stdc++.h>
using namespace std;

// function to add undirected edge between two nodes
void addEdge(vector <int> graph[], int u, int v)
{
    graph[u].push_back(v);
    graph[v].push_back(u);
}

// count nodes at particular level in the tree
int countNodes(int root, vector <int> graph[], int level, int n)
{
    // mark all the nodes unvisited
    vector <bool> visited(n,false);
    // to store mapping between level->number of nodes
    unordered_map<int,int> um;
    
    // BFS queue
    // stores {node value, node level}
    queue <pair<int,int>> q;
    // root is at first level
    int L = 1;
    // push root into queue
    q.push({root,L});
    
    // Perform BFS traversal
    // Traverse each node and find their level in the tree
    while(!q.empty())
    {
        auto front = q.front();
        q.pop();
        
        visited[front.first] = true;
        // Increase number of nodes at that level by 1
        um[front.second]++;
        
        // Visit all the neighbor nodes of the popped node
        for(auto node : graph[front.first])
        {
            if(!visited[node])
                q.push({node,front.second+1});
        }
    }
    
    // return number of nodes at 'level'
    return um[level];
}

int main()
{
    // define number of nodes & root node
    int n = 7;
    int root = 0;
    
    // construct the graph & link the nodes by edges
    vector <int> graph[n];
    vector <pair<int,int>> edges = {{0,1},{0,2},{0,3},{1,4},{1,5},{4,6}};
    for(auto e : edges)
    addEdge(graph,e.first,e.second);
    
    // define level
    int L = 2;
    cout<<"Number of Nodes at 2nd Level = "<<countNodes(root,graph,L,n)<<endl;
    
    return 0;
}
Number of Nodes at 2nd Level = 3

የጃቫ ፕሮግራም ቢ.ኤፍ.ኤፍስን በመጠቀም በአንድ ዛፍ ውስጥ በተሰጠ ደረጃ የአንጓዎችን ቁጥር ለመቁጠር

import java.util.*;
import java.io.*;

class TutorialCup
{
    // class definition to handle pairs
    static class pair
    {
        int first,second;
        pair(int u,int v)
        {
            first = u;
            second = v;
        }
    }
    // function to add undirected edge between two nodes
    static void addEdge(ArrayList<ArrayList<Integer>> graph, int u, int v)
    {
        graph.get(u).add(v);
        graph.get(v).add(u);
    }
    
    // count nodes at particular level in the tree
    static int countNodes(int root, ArrayList<ArrayList<Integer>> graph, int level, int n)
    {
        // mark all the nodes unvisited
        boolean [] visited = new boolean[n];
        // to store mapping between level->number of nodes
        HashMap<Integer,Integer> um = new HashMap<>();
        
        // BFS queue
        // stores {node value, node level}
        Queue <pair> q = new LinkedList<>();
        // root is at first level
        int L = 1;
        // push root into queue
        q.add(new pair(root,L));
        
        // Perform BFS traversal
        // Traverse each node and find their level in the tree
        while(!q.isEmpty())
        {
            pair front = q.poll();
            visited[front.first] = true;
            
            // Increase number of nodes at that level by 1
            if(um.containsKey(front.second))
            um.put(front.second, um.get(front.second)+1);
            else
            um.put(front.second, 1);
            
            Iterator itr  = graph.get(front.first).iterator();
            // Visit all the neighbor nodes of the popped node
            while(itr.hasNext())
            {
                int node = (Integer)itr.next();
                if(visited[node] == false)
                    q.add(new pair(node,front.second+1));
            }
        }
        
        // return number of nodes at 'level'
        return um.get(level);
    }
    
    public static void main (String[] args)
    {
        // define number of nodes & root node
        int n = 7;
        int root = 0;
        
        // construct the graph & link the nodes by edges
        ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
        
        for(int i=0;i<n;i++)
        graph.add(new ArrayList<Integer>());
        
        int [][] edges = {{0,1},{0,2},{0,3},{1,4},{1,5},{4,6}};
        
        for(int i=0; i<edges.length; i++)
        addEdge(graph,edges[i][0],edges[i][1]);
        
        // define level
        int L = 2;
        System.out.println("Number of Nodes at 2nd Level = "+countNodes(root,graph,L,n));
    }
}
Number of Nodes at 2nd Level = 3

ውስብስብነት ትንተና

  1. የጊዜ ውስብስብነትT (n) = ኦ (V + E)
  2. የቦታ ውስብስብነትA (n) = O (V) ፣ ጥቅም ላይ ለሚውለው የ BFS ወረፋ ፡፡

ወረፋ ስለተጠቀምን እና በሁሉም መስቀሎች ላይ ስናልፍ አልጎሪዝም ስልታዊ በሆነ ጊዜ ይሠራል። አልጎሪዝም መስመራዊ የጊዜ ውስብስብነት አለው። በሁሉም አንጓዎች ላይ ለማቋረጥ ወረፋ እንደተጠቀምን ፣ በጣም የከፋ የቦታ ውስብስብነት N ይሆናል ፣ ስለሆነም የመስመር ክፍተት ውስብስብ ነው።

V = በዛፉ ውስጥ የአንጓዎች ብዛት

E = በመስቀለኛ ክፍል ውስጥ የጠርዙ ብዛት