Graph

컴퓨터 공학에서의 그래프는 복잡한 네트워크 망과 같은 모습이다.
여기서 A,B,C,D,E와 같은 점들을 정점(vertex), 선들은 간선(edge)라고 표현한다.

간선이 없다면 관계가 없다라고 표현하고 간선이 정점을 이어주기만 한다면 비가중치 그래프이고, 간선에 내용이 있다면 가중치 그래프라고 부른다.

실사용 예제로는 SNS(계정끼리의 팔로우,맞팔)와 네이게이션(길찾기) 등이 있다.

용어

무향그래프(undirected graph) : 양방향으로 가능한 그래프
단방향(directed) : 한방향으로만 가능한 간선
진입차수(in-degree) : 한 정점에 들어오는 간선의 갯수
진출차수(out-degree) : 한 정점에서 나가는 간선의 갯수
인접(adjacency) : 두 정점간에 간선이 직접 이어져 있다면 이 두 정점은 인접한 정점.
자기루프(self loop) : 정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우. 다른 정점을 거치지 않은다는 것이 특징.
사이클(cycle) : 한 정점에서 시작하여 다른 정점을 지나서 다시 해당 정점으로 돌아 올 수 있는 경우

인접 행렬

정점들간의 인접함을 표시해 주는 행렬으로 2차원 배열의 모습을 가지고 있다. 만약 A라는 정점과 B라는 정점이 이어져 있다면 1, 아니면 0으로 표시하는 일종의 표와 같다. 만약 가중치 그래프라면 1대신 다른 값을 저장한다.

• 장점 : 두 정점 사이의 관계가 있는지 확인하기에 용이하다.
  가장 빠른 경로를 찾고자 할 때 주로 사용된다.

인접 리스트

각 정점이 어떤 정점과 인접한지 리스트 형태로 볼 수 있는 표현 방식이다. 각 정점마다 하나의 리스트를 가지고 있고, 순서는 보통 중요하지 않다. 순위를 다뤄야한다면 queue,heap과 같은 자료구조를 사용하는 것이 합리적이다.

• 장점 : 서로 인접하지 않는 다면 0을 저장하지 않으므로 메모리 효율에서 좋다.

Tree구조

그래프의 한 종류이며, 하나 이상의 데이터에 단방향으로 연결되는 계층적 자료구조이다. 데이터를 순차적으로 나열시킨 형태가 아니므로 비선형 구조로 되어 있고, 아래로만 뻗기 때문에 사이클이 없다.

Tree구조는 Root라는 하나의 꼭짓점 데이터를 시작으로 여러개의 데이터를 간선으로 연결한다. 이 데이터들을 Node라고 하며, 부모 자식 관계를 가지게 된다. 자식이 있다면 자식 노드도 부모 노드가 될 수 있다. 자식이 없는 노드는 leaf Node라고 부른다.

밑으로 뻗어가는 구조이기 때문에 구조의 깊이를 측정 할 수 있다. 이 깊이를 레벨로 구분하며 depth라고 표현한다. 같은 레벨 즉, 같은 깊이의 Node는 sibling Node라고 표현한다.

실사용 예제로는 디렉토리가 있다.. 디렉토리 안에 또 여러개의 디렉토리가 있고 또 그 안에 디렉토리가 있는 트리 구조의 대표적인 예이다.