[알고리즘] DFS

DFS

• 그래프 탐색 알고리즘 (그래프의 모든 정점을 확인하는 알고리즘) 중 하나
• 그래프 (Graph)
  • Vertex (정점) + Edge(간선)
  • Degree (차수) - 정점에 연결되어 있는 간선의 수, 방향 그래프에서 진입/진출 차수의 합
• 깊이 우선 탐색

• 재귀적으로 구현 (스택으로도 가능)

시간 복잡도

• 인접 행렬 : O(n^2)
• 인접 리스트 : O(n+e)

자료 구조

• 검색할 그래프
• 방문 여부 확인 (재방문 금지)

예시 코드

def dfs(g,v,visited):
    visited[v] = True
    print(v,end =' ')
    for i in g[v]:
        if not visited[i]:
            dfs(g,i,visited)