[알고리즘] DFS(깊이 우선 탐색)

DFS는 길이 있으면 무조건 길 따라 더 들어가보는 노빠꾸 상남자다.

가보지 않는 길을 가는 상남자기 때문에 정점과 연결되어 있는 정점의 방문 여부를 체크한다.

 

void DFS(int here)
{
	visited[here] = true;
    
    for(int i=0; i < adjacent[here].size(); i++) //정점과 연결된 정점들 순회
    {
	int there = adjacent[here][i];
        if(visited[there]==false)
        	DFS(there); //방문하지 않은 정점에 대하여 재귀
    }

 

이렇게 하면 간선이 연결되지 않은 정점은 아예 탐색이 안될 수 있기 때문에 모든 정점에 대해 DFS를 해줘야 한다.

 

void DFSAll(int here)
{
	visited = vector<bool>(6,false);
    
    for (int i=0; i < 5;i++)
    	if(visited[i]==false)
        	DFS(i);
 }