[알고리즘 개념] DFS

 

<DFS>

오늘 배워볼 주제는 DFS입니다.

DFS란 무엇인가요?

 

DFS(깊이 우선 탐색, Depth-First Search)

-> 그래프에서 노드를 탐색하는 알고리즘 중 하나

-> 가능한 깊게 노드를 탐색,가능한 깊게 노드를 방문하고 더 이상 방문할 노드가 없다면 이전으로 돌아가 다른 경로를 탐색한다.

->주로 스택과 재귀함수를 사용한다.

 

 

DFS의 메커니즘은 다음과 같습니다.

 

1. 시작 노드를 스택에 삽입하고, 방문처리

2. 스택의 최상단 노드의 인접노드가 방문처리가 되어 있지 않다면, 해당 노드를 스택에 넣고 방문처리를 한다.

3. 방문하지 않은 인접 노드가 없다면 스택에서 해당 노드를 꺼낸다.

4. 2와 3을 반복하여 모든 노드를 방문할때까지 계속한다.

 

 

 

그래프의 구현 방식

1. 인접행렬

2. 인접리스트

 

-인접행렬 - 2차원 배열로 표현

노드의 수가 N이라면 N*N행렬을 만들어서 표현하는 겁니다.

def dfs(matrix, v, visited):
    visited[v] = True	#시작노드 방문처리
    print(v, end=' ')	#시작노드 출력
    for i in range(len(matrix[v])):	#시작 노드의 인접 노드 확인
        if matrix[v][i] == 1 and not visited[i]:	#인접 노드(1)이 방문처리가 되어 있지 않다면
            dfs(matrix, i, visited)		#dfs 재귀처리

n = 5  # 노드의 수
visited = [False] * n
graph = [
    [0, 1, 1, 0, 0],
    [1, 0, 0, 1, 0],
    [1, 0, 0, 0, 1],
    [0, 1, 0, 0, 0],
    [0, 0, 1, 0, 0]
]

dfs(graph, 0, visited)

 

인접리스트 - 각 노드에 연결된 다른 노드들의 목록을 배열이나 리스트로 저장합니다.

def dfs(graph, v, visited):
    visited[v] = True		#노드 방문처리
    print(v, end=' ')		#출력
    for i in graph[v]:		#연결된 노드 중 방문처리 안되어 있는게 있다면 방문처리
        if not visited[i]:
            dfs(graph, i, visited)

n = 5  # 노드의 수
visited = [False] * n
graph = [
    [1, 2],    # 노드 0에 연결된 노드
    [0, 3],    # 노드 1에 연결된 노드
    [0, 4],    # 노드 2에 연결된 노드
    [1],       # 노드 3에 연결된 노드
    [2]        # 노드 4에 연결된 노드
]

dfs(graph, 0, visited)

 

인접행렬 방식은 연결되어 있지 않은 노드까지 모두 구현하는 반면에, 인접리스트 방식은 직접 연결된 노드만 저장하기에 메모리를 효율적으로 사용합니다. 

 

시간복잡도

N:정점의 수, E:간선의 수

* 인접 행렬로 표현된 그래프 : O(N^2)

* 인접 리스트로 표현된 그래프 : O(N+E)

 

 

 

 

 

 

 

 

 

참고한 자료의 출처

 

https://lineho.tistory.com/42

[DFS, BFS/ 알고리즘] Depth First Search & Breadth First Search 알아보기