დიაპაზონის პირველი ძებნა (BFS) დიაგრამაზე  


Რთული ტური Easy
ხშირად ეკითხებიან Amazon კადენს ინდოეთი GE Healthcare საცხოვრებელი. Com ჯიბის ძვირფასი ქვები UHG Optum
სიგანე პირველი ძებნა Graph Queue

სიგანის პირველი ძებნა (BFS) გრაფიკისთვის არის ხე / გრაფიკის მონაცემთა სტრუქტურაში გადატანის ან ძიების ალგორითმი. იგი იწყება მოცემული წვერიდან (ნებისმიერი თვითნებური მწვერვალიდან) და იკვლევს ყველა დაკავშირებულ მწვერვალს და ამის შემდეგ გადავა უახლოეს წვერზე და იკვლევს ყველა გამოუკვლევ კვანძს და ზრუნავს, რომ ორჯერ არცერთი მწვერვალი / კვანძი არ იყოს ნამყოფი. კონკრეტული კვანძიდან დაწყებული მოცემული გრაფიკის BFS გასარკვევად გვჭირდება a Queue მონაცემთა სტრუქტურა ამის გასარკვევად. გადავიდეთ მაგალითზე, რომ სწრაფად გავიგოთ

სიგანის პირველი ძიების (BFS) გავლა და მისი განხორციელება  

როდესაც კონკრეტულ კვანძს დავამატებთ დაკავშირებულ კვანძებს, შემდეგ ამ კვანძსაც დავამატებთ შედეგს და რიგიდან გავაფართოვებთ უფრო გასაგებად, უბრალოდ იხილეთ ქვემოთ მოცემული ეტაპობრივი პროცედურა:

გრაფიკის პირველი სიგანის ძებნა (BFS)Pin

 

გრაფიკის პირველი სიგანის ძებნა (BFS)Pin

 

გრაფიკის პირველი სიგანის ძებნა (BFS)Pin

 

გრაფიკის პირველი სიგანის ძებნა (BFS)Pin

 

გრაფიკის პირველი სიგანის ძებნა (BFS)Pin

 

გრაფიკის პირველი სიგანის ძებნა (BFS)Pin

 

გრაფიკის პირველი სიგანის ძებნა (BFS)Pin

 

გრაფიკის პირველი სიგანის ძებნა (BFS)Pin

 

გრაფიკის პირველი სიგანის ძებნა (BFS)Pin

 

Pin

 

Pin

 

Pin

 

Pin

 

Pin

 

შენიშვნა:

  •   კონკრეტული გრაფიკისთვის შესაძლებელია ერთზე მეტი BFS (როგორც ზემოთ მოცემული გრაფიკი). ისევე როგორც ზოგიერთი სხვა შესაძლო BFS ზემოთ მოცემული გრაფიკისთვის: (1,3,2,5,6,7,4,8), (1,3,2,7,6,5,4,8), (1,3,2,6,7,5,4,8, XNUMX).
  • BFS არის დონის შეკვეთის გადაკვეთა.

სიგანის პირველი ძიების (BFS) განხორციელება  

C ++ კოდი სიგანის პირველი ძიებისთვის (BFS)

/*C++ Implementation of BFS of a given graph using STL*/
#include <bits/stdc++.h>
using namespace std;
int main() {
    int nodes,edges;
    /*take input*/
    cin>>nodes>>edges;
    vector<int> v[nodes+1];
    bool visited[nodes+1];
    memset(visited,false,sizeof(visited));
    /*Make graph using vector*/
    for(int i=0;i<edges;i++)
    {
        int x,y;
        cin>>x>>y;
        /*add edge between x and y*/
        v[x].push_back(y);
        /*add edge between y and x*/
        v[y].push_back(x);
    }
    int start;
    /*Take input node at which the BFS starts*/
    cin>>start;
    queue<int> q_calc;
    q_calc.push(start);
    visited[start]=true;
    vector<int> bfs;
    while(!q_calc.empty())
    {
        /*pop the element from queue*/
        int pop_elem=q_calc.front();
        /*update the answer*/  
        bfs.push_back(pop_elem);
        q_calc.pop();
        /*add all the connected nodes with pop_elem into queue*/
        for(int i=0;i<v[pop_elem].size();i++)
        {
            /*if we visit already then we can't add it into queue*/
            if(!visited[v[pop_elem][i]])
            {
                visited[v[pop_elem][i]]=true;
                q_calc.push(v[pop_elem][i]);
            }
        }
    }
    /*print the BFS for given graph at starting with given node*/
    for(int i=0;i<nodes;i++)
    {
        cout<<bfs[i]<<" ";
    }
    cout<<"\n";
  return 0;
}
Input:
8 9
1 2
1 3
2 4
3 4
3 5
3 6
3 7
6 8
7 8
1
Output:
1 2 3 4 5 6 7 8

დროის სირთულე BFS  

O (V + E) სადაც V აღნიშნავს წვეროების რაოდენობას და E აღნიშნავს კიდეების რაოდენობას.

იხილეთ ასევე
კუნძულის მაქსიმალური ფართობი

Reference

ინტერვიუ კითხვები