알고리즘 (트리,DFS,BFS,디버그)

선형 구조 : 앞 , 뒤 관계가 1:1 인 구조

비선형 구조: 원소들 간의 1:n 관계를 가지는 자료구조

 

트리 : 비선형구조, 원소들 간에 계층관계를 가지는 계층형 자료구조, 하위원소로 내려가면서 확장되는 나무모양구조

비선형구조는 선형구조에서와 같이 선후 연결관계를 알 수 없기 때문에 노드를 중복되지 않게 전부 방문하는 특별한 방법이 필요 하다.

---

 

- 너비 우선 탐색 ( BFS ) : 자식 노드들을 먼저 모두 차례로 방문한 후, 방문 했던 자식 노들들을 기준으로 하여 다시 해당노드의 자식 노드들을 차례로 방문하는 방식.

인접한 노드들에 대해 탐색을 한후 , 차례로 다시 너비 우선 탐색을 진행해야 하므로, 선입 선출 형태의 자료구조인 큐를 활용함

 

 

BFS()

 큐 생성

 루트 v를 큐에 삽입

 while( 큐가 비어있지 않은 경우){

  t  <- 큐의 첫번쨰 원소 반환

  t 방문

  for(t와 연결된 모든 간선에 대해) {

      u <- t의 자식 노드

      u를 큐에 삽입

   }

 

---

- 깊이 우선 탐색 ( DFS )

가장 마지막에 만났던 갈림길의 노드로 되돌아가서 다시 깊이 우선 탐색을 반복해야 하므로 재귀적으로 구현하거나 후입선출 구조의 스택 사용해서 구현 ( 재귀가 사실 함수호출이 스택의 구조라 push,pop없이 보통 재귀적으로 많이 구현 )

3가지 기본적인 순회방법 : 전위순회, 중위순회, 후위순회

---

-DEBUG

여기부터 뭔가 버그가 있을것 같은데 ---> 그 라인에 브레이크 포인트

함수안에 파고들기(ex API, 재귀) ( F5 ) 함수 파고들었던거 빠져나오기 (F7)

F8을 누르면 다음 디버그 포인트로 이동된다. 만약 디버그 포인트가 지정되지 않았다면 디버그가 종료된다.

힙 : 완전 이진트리에 있는 노드중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료구조(최대 힙, 최소 힙)

우선순위 큐가 힙으로 구현되어있음 ( 자바에서 힙의 구현체는 PriorityQueue이다 ).