Graph
컴퓨터에서의 그래프는 수학에서의 x,y축이 존재하는 그래프와는 달리
정점(vertex)과 간선(edge)로 이루어져있다.
여기서 각각의 번호가 정점이되며 그 정점을 바로 이어주는 선이 간선이 된다.
그래프는 보통 포털 사이트의 검색 엔진, SNS, 네비게이션 (길찾기) 등에서 사용되어지는 자료구조형이다.
정점: 서울, 대전, 부산
간선: 서울—대전, 대전—부산, 부산—서울
서울, 대전, 부산이 서로 이어져 있다는 것은 알 수 있지만, 각 도시가 얼마나 떨어져 있는지는 알 수 없다.
간선은 특정 도시 두 개가 이어져 있다는 사실만 알려줄 뿐, 그 외의 정보는 아무것도 없기 때문입니다. 가중치(연결의 강도가 얼마나 되는지)가 적혀 있지 않은 현재의 그래프는 비가중치 그래프 라고 부른다.
정점: 서울, 대전, 부산
간선: 서울—140km—대전, 대전—200km—부산, 부산—325km—서울
도시간의 거리를 추가해준다면 이것을 가중치 그래프라고 부른다.
이 가중치 그래프가 확장되어 수백만개의 정점(주소)과 간선이 추가 되어야 비로소 내비게이션에서 쓰는 자료구조와 유사해 지는 것이라고 할 수 있다.
그래프 용어 종류
-
무향그래프(undirected graph): 서울에서 부산으로 갈 수 있듯, 반대로 부산에서 서울로 가는것도 가능합니다. 하지만 단방향(directed) 그래프로 구현 된다면 서울에서 부산을 갈 수 있지만, 부산에서 서울로 가는 것은 불가능합니다(혹은 그 반대). 만약 두 지점이 일방통행 도로로 이어져 있다면 단방향인 간선으로 표현할 수 있습니다.
-
진입차수(in-degree) / 진출차수(out-degree): 한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타냅니다.
-
인접(adjacency): 두 정점간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점입니다.
-
자기 루프(self loop): 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 표현합니다. 다른 정점을 거치지 않는다는 것이 특징입니다.
-
사이클(cycle): 한 정점에서 출발하여 다시 해당 정점으로 돌아갈 수 있다면 사이클이 있다고 표현합니다.
인접행렬
두 정점을 바로 이어 주는 간선이 있다면 이 두 정점은 인접하다고 한다.
인접 행렬은 정점들간의 인접함을 표시해 주는 행렬으로 2차원 배열의 모습
[ a b c
a [0][0][1]
b [0][0][1] // 1은 인접된 상태
c [1][0][0]
]인정햅렬 장점: 한눈에 확인 할 수 있는 표로 이루어져있어서 두 정점 사이에 관계가 있는지, 없는지 확인하기에 용이합니다.
가장 빠른 경로(shortest path)를 찾고자 할 때 주로 사용됩니다.
인접리스트
인접 리스트는 각 정점이 어떤 정점과 인접한지 리스트의 형태로 볼 수 있는 표현 방식
각 정점마다 하나의 리스트를 가지고 있으며, 이 리스트에는 자신과 인접한 다른 정점들이 담겨있다.
A->C->null
B->A->C->null
C->A->null인접 리스트는 인접 행렬은 연결 가능한 모든 경우의 수를 저장합니다.
서로 인접하지 않다면 0을, 인접하다면 1을 저장하기 때문에 메모리를 많이 차지하게 됩니다.
메모리를 효율적으로 사용하고 싶다면 인접 행렬 대신 인접 리스트를 사용합니다.
Tree
나무를 거꾸로 놓은 듯한 모습이며, 일방향 그래프이다.
가장 위의 F는 루트(Root)이며 최상단에 위치한다.
각각의 알파벳은 노드(Node)라고 하며, 만약 아래 쪽으로 가지를 내렸다면 기존의 노드는 부모가 되고 그 아래는 자식이 된다.
자식이 없는 노드는(H와 같은) 리프노드(leaf Node)라고도 부른다.
-> 파일 시스템과 같은 구현은 모두 트리를 이용해서 만듭니다.
BST
완전 이진 트리: 마지막 레벨을 제외한 모든 노드가 가득 차 있어야 하고, 마지막 레벨의 노드는 전부 차 있지 않아도 되지만 왼쪽이 채워져야 합니다.
포화 이진 트리: 정 이진 트리이면서 완전 이진 트리인 경우입니다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리입니다.
정 이진 트리: 각 노드가 0 개 혹은 2 개의 자식 노드를 갖습니다.
