[CS] 자료구조(Graph, Tree & BST) 기초 Day-26

Graph

일반적으로 수학에서 얘기하는 그래프가 아니라 복잡한 네트워크망을 그래프라고 합니다.

여러개의 점들이 서로 복잡하게 연결되어 있는 관계를 표현한 자료구조입니다. 직접적인 관계가 있는 경우 두 점 사이를 이어주는 선이 있습니다.

Graph 실사용 예

포털 사이트의 검색 엔진, SNS에서 사람들과의 관계, 네비게이션에서 사용하는 자료구조가 Graph 입니다. 세 가지 모두 수많은 정점을 가지고 있고, 관계가 있는 정점은 간선으로 이어집니다.

• 간선: 연결된 두 개의 정점에서 데이터가 이동할 수 있음을 나타낸다.
• 데이터가 서로 이동할 수 없는 경우 관계가 없다고 표현합니다.

ex) 코드

let isConnected = {
	seoul: {
    	busan: true,
        daegu: true
    },
    busan: {
    	seoul: true,
        daegu: true
    }
    daegu: {
    	seoul: true,
        busan: true
    }
}

console.log(isConnected.seoul.busan) // true
console.log(isConnected.busan.seoul) // true

위 코드를 통해 네비게이션이 서울 부산 경로를 출력할 수 있고, 부산 서울도 경로를 출력할 수 있음을 알 수 있습니다.
(수백 만 개의 데이터를 추가해 간선을 통해 거리, 시간등을 표기할 수 있고 일반 네비게이션의 자료구조와 유사해집니다.)

Graph 용어 정리

• 정점(vertex): 노드(node)라고도 하며 데이터가 저장되는 그래프의 기본 원소입니다.
• 간선(edge): 정점 간의 관계를 나타냅니다.
• 인접 정점(adjacent vertex): 하나의 정점에서 간선에 의해 직접 연결되어 있는 정점을 뜻합니다.
• 가중치 그래프(weighted Graph): 연결의 강도가 얼마나 되는지 적혀져 있는 그래프를 뜻합니다.
• 비가중치 그래프(unweighted Graph): 연결의 강도가 적혀져 있지 않는 그래프를 뜻합니다.
• 무(방)향 그래프(undirected Graph): 단방향 그래프로 구현된 경우 일방통행이라고 생각하면 됩니다. 데이터가 한쪽으로만 갈 수 있습니다.
• 진입차수(in-degree) / 진출차수(out-degree): 한 정점에 진입하고 진출하는 간선이 몇개인지 나타냅니다.
• 인접(adjacency): 두 정점 간 간선이 직접 이어져 있다면 두 정점은 인접한 정점입니다.
• 사이클(cycle): 한 정점에서 출발하여 해당 정점으로 돌아갈 수 있을 때 사이클이 있다고 표현합니다.

(비중이 낮은 인접)

인접 행렬

• 두 정점 사이에 관계가 있는지 확인 할 때
• 가장 빠른 경로를 찾고자 할 때 사용

인접 리스트

인접 리스트는 각 정점이 어떤 정점과 인접하는지를 리스트의 형태료 표현합니다.
각 정점마다 하나의 리스트를 가지고 있으며, 리스트는 자신과 인접한 다른 정점을 담고 있습니다.

인접 리스트를 사용할 경우 장점도 있지만 우선 순위와 관련된 자료구조를 다뤄야 할 때 Queue, heap을 사용하는 것이 합리적입니다.

그럼에도 불구하고 인접 리스트를 사용하는 이유는 메모리를 효율적으로 사용할 수 있기 때문입니다.

Tree

단방향 그래프의 한 구조로, 하나의 뿌리로부터 가지가 사방으로 뻗은 형태를 트리구조라고 합니다.

나무를 거꾸로 뒤집어 놓은 모양이라고 트리 구조..

데이터가 단방향으로 연결된 계층적 자료구조입니다. 하나의 데이터 아래에 여러 개의 데이터가 존재할 수 있는 비선형 구조입니다. 트리 구조는 아래로만 뻗어나가기 때문에 사이클이 없습니다.

트리 구조는 (Root)라는 하나의 꼭지점 데이터를 시작으로 여러 개의 데이터를 간선(edge)로 연결합니다. 각 데이터를 노드(Node)라고 하며, 두 개의 노드가 상항 계층으로 연결되면 부모/자식 관계를 가지게 됩니다.

위 자료를 보면 F는 B와 G의 부모 노드(Parent Node)고, B와 G는 F의 자식 노드(Child Node)라고 합니다. A, C, E, H와 같이 자식이 없는 노드를 리프 노드(Leaf Node)라고 부릅니다.

용어 정리

• 노드(Node): 트리 구조를 이루는 모든 개별 데이터
• 루트(Root): 트리 구조의 시작점이 되는 노드
• 부모 노드(Parent Node): 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 가까운 노드
• 자식 노드(Child Node): 두 노드가 상하관계로 연결되어 있을 때 상대적으로 루트에서 먼 노드
• 리프(Leaf): 트리 구조의 끝 지점이고, 자식이 없는 경우에 해당

트리 구조에서 깊이(depth)

트리 구조에서 루트로부터 하위 계층의 특정 노드까지의 깊이(depth)를 표현할 수 있습니다. 루트 노드는 지면에 있는 것처럼 깊이가 0입니다. 반면 B,G는 깊이가 1이 됩니다. A, D, I는 깊이가 2가 됩니다.

트리 구조에서 레벨(level)

트리 구조에서 같은 깊이를 가지고 있는 노드를 묶어서 레벨(level)로 표현할 수 있습니다. 깊이가 0일 경우 level1, 깊이가 1일 경우 level2 입니다. 같은 레벨에 나란히 있는 노드를 형제 노트 (sibling Node)라고 합니다.

서브 트리(Sub Tree)

트리 구조의 Root에서 뻗어 나와 작은 트리 구조를 갖춘 것을 서브 트리 라고 부릅니다. B,A,D를 묶으면 서브 트리가 될 수 있습니다.

트리의 실 사용

가장 대표적인 예가 컴퓨터의 디렉토리 구조입니다. 어떤 프로그램이나 파일을 찾을 때 폴더에 진입하고 그 안에서 도 다른 폴더로 진입하면서 원하는 파일을 찾습니다.

모든 폴더는 루트 폴더에서 부터 시작됩니다.

Binary Search Tree (BST)

트리 구조는 편리한 구조를 전시하는 것 외 효율적인 탐색을 위해 사용됩니다.

• Binary Tree(이진 트리): 자식 노드가 최대 2개인 노드들로 구성 된 트리입니다. 두 개의 자식 노드는 왼쪽 자식 노드와 오른쪽 자식 노드로 나눌 수 있습니다.

이진 트리는 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full binary Tree), 완전 이진 트리(Complete binary Tree), 포화 이진 트리(Perfect binary Tree)로 나뉩니다.

균형이 잡히지 않은 트리는 탐색하는 데 시간이 더 걸리는 경우도 있기 때문에 해결해야 할 문제입니다.

Tree traversal

특정 목적을 위해 트리의 모든 노드를 한 번씩 방문하는 것을 트리 순회라고 합니다.
1에서 10까지의 정수로 구성된 트리에서 3이라는 숫자를 찾기 위해 모든 노드를 방문하는 경우는 트리 순회의 한 예시입니다.

트리 순회 방법

• 전위 순회
  루트부터 시작해 왼쪽의 노드들을 순차적으로 둘러본 뒤, 왼쪽의 노드 탐색이 끝나면 오른쪽 노드를 탐색합니다.

• 중위 순회
  루트를 가운데에 두고 순회합니다. 제일 왼쪽 끝에 있는 노드부터 순회하기 시작하여 루트를 기준으로 왼쪽 노드의 순회가 끝나면 오른쪽 노드로 이동하며 탐색합니다.

• 후위 순회
  루트를 가장 마지막에 순회합니다. 제일 왼쪽 끝에 노드부터 순회하기 시작하여 루트를 거치지 않고 오른쪽으로 이동해 마지막에 루트를 순회합니다.

BFS / DFS

그래프의 탐색은 하나의 정점에서 시작해 그래프의 모든 정점들을 한 번씩 방문하는 것이 목적입니다. 그래프의 데이터는 배열처럼 정렬이 되어 있지 않습니다. 원하는 자료를 찾으려면 하나씩 방문해야 합니다.

그래프의 모든 정점 탐색 방법에도 여러 가지가 있습니다. 그 중 대표적인 두 가지 방법이 DFS와 BFS를 소개합니다. 데이터를 탐색하는 순서만 다를 뿐, 모든 자료를 하나씩 확인하는 건 똑같습니다.

BFS

가까운 정점부터 탐색을 시작합니다. 정점을 순서대로 방문하고 경로를 최단으로 찾을 때 사용합니다.

DFS

하나의 경로를 끝까지 탐색한 후 다음 경로로 넘어갑니다. 한 정점에서 시작해 다음 경로로 넘어가기 전 경로를 계속해서 살펴봅니다.
(가장 가까운 경로를 살펴보기보다는 맞는 경로를 탐색 후 기타 경로도 계속해서 검색합니다.)