깊이 우선 탐색 : 리프노드까지 아래로 내려가면서 탐색한다. 리프에 도달하면 부모에게 돌아간다. 그후 다시 자식노드로 내려간다.
: 노드 방문 => 왼쪽 자식 => 오른쪽 자식 순서로 우선 탐색을 진행한다.
: 왼쪽 자식 => 노드방문 => 오른쪽 자식
: 왼쪽 자식 => 오른쪽 자식 => 돌아와 노드 방문
너비 우선 탐색 : 낮은 레벨에서 시작해 왼쪽에서 오른쪽 방향으로 따라가다가 한 레벨에서 탐색이 끝나면 다음 레벨로 내려간다.
정점과 간선을 이용해 연결되어 있는 원소 사이 다대다 관계 표현한 자료구조
2차원 배열을 이용, 에지 중심으로 그래프 표현
코딩테스트에서 입력으로 주어지는 경우가 많음
2차원 배열을 이용, 노드 중심으로 그래프 표현
노드에 비해 간선이 작은 경우 메모리/탐색 효율이 낮음
ArrayList를 배열에 넣는 방법, 노드 중심으로 그래프를 표현
공간 효율이 좋고 각 노드에 연결되어 있는 엣지를 탐색하는데 빠름
실제 코딩테스트에서 가장 많이 선호되는 그래프 표현 방식
시작 노드에서 출발해 시작 노드를 기준으로 가까운 노드를 먼저 방문하면서 탐색하는 알고리즘이다.