깊이 우선 탐색은 말 그대로 한 방향을 정해서 깊게 먼저 탐색하는 방식이다.

재귀적인 코드로 쉽게 구현이 가능하다
정점의 각 상태를 표기하여 다양한 정보로 활용하기 좋다.
인접리스트 O(V+E), 인접행렬 O(V^2)
backtracking과 다른 점은 퇴각할때 정점의 표시를 이전 상태로 되돌리는 작업.

그래프 간선의 속성

  • 트리 간선 : DFS가 탐색하는 간선. 현재 상태가 EXPLORED -> UNVISITED 로 향하는 간선
  • 역방향 간선 : 사이클에 해당하는 간선. 현재 상태가 EXPLORED -> EXPLORED 로 향하는 간선. (양방향 간선은 사이클로 취급하지 않음).
  • 순방향 간선, 교차 간선 : EXPLORED -> VISITED
그래프 간선 속성

이론

정점의 Color는 정점의 시간 기록으로 파악 가능하다.

  • White : 정점을 아직 방문하지 않음
  • Gray : 정점을 방문 중이고 하위 정점으로 간 상태
  • Black : 정점 방문이 끝났고 다른 정점으로 감
괄호 정리 - 흰색 경로 정리
정점 u가 발견 될 때, u->v 까지 모든 경로상 정점들은 흰색 정점으로 구성된다.
무방향 그래프에서는 트리간선, 역행간선만 존재 (순행, 교차간선은 없음)
=> 순행이 없는 것은 무방향이라 u->v->w에서 w에 도착했을때 w->u(역행) 간선으로 취급됨.
=> 교차도 마찬가지로, 방문 안했다면 트리간선이 되고 방문 했다면 역행간선이 됨.

소스 코드

각 정점에 시간을 기록하여 그래프 구조에 관한 중요한 정보 제공.

void graphCheck(int u){
    dfs_num[u] = EXPLORED;
    time_d[u] = time++;   // 시간 기록
    for (int j = 0; j < AdjList[u].size(); ++j){
        int v = AdjList[u][j];
        if (dfs_num[v] == UNVISITED){ // 트리 간선, EXPLORED->UNVISITED
            dfs_parent[v] = u;
            graphCheck(v);
        }
        else if (dfs_num[v] == EXPLOED){ //
            if (v == dfs_parent[u])
                // 양방향 간선
            else
                // 역방향 간선 (사이클 여부 조사)
        }
        else if (dfs_num[v] == VISITED) // EXPLORED->VISITED
            // forward/cross edge
    }
    dfs_num[u] = VISITED;
    time_f[u] = time++;
}