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

DFS

 

깊이 우선 탐색은 맹목적 탐색방법으로써 길을 탐색할 때 한 방향으로 이동 가능 할 때까지 탐색한 후 더 이상 이동이 불가 하면 마지막 갈림길로 돌아가 다른 방향으로 다시 탐색을 진행하는 방법이다.이러한 DFS는 그래프의 전체구조 및 관계도 파악에 매우 유리하다.

 

 

DFS구현

 

 

 

그래프는 다음의 그래프를 사용한다.

 

방향 그래프

 

struct Vertex{};
vector<Vertex>ver;
vector<vector<int>>adjacent;
 vector<bool>visited(6,false);

void CreateGraph()_1//인접 리스트
{
 ver.resize(6);
 adjacent=vector<vector<int>>(6);
 
 adjacent[0].push_back(1);
 adjacent[0].push_back(3);
 adjacent[1].push_back(0);
 adjacent[1].push_back(2);
 adjacent[1].push_back(3);
 adjacent[3].push_back(4);
 adjacent[5].push_back(4);
 
}

void CreateGraph_2()//인접 행렬
{
 ver.resize(6);
 adjacent=vector<vector<int>>
 {
 
  {0,1,0,1,0,0},
  {1,0,1,1,0,0},
  {0,0,0,0,0,0},
  {0,0,0,0,1,0},
  {0,0,0,0,0,0},
  {0,0,0,0,1,0}
  
 };
 
 
}

 

 

void DFS_1(int here)//인접 리스트 DFS
{
 visited[here]=true;
 for(int i=0;i<adjacent[i].size();i++)
 {
  int there=adjacent[here][i];
  if(visited[there]=false)DFS_1(there);
 }
}

void DFS_2(int here)// 인접 행렬 DFS
{
 for(int there=0;there<6;there++)
 {
  if(adjacent[here][there]==0)continue;
  if(visited[there]==false)DFS_2(there);
 }
}