DFS
- 깊이 우선 탐색
- 그래프에서 깊은 곳을 우선적으로 탐색하는 알고리즘
- STACK 구조를 이용한 DFS 동작 과정
1. 탐색 시작 노드를 스택에 PUSH
2. 스택의 최상단 노드의 인접노드 중 방문하지 않은 노드가 있으면 그 인접 노드를 스택에 PUSH하고 방문 + 더이상 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 꺼냄
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복
- 데이터의 개수가 N개인 경우 시간복잡도 O(N)
BFS
- 너비 우선 탐색
- 가까운 노드 먼저 탐색 = 큐 자료구조 이용(먼저 들어온게 먼저 나가도록 하기 위해서)
- QUEUE를 이용한 BFS 동작 과정
1. 탐색 시작 노드를 큐에 put
2. 큐에서 노드를 get해서 get된 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복
그래프 표현 방식
- 인접행렬: 2차원 리스트에 각 노드가 연결된 형태를 기록하는 방식
--> 연결되지 않은 노드끼리는 무한 비용으로 작성 = 실제 코드에서는 논리적으로 말이 안되는 큰 값들을 사용하는 경우가 많다.
graph = [
[노드0, 노드1과의 비용, 노드2와의 비용, 노드3과의 비용,,,, ]
]
- 인접리스트: 모든 노드에 연결된 노드에 대한 정보를 차례대로 저장
--> 파이썬의 경우 인접리스트의 내용을 별도의 라이브러리 없이 append를 이용해서 추가하면됨
graph = [[] for _ in range(노드 개수)]
graph[0].append((노드, 거리))
인접행렬 vs 인접리스트
- 인접행렬은 연결되지 않은 노드 사이의 관계들도 무한 비용으로 표현하고 모두 작성하기 때문에 메모리 측면에서 보면 인접리스트보다 비효율적이라고 볼 수 있음
- 인접리스트는 특정한 두 노드가 연결되어 있느지 확인할때 비효율적
- 특정한 노드와 연결된 모든 인접 노드를 순회해야 하는 경우 인접 리스트 방식이 인접 행렬 방식에 비해 메모리 공간의 낭비가 적음 (인접리스트가 연결되지 않는 노드의 정보는 저장하지 않으니까)