# DFS & BFS

- BFS: queue 를 사용. 반복문으로 구현
- 활용 사례
- 최단거리와 가중치가 없는 그래프의 minimum spanning tree (이건 DFS 도 가능)
- p2p network
- 검색엔진 크롤러
- social network에서 distance k 안에 있는 사람들을 찾기 위한 알고리즘
- garbage collection (locality 때문에)
- network broad casting
- path finding (두 vertex사이에 path 가 있는지 체크)
- 그래프에서 모든 연결 컴포넌트 찾기
- 하나의 연결 컴포넌트 내 모든 노드 찾기
- 두 노드 간 가장 짧은 경로 찾기
- 문제에서 DFS 보다 BFS 가 좀 더 땡기는 문제
- leaf node 까지 도착했는지 확인하는 문제. 예를 들어, src 에서 dest 까지 shortest path 로 가는 경로를 찾는 문제.
- https://leetcode.com/problems/path-sum/
- https://leetcode.com/problems/minimum-depth-of-binary-tree/
- DFS: stack 을 사용. 재귀함수로 구현
- 활용사례
- graph 에서 cycle 이 있는지 확인
- path finding
- topological sorting (scheduling, logic synthesis determining the order of compilation job)
- graph 가 bipartite 인지 체크
- 연결 컴포넌트 찾기
- 그래프의 관철점(articulation points, cut vertice)
- 미로 퍼즐 풀기
- 공통점: 순환될 수 있기 때문에 visited array 를 사용함. Backtracking 알고리즘을 사용하기 전에 가능한 한 많은 멀리? 가기 위한 알고리즘.

DFS - Permuatation
---

# DFS
def permute(self, nums):
    res = []
    self.dfs(nums, [], res)
    return res
    
def dfs(self, nums, path, res):
    if not nums:
        res.append(path)
        # return # backtracking
    for i in xrange(len(nums)):
        self.dfs(nums[:i]+nums[i+1:], path+[nums[i]], res)

> 코드 출처: https://leetcode.com/problems/permutations/discuss/18296/Simple-Python-solution-(DFS).