알고리즘) DFS(깊이 우선 탐색), BFS(넓이 우선 탐색)

그래프의 깊은 부분을 우선 탐색하는 알고리즘

-> 스택 자료구조 혹은 재귀함수를 이용

 

1. 스택의 최상단 노드에 방문하지 않은 인접한 노드가 있으면 해당 노드를 스택에 넣고 방문 처리
2. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다
3. 2번을 더이상 수행할 수 없을 때 까지 반복

인접한 노드에서 어디 부터 방문해야할지는 문제에서 주어진다

방문하지 않은 인접 노드가 여러개일 경우 보통은 번호가 낮은 인접 노드부터 

 

파이썬은 그래프를 표현하기 위해 2차원 배열을 이용

 

 

```

graph = [

    [],

    [2, 3, 8]

    [1, 7]

    [1, 4, 5]

    [3, 5]

    [3, 4]

    [7]

    [2, 6, 8],

    [1, 7]

]

 

def dfs(graph, v, visited):

    visited[v] = True

    print(v, end=' ')

    for i in graph[v]:

        if not visited[i]:

            dfs(graph, i, visited)

```

 

BFS 넓이 우선 탐색

그래프에서 가까운 노드부터 우선 탐색하는 알고리즘

BFS는 큐 자료구조를 이용

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리

2. 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모드 큐에 삽입하고 방문처리

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

 

 

```

from collections import deque

 

graph = [

    [],

    [2, 3, 8]

    [1, 7]

    [1, 4, 5]

    [3, 5]

    [3, 4]

    [7]

    [2, 6, 8],

    [1, 7]

]

 

def bfs(graph, start, visited):

 queue = deque([start])

visited[start] = True

while queue:

    v = queue.popleft()

    print(v, end=' ')

    for i in graph[v]:

        if not visited[i]:

            queue.append(i)

            visited[i] = True

 

```