DFS(Depth-First-Search)

• 깊이 우선 탐색
• 가장 깊은 곳까지 탐색
• 모든 노드를 방문하고자 할때 사용되는 방법
  - ex) 미로 찾기, 그래프의 위상정렬, 전체 탐색, 연결 구성요소 찾기, 이분 그래프 등
• BFS에 비해 검색 속도는 느림
• 스택, 재귀함수 사용해 구현

DFS 구현

1. 재귀로 구현

def dfs(start, visited = [False]*(N+1)):
    visited[start] = True
    for v in G[start]:
        if not visited[v]:
            dfs(v, visited) 
    return visited

방문하지 않은 노드(v)일 경우 dfs 함수를 호출해 방문해준다.
visited의 모든 노드가 방문처리 될때까지 재귀호출을 하는 형태이다.

2. 스택(stack)으로 구현

from collections import deque

def dfs(start, visited=[False]*(N+1)):
    stack = deque()
    stack.append(start)
    while stack: 
        v = stack.pop()
        if not visited[v]:
            visited[v] = True
            for u in G[v]:
                stack.append(u)
    return visited

recursion depth를 고려해야하는 코드라면, 재귀대신 for문과 스택 자료구조를 사용하면 된다.
인접 노드를 차례로 저장하고, 최근 방문한 순으로 꺼내쓸수 있는 자료구조가 필요하기 때문에 스택을 사용하는 것이다.

BFS(Breadth-First-Search)

• 너비 우선 탐색
• 시작점인 루트노드와 같은 거리에 있는 노드부터(가까운 노드부터) 우선적으로 탐색
• 최단 경로 탐색시 사용
• 큐를 사용해 구현
  

BFS 구현

큐(queue)로 구현

from collections import deque

def bfs(start, visited=[False]*(N+1)):
    que = deque()
    que.append(start)
    while que: 
    	v = que.popleft()
        if not visited[v]:
            visited[v] = True
            for u in G[v]:
                que.append(u)

    return visited

---

참고 자료

• https://codingsmu.tistory.com/170#--%--%EC%-E%AC%EA%B-%--%EB%A-%-C%--%EA%B-%AC%ED%--%--