알고리즘 복습/그래프

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

PJNull 2022. 2. 5. 22:32
728x90
반응형

BFS

 

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

 

BFS구현

 

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

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

 

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

DFS 깊이 우선 탐색은 맹목적 탐색방법으로써 길을 탐색할 때 한 방향으로 이동 가능 할 때까지 탐색한 후 더 이상 이동이 불가 하면 마지막 갈림길로 돌아가 다른 방향으로 다시 탐색을 진행하

pjnull.tistory.com

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;
  }
 }
}
728x90
반응형