[그래프탐색] DFS- JS, Python

탐색이란?

많은 양의 데이터 중에서 원하는 데이터를 찾는 과정

그래프, 트리 등의 자료구조 안에서 탐색하는 문제 자주 물음

DFS와 BFS를 다루기 전에 스택, 큐, 재귀함수에 대한 개념을 알아야 하는데 

전 포스팅에 정리한 내용을 확인해 주세요

2021.02.07 - [이론/자료구조] - 스택(Stack) - JS

2021.02.07 - [이론/자료구조] - 배열 - JS

2020.04.15 - [이론/알고리즘] - 재귀 함수

배열 - JS

스택(Stack) - JS

그래프 기본 구조

• 그래프는 노드(Node)와 간선(Edge)로 표현되며 이때 노드를 정점(Vertex)이라고 말한다
• 그래프 탐색이란 하나의 노드를 시작으로 다수의 노드를 방문하는 것을 말한다
• 두 노드가 간선으로 연결되어있다면 두 노드는 인접하다라고 표현된다

• 그래프는 크게 2가지 방식으로 표현
  • 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결관계를 표현하는 방식 / 각 노드가 연결된 형태를 기록하는 방식 / 연결되어 있지 않은 노드끼리는 무한의 비용이라고 작성
    
    • 모든 관계를 저장하므로 노드 개수가 많을 수록 메모리가 불필요하게 낭비됨
    • 노드1과 노드 7이 연결되어있는지 확인할 때 graph[1][7]로 바로 확인 가능
  • 인접 리스트(Adjacency Matrix) : 리스트로 그래프의 연결 관계를 표현하는 방식 / 모든 노드에 연결된 노드에 대한 정보 차례대로 연결하여 저장 / 연결리스트라는 자료구조를 이용해 구현하는데 파이썬은 연결리스트의 기능 모두 기본으로 제공하므로 2차원 리스트를 이용하면 된다
    • 인접행렬방식에 비해 특정한 두 노드가 연결되어 있는지에 대한 정보를 얻는 속도가 느리다 (연결된 데이터를 하나씩 확인해야 하기 때문에)
    • 노드1과 노드 7연결되어있는지 확인할 때 인접리스트 앞에서부터 차례대로 확인해야함
    • 메모리 공간의 낭비는 적다

인접행렬방식

INF = 987654321

graph = [
    [0, 7, 5],
    [7, 0, INF],
    [5, INF, 0]
]

print(graph)

인접 리스트방식

# 행(ROW)이 3개인 2차원 리스트로 인접 리스트 표현
graph = [[] for _ in range(3)]

# 노드 0에 연결된 노드 정보 저장(노드, 거리)
graph[0].append((1, 7))
graph[0].append((2, 5))

# 노드 1에 연결된 노드 정보 저장(노드, 거리)
graph[1].append((0, 7))

# 노드 2에 연결된 노드 정보 저장(노드, 거리)
graph[2].append((0, 5))

print(graph) # [[(1, 7),(2, 5)],[(0, 7)],[(0, 5)]]

깊이우선탐색(DFS)

• 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘
• 특정한 경로를 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후 다시 돌아가 다른 경로로 탐색하는 알고리즘
• 관행적으로 번호가 낮은 순서부터 처리하도록 구현
• 한 번에 이해하기 어려운 경우 종이에 직접 써가면서 해보는걸 추천한다

1. 탐색 시작 노드를 스택에 삽입하고 방문처리를 한다

2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다

3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다

TIP. 방문처리는 스택에 한 번 삽입되어 처리된 노드가 다시 삽입되지 않게 체크하는 것.

BIG O

참고

인접 행렬을 사용하는 경우

DFS 하나에 for loop을 V 만큼 돌기 때문에, O(V) 시간이 필요함.

정점을 방문할 때 마다 DFS를 부르는데, V개의 정점을 모두 방문하므로

DFS의 전체 시간복잡도 = V * O(V) = O(V^2)

 

인접 리스트를 사용하는 경우

DFS는 총 V번 부르게 된다. 그러나, 인접 행렬로 구현한 경우와 달리 인접 리스트로 구현한 DFS는 DFS 하나당 각 정점에 연결되어 있는 간선의 개수만큼 탐색을 하게 되어 DFS 하나의 수행 시간이 일정하지 않다.

전체 DFS가 다 끝난 이후를 생각해 보면, DFS가 다 끝났을 시점에는 모든 정점을 한번씩 방문하고, 모든 간선을 한번씩 검사하게 되므로 O(V+E)의 시간이 걸린다고 말할 수 있다.

따라서, 인접리스트로 구현할 경우 DFS의 시간 복잡도는 O(V+E)이다.

 

특징

• 재귀함수로 DFS구현하면 실제 수행시간이 느려질 수 있다. 
• 스택과 재귀를 사용해서 구현
• BFS보다는 구현시간이 느림 (BFS는 O(N)의 시간복잡도를 가짐)
• 스택 오버플로우가 생길 수 있음
• 모든 경우를 다 탐색 해봐야하는 경우 사용함

 

코드 구현

Python

def dfs(graph, v, visited):
	visited[v] = True
    print(v, end=' ') # 1 2 7 6 8 3 4 5
    
    for i in graph[v]: # 방문한 노드와 연결된 노드들 확인
    	if not visited[i]: 
        	dfs(graph, i, visited)
    	


graph = [
    [],
    [2, 3, 8],
    [1, 7], 
    [1, 4, 5],
    [3, 5],
    [3, 4], 
    [7], 
    [2, 6, 8],
    [1, 7]
]

visited = [False] * 9

dfs(graph, 1, visited)

 

JS

const dfs = function(graph, v, visited, result) {
    visited[v] = true
    console.log(v + '\t')
    for (const i of graph[v]) {
        if (!visited[i]) {
            dfs(graph, i, visited)
        }
    }
}


graph = [
    [],
    [2, 3, 8],
    [1, 7], 
    [1, 4, 5],
    [3, 5],
    [3, 4], 
    [7], 
    [2, 6, 8],
    [1, 7]
]

// 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
visited = Array(9).fill(false)
let result = ''
dfs(graph, 1, visited, result)



//1	
//2	
//7	
//6	
//8	
//3	
//4	
//5