DFS와 BFS의 시간복잡도와 공간복잡도
DFS
시간복잡도 : O(V+E)
공간복잡도 : 인접행렬로 구현시 - O(V^2) / 인접리스트 - O(V+E)
BFS
시간복잡도 : O(V+E)
공간복잡도 : 인접행렬로 구현시 - O(V^2) / 인접리스트 - O(V+E)
DFS와 BFS의 특징과 장단점
DFS
특징 : 재귀나 스택으로 구현
장점 : 매우 넓은 그래프 탐색에 효과적임
단점 : 목표 노드가 없는 경로에 깊이 빠질 수 있음
사용예 : 위상정렬, 사이클 탐지
BFS
특징 : 큐로 구현
장점 : 매우 깊거나 무한에 가까운 그래프 탐색에 효과적임
단점 : 목표 노드로의 경로의 길이가 모두 같다면 비효과적임
사용예 : 최단경로, 최소신장트리
DFS 함수 구현
public static void dfs(int i){
visit[i] = true; // 함수 호출 시, visit 했음을 표시
System.out.print(i+ " ");
for(int j = 1; j < Nv+1; j++){
if(ad[i][j] == 1 && visit[j] == false){ // j를 방문하지 않았으면 j를 방문한다.
dfs(j);
}
}
}
백트래킹이란?
깊이 우선 탐색 시 막히면 나아갈 곳이 있는 곳으로 돌아가는 방법
최소신장트리란?
신장 트리 중 edge weight의 합이 최소인 신장트리를 말함.
신장트리
그래프의 모든 정점이 cycle 없이 연결된 형태를 말함.
그래프에서 제한사항 2가지
- 자기 자신을 향하는 간선은 없다.(no self loop)
- 중복된 간선을 허용하지 않는다.(not multigraph)
그래프 구현시 인접행렬과 인접리스트 방식의 장단점
인접 행렬
장점 : 직관적이며 쉽게 구현 가능, dense Graph에 효과적임(값이 거의다 있는 그래프)
단점 : 불필요한 정보의 저장이 많으며 그래프의 크기가 커지면 메모리 초과가 발생할 수 있음
인접 리스트
장점 : 필요한 정보만 저장하여 메모리 절약 가능, sparse graph에 효과적임(0인 값이 많은 행렬)
단점 : 인접행렬에 비해 다소 구현이 어려움
그래프에서 사이클을 찾는 방법
그래프 탐색 알고리즘을 사용하여 방문했던 노드를 다시 방문한 경우에 사이클이라 판정
이분 그래프란?
그래프를 A, B로 나눌 수 있을 때 A에 포함되어 있는 정점끼리 연결된 간선이 없으며, B에 포함되어 있는 정점끼리 연결된 간선이 없는 그래프