그래프에 대한 BFS (Breadth First Search)

난이도 쉽게
자주 묻는 질문 아마존 케이던스 인도 GE 헬스 케어 Housing.com 포켓 보석 UHG 옵텀
폭 우선 검색 Graph 조회수 74

시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.

BFS (Breadth First Search) for a graph는 트리 / 그래프 데이터 구조의 순회 또는 검색 알고리즘입니다. 주어진 정점 (임의의 정점)에서 시작하여 연결된 모든 정점을 탐색 한 후 가장 가까운 정점으로 이동하여 탐색되지 않은 모든 노드를 탐색하고 정점 / 노드가 두 번 방문하지 않도록주의합니다. 특정 노드에서 시작하여 주어진 그래프의 BFS를 찾으려면 알아낼 데이터 구조. 에 대한 빠른 이해를 위해 예제로 이동하겠습니다.

BFS (Breadth First Search) 순회 및 구현

연결된 노드를 특정 노드에 추가 할 때 해당 노드를 결과에 추가하고 더 많은 이해를 위해 대기열에서 팝합니다. 아래 단계별 절차를 참조하십시오.

그래프에 대한 BFS (Breadth First Search)

 

그래프에 대한 BFS (Breadth First Search)

 

그래프에 대한 BFS (Breadth First Search)

 

그래프에 대한 BFS (Breadth First Search)

 

그래프에 대한 BFS (Breadth First Search)

 

그래프에 대한 BFS (Breadth First Search)

 

그래프에 대한 BFS (Breadth First Search)

 

그래프에 대한 BFS (Breadth First Search)

 

그래프에 대한 BFS (Breadth First Search)

 

 

 

 

 

 

알림:

  •   특정 그래프에 대해 가능한 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 (Breadth First Search) 구현

BFS (Breadth First Search)를위한 C ++ 코드

/*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는 모서리 수를 나타냅니다.

참고

면접 질문

균열 시스템 설계 인터뷰
Translate »