시스템 설계 면접 질문 너무 개방적이어서 올바른 준비 방법을 알기가 너무 어렵습니다. 이제 구매 후 Amazon, Microsoft 및 Adobe의 디자인 라운드를 해독할 수 있습니다. 이 책은. 매일 수정 하나 디자인 질문 그리고 나는 당신이 디자인 라운드를 깨뜨릴 수 있다고 약속합니다.
BFS (Breadth First Search) for a graph는 트리 / 그래프 데이터 구조의 순회 또는 검색 알고리즘입니다. 주어진 정점 (임의의 정점)에서 시작하여 연결된 모든 정점을 탐색 한 후 가장 가까운 정점으로 이동하여 탐색되지 않은 모든 노드를 탐색하고 정점 / 노드가 두 번 방문하지 않도록주의합니다. 특정 노드에서 시작하여 주어진 그래프의 BFS를 찾으려면 열 알아낼 데이터 구조. 에 대한 빠른 이해를 위해 예제로 이동하겠습니다.
차례
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는 모서리 수를 나타냅니다.
