График үшін бірінші іздеу (BFS)


Күрделілік дәрежесі оңай
Жиі кіреді Amazon Cadence Үндістан GE Healthcare Housing.com Қалта асыл тастар UHG Optum
Бірінші іздеу Графика кезек

Бірінші іздеу (BFS) график үшін бұл ағаш / граф деректер құрылымындағы өтпелі немесе іздеу алгоритмі. Ол берілген шыңнан басталады (кез-келген еркін шыңнан) және барлық байланысқан шыңдарды зерттейді, содан кейін ең жақын шыңдарға ауысады және зерттелмеген барлық түйіндерді зерттейді және ешқандай шыңдар / түйіндер екі рет келмеуін қадағалайды. Белгілі бір түйіннен басталатын берілген графиканың BFS мәнін білу үшін бізге а керек кезек табу үшін деректер құрылымы. Туралы тез түсіну үшін мысалға көшейік

Бірінші іздеуді кеңейту (BFS) және оны жүзеге асыру

Байланыстырылған түйіндерді белгілі бір түйінге қосқан кезде нәтижеге қосыламыз және кезектен көп түсіну үшін кезекпен төмендегі процедураны қараңыз:

График үшін бірінші іздеу (BFS)

 

График үшін бірінші іздеу (BFS)

 

График үшін бірінші іздеу (BFS)

 

График үшін бірінші іздеу (BFS)

 

График үшін бірінші іздеу (BFS)

 

График үшін бірінші іздеу (BFS)

 

График үшін бірінші іздеу (BFS)

 

График үшін бірінші іздеу (BFS)

 

График үшін бірінші іздеу (BFS)

 

 

 

 

 

 

ЕСКЕРТУ:

  •   Белгілі бір график үшін бірнеше 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

БФС уақытының күрделілігі

O (V + E) мұндағы V шыңдар санын, ал E шеттер санын білдіреді.

анықтамалық

Сұхбат сұрақтары