알고리즘 복습) BFS(너비 우선 탐색)

BFS

 

BFS는 맹목적 탐색 방법중 하나로, 최단 경로 혹은 임의의 경로를 찾을때 매우 유용하다.

 

BFS구현

 

그래프는 지난 포스팅의 그래프를 활용한다.

[알고리즘 복습/그래프] - 알고리즘 복습) DFS(깊이 우선 탐색)

알고리즘 복습) DFS(깊이 우선 탐색)

void BFS(int here)//인접리스트
{

 vector<int>parent(6,-1);
 vector<int>distance(6,-1);
 
 queue<int>q;
 q.push(here);
 visited[here]=true;
 parent[here]=here;
 distance[here]=0;
 
 while(q.empty()==false)
 {
  here=q.front();
  q.pop();
  
  for(int there:adjacent[here])
  {
   if(visited[there])continue;
   
   q.push(there);
   visited[there]=true;
   parent[there]=here;
   distance[there]=distance[here]+1;
  }
 }
}

void BFS_2(int here)//인접행렬
{
 vector<int>parent(6,-1);
 vector<int>distance(6,-1);
 
 queue<int>q;
 q.push(here);
 visited[here]=true;
 parent[here]=here;
 distance[here]=0;
 
 while(q.empty()==false)
 {
  here=q.front();
  q.pop();
  
  for(int there=0;there<6;there++)
  {
   if(adjacent[here][there]==0)continue;
   if(visited[there])continue;
   
   q.push(there);
   visited[there]=true;
   parent[there]=here;
   distance[there]=distance[here]+1;
  }
 }
}