[자료구조] 그래프 - DFS(Depth First Search)

DFS(Depth First Search)

• 그래프를 깊이를 우선시하여 탐색하는 알고리즘
• 하나의 정점에서 시작하여 그 정점에서부터 가장 깊은 정점까지 탐색한다.
• 방문 여부를 검사하여 재귀함수를 통해 구현하는게 간편하다.

• 위의 그래프에서 0부터 시작한다고 하면 0 -> 2 -> 3 -> 4 -> 5 -> 1의 순서로 탐색한다.

코드

void DFS(int here)
{
	visited[here] = true;
    
    for (int there = 0; there < 6; there++)
    {
    	if (adjecent[here][there] == 0)
        	continue;
        
        if (visited[here] == false)
        	DFS(there);
     }
}