---
# System prepended metadata

title: DFS & BFS

---

# 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
---
```python=
# 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).