그래프 탐색
하나의 정점으로부터 시작하여 차례대로 모든 정점을 한번씩 방문하는 것이다.
DFS
•
root 에서 시작해서 다음 branch 로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법이다.
•
넓게 탐색하기 전에 깊게 탐색하는 것이다.
•
모든 노드를 방문하고자 하는 경우에 사용한다.
•
자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다.
•
stack 자료 구조를 활용한다.
•
어떤 노드를 방문했는지의 여부를 반드시 검사해야 한다.
◦
무한 루프 방지
BFS
•
그래프에서 가장 가까운 부분을 우선적으로 탐색한다.
•
한 정점에서 가장 인접한 노드를 먼저 넓게 탐색하므로 DFS 와는 정반대이다.
•
재귀적으로 동작하지 않는다.
•
노드 방문 여부를 반드시 검사해야 한다.
•
방문한 노드들을 차례로 저장한 후 꺼낼 수 있는 Queue 를 사용한다.
•
최단 경로를 찾는 데 활용한다.
◦
다익스트라
◦
플로이드
이분 그래프(Bipartite Graph)
•
그래프의 모든 정점이 두 그룹으로 나누어지고, 서로 다른 그룹의 정점이 간선으로 연결되어져 있는 그래프를 이분 그래프라고 한다.
•
이분 그래프인지 확인하기 위해 BFS, DFS 탐색을 사용한다.
◦
BFS 에서 같은 레벨의 정점 끼리는 무조건 같은 색으로 칠해진다.
•
연결 성분의 개수를 구하는 방법과 유사하다.
•
모든 정점을 방문하여 간선을 검사한다.