그래프, 트리구조, 이진 탐색 트리 -Data Structure

그래프란?

그래프는 노드(혹은 정점(vertex))와 노드와 노드 사이를 연결하는 간선(edge)로 구성.

그래프는 무방향(=간선에 의해 연결된 두 노드가 대칭일 수 있음)일 수도 있고 방향성(=비대칭 관계가 존재함)이 있을 수도 있다.

 

그래프의 개념

-진입 차수는 노드를 머리로 하는 간선이 다른 노드와 연결된 갯수.

-친출 차수는 노드를 꼬리로 하는 간선이 다른 노드와 연결된 갯수.

-인접 행렬 방식은 그래프 구현 방식 중 하나로 보통 배열을 이용해 정보를 저장한다(adj[i][j]). 

-인접 리스트 방식은 그래프 구현 방식 중 하나로 그래프의 연결 관계를 vector의 배열(vector<int>adj[])로 나타내는 방식이며 vector<int>에 노드 번호가 그대로 저장된다.

 

트리구조란?

노드로 구현된 계층적 자료구조.

최상위 노드를 루트로 두고 밑으로 child 노드가 추가되고 또 child 노드 밑으로 새로운 child가 추가되는 방식으로 구현된다.

 

트리구조의 개념

-트리의 각 구성요소를 노드라고 부른다.

-트리의 최상위에 위치한 노드를 루트라고 부른다.

-루트를 기준으로 노드에 접근하기 위한 거리를 depth라고 부른다.

-같은 부모를 가지면서 같은 깊이에 위치한 노드들은 sibling 관계에 있다.

-노드와 노드를 잇는 선은 edge이다.

-자식이 없는 노드는 leaf라고 부른다.

-----------------------

그래프 탐색이란?

하나의 정점에서 차례대로 모든 정점을 한 번식 방문하는 것

 

이진 탐색 트리란?

최대 2개의 자식만 가지는 트리구조이다.

트리구조는 재귀적이므로 자식 역시 최대 2개의 자식을 갖는다. 이진 탐색 트리에서는 노드의 값이 정렬방법에 따라 순서가 존재한다. 노드의 두 자식과 연결된 엣지 중 왼쪽 엣지로 연결된 서브트리에는 노드의 값보다 작은 값이, 오른쪽 엣지로 연결된 서브트리에는 노드의 값보다 같거나 큰 값이 존재한다.

 

 

이진 트리를 순회하는 방법

 

-DFS(Depth-First Search : 깊이 우선 탐색)

=루트 노드 혹은 임의의 노드에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 마지막 깊이까지 완벽하게 탐색하는 방법.

=모든 노드를 방문하고자 하는 경우 이 방법이 사용된다.

=너비 우선 탐색보다 구현이 간단하다.

=단순 검색 속도는 너비 우선 탐색에 비해 느리다.

=재귀 순환 알고리즘의 형태이다.

=전위 순회(Pre-Order Traversals)를 포함한 모든 트리 순회는 DFS의 일종이다.

=이 알고리즘을 구현할 때 주의점은 그래프 탐색 시 어떤 노드를 방문했었는지 여부를 반드시 검사해야 무한루프에 빠지지 않는다는 것이다.

 

-BFS(Breadth-First Search : 너비 우선 탐색)

=시작한 노드에서 가까운 노드부터 방문하고 멀리 떨어진 노드를 나중에 방문하는 순회 방법.

=두 노드 사이에 최단 경로나 임의의 경로를 찾고 싶을 때 사용된다.

=깊이 우선 탐색보다 구현이 복잡하다.

=재귀적으로 동작하지 않는다.

=이 알고리즘을 구현할 때 주의점은 그래프 탐색 시 어떤 노드를 방문했었는지 여부를 반드시 검사해야 무한루프에 빠지지 않는다는 것이다.

=방문한 노드들을 차례로 저장한 후 꺼낼 수 있도록 큐(Queue)를 사용한다.