ספר את מספר הצמתים ברמה הנתונה בעץ באמצעות BFS


רמת קושי קַל
נשאל לעתים קרובות אלציה בנק בזאר JP מורגן בצורת ריבוע Taxi4Sure
רוחב החיפוש הראשון גרף עֵץ מעבר עץ

תיאור

הבעיה "ספר את מספר הצמתים ברמה נתונה בעץ באמצעות BFS" קובעת שאתה מקבל עץ (גרף אציצי) וצומת שורש, גלה את מספר הצמתים ברמה החמישית.

גרף מחזורי: זוהי רשת של צמתים המחוברים בקצוות ללא לולאה סגורה.

הערה: צומת השורש עצמו נמצא ברמה הראשונה בעץ.

דוגמה

שקול את העץ המופיע למטה, מושרש בצומת 0.

ספר את מספר הצמתים ברמה הנתונה בעץ באמצעות BFS

מספר הצמתים ברמה השנייה = 2

הסבר

ספר את מספר הצמתים ברמה הנתונה בעץ באמצעות BFS

רוחב החיפוש הראשון

גישה

הרעיון הוא לבצע BFS החל מצומת שורש ולעקוב אחר ערך הרמה של כל צומת לאורך הנתיב. צומת השורש נמצא ברמה הראשונה. רמת צמתי הילדים תהיה ברמת צומת ההורה + 1. תור השתמשו לעיבוד צמתים במהלך חנות מעבר BFS {node.value, node.level} כצמד לכל צומת בעץ.

אַלגוֹרִיתְם

  1. קחו בחשבון, גרף עץ ניתן יחד עם הרמה 'L'.
  2. צור תור BFS המאחסן את ערך הצומת ורמת הצומת כזוג במהלך חציית BFS.
  3. צור מפת גיבוב המאחסן את מספר הצמתים הקיימים בכל רמה.
  4. התחל מעבר BFS איטרטיבי לאחר הוספת צומת השורש יחד עם הרמה לתור BFS.
  5. במהלך כל איטרציה של המעבר, פתח צומת חזית & זה ברמה מהתור.
  6. סמן את הצומת שהוצץ כביקור
  7. הגדל את מספר הצמתים ברמה מסוימת זו ב -1.
  8. בקר בכל אחד מהשכנים שלא ביקרו בצומת שצץ, הכנס כל צומת לתור יחד עם הרמה שלו [כלומר (רמת חֲזִית) + 1].
  9. לאחר סיום מעבר BFS, החזר את המספר הכולל של הצמתים ברמה הנתונה בעץ.

ספר את מספר הצמתים ברמה הנתונה בעץ באמצעות BFS

 

קופונים

תוכנית C ++ לספירת מספר הצמתים ברמה נתונה בעץ באמצעות BFS

#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

תוכנית Java לספירת מספר הצמתים ברמה נתונה בעץ באמצעות BFS

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) = O (V + E)
  2. מורכבות בחלל: A (n) = O (V), עבור התור BFS בשימוש.

האלגוריתם פועל בזמן ליניארי שכן השתמשנו בתור וחצינו את כל הצמתים. לאלגוריתם מורכבות זמן ליניארית. מכיוון שהשתמשנו בתור כדי לחצות את כל הצמתים, מורכבות החלל הגרועה ביותר תהיה N, ולכן מורכבות החלל הליניארית.

V = מספר הצמתים בעץ

E = מספר הקצוות בצומת