DFS
- 재귀함수 사용
- 스택을 사용
- 한 방향으로 깊게 들어가고 더이상 자식 노드가 없으면 되돌아서 방문 안한 곳을 방문함
- 시간복잡도 O(∣V∣+∣E∣)
BFS
- 이웃을 먼저 탐색함 (시작노드의 이웃노드 → 그다음노드의 이웃노드 → …)
- 큐(FIFO)를 사용
- 시간복잡도 O(∣V∣+∣E∣)
다익스트라
- 한 지점에서 모든 노드의 거리를 구하는 것(1차원 배열)
- 가중치가 있는 그래프 최단 거리 구하기
- 가중치에 음수가 있으면 작동에 오류가 생김
- 우선순위 큐를 사용함 (최솟값 추출)
- 시간복잡도는 O(∣E∣log∣V∣)
플로이드
- 모든지점에서 모든지점까지의 거리 (2차원 배열)
- 쉽게 작성이 되지만 3중 반복문을 사용하기에 필요한 부분만 다익스트라를 돌리는게 효율적
크루스칼
- MST - 최소한의 비용을 이용한 스패닝 트리a
- Union-Find -
- 경로 압축: logN으로 개선
- 크루스칼은 그래프에서 가장 작은 가중치를 고르면서 트리형태를 유지하게끔 만드는 것이다
- 간선 개수가 E개면 O(ElogE) 의 시간복잡도를 가짐
- 배열을 사용
프림
- 크루스칼과 반대로 한 지점에서 시작해 점점 확장하는 방식
- 우선순위 큐 사용
- 정점이 V, 간선이 E이면 시간복잡도는 O(∣E∣log∣V∣)
- 그 이유는 프림 알고리즘을 진행하면 각 간선을 한 번씩 보게 되는데, 이때 dist값이 변하면 우선순위큐에서의 순서가 계속 바뀌게 될 수도 있으므로 간선의 수 × 우선순위 큐 이용 시간복잡도가 됨
- 프림은 사이클을 신경안써도 되지만 크루스칼은 처리를 해줘야함
위상정렬
- 전 단계가 끝나야만 진행이 된다는 일이 있다면 많은 방법 중 하나를 골라주는 방법이 위상정렬
- DFS 와 in-degree 방법이 있다
- DFS
- 시간복잡도 O(V+E)
- 1번 정점부터 n번 까지 dfs를 적용시켜 모두 방문
- in-degree
- 시간복잡도 O(V+E)
- 0층부터 시작함
PM/PO