그래프(Graph)

그래프는 정점과 정점을 연결하는 간선으로 모아놓은 자료구조이다. 여러개의 점들이 서로 복잡하게 연결되어 있는 구조이다.

컴퓨터 공학에서 말하는 자료구조 그래프는 거미줄처럼 어려개의 점들이 선으로 이어져 있는 네트워크 망과 같은 모습을 가지고 있다.

서로 다른 점들은 직접적인 관계를 가지고 있고 이어주는 선은 간접적인 관계를 가지고 있다.
그래프에서는 점을 정점(vertex), 선은 간선(edge)라고 한다.

그래프 특징

• 루트 노드가 없다.
• 양방향 경로를 가질 수 있다.
• self-loop를 가질 수 있다
• 순회는 DFS나 BFS로 할 수 있다.

그래프 실사용 예제

• 포털 사이트의 검색 엔진
• SNS
• 네이게이션(길찾기)

알아둬야 할 그래프 용어

• 무향그래프(undirected graph) / 유향그래프(directed graph)
  간선 방향이 없는 그래프를 말한다. 반대로 유향그래프(directed graph)는 간선의 방향이 정해져 있는 그래프이다.
  

• 진입차수(in-degree) / 진출차수(out-degree)
  한 정점에 진입(들어오는 간선)하고 진출(나가는 간선)하는 간선이 몇 개인지를 나타낸다.

• 인접(adjacency)
  두 정점간에 간선이 직접 이어져 있다면 두 정점은 인접한 정점이다.

• 자기 루프(self loop)
  정점에서 진출하는 간선이 곧바로 자기 자신에게 진입하는 경우 자기 루프를 가졌다 라고 한다.
  다른 정점을 거치지 않는 것이 특징이다.

• 사이클(cycle)
  한 정점에서 출발해 다시 해당 정점으로 돌아갈 수 있다면 사이클이 존재한다.
  내비게이션 예시에선 서울 —> 대전 —> 부산 —> 서울 로 이동이 가능하므로 사이클이 존재하는 그래프이다.

그래프(Graph) 표현 방식

1) 인접 행렬

인접 행렬은 2차원 배열의 형태이다.
정점끼리 이어져 있다면 1, 이어져 있지 않다면 0으로 표시된다.
만약 가중치 그래프라면 1 또는 0 대신 관계에서 의미있는 값(정점 간의 거리 등)을 저장한다.

• 장점
  1) 직관적이고, 구현이 쉽다.
• 단점
  1) 모든 경우의 수를 저장하므로 그래프의 크기가 커지면 메모리 초과가 발생 할 수 있다.
  2) 인접한 정점을 찾으려면 모든 정점을 순회해야한다.

무향 그래프는 대칭을 이루는 반면 유향 그래프는 대칭성이 없다.

위 왼쪽 무향 그래프를 예시로 들면,
A의 진출 차수는 2개이다. (A -> B와 A -> D)
[0][1] = 1, [0][3] = 1

C의 진출 차수는 1개이다.(C -> D)
[2][3] = 1

인접 행렬을 사용하기 좋을 때?

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

2) 인접 리스트

각 정점이 어떤 정점과 인접한지 리스트 형태로 볼 수 있는 방식이다.
각 정점마다 하나의 리스트를 갖고, 그 리스트에는 자신과 인접한 다른 정점들을 담고 있다.

• 장점
  1) 인접한 곳만 저장하므로 메모리를 효율적으로 사용한다.
  2) 정점의 인덱스 번호로 각 정점의 리스트에 쉽게 접근할 수 있다.

• 단점
  1) 인접행렬에 비해 다소 직관적이지 못하고 어렵다.

위 그림의 유향 그래프를 인접 리스트로 나타내면 아래와 같이 정점에서 갈 수 있는 곳만을 저장한다.

트리(Tree)

데이터가 바로 아래에 있는 하나 이상의 데이터에 단방향으로 연결되는 계층적 자료구조이다.

그래프의 구조 중 일방향 그래프의 한 구조로 하나의 뿌리로부터 가지가 사방으로 뻗은 형태를 띄고 있어 트리라고 한다.

• root: 하나의 꼭짓점 데이터로 여러 개의 데이터를 간선으로 연결한다.
• Parent Node / Child Node : 상위 노드와 하위 노드가 연결되면 부모/자식 관계를 갖는다.
• leaf Node : 자식이 없는 노드이다.
• Sibling : 같은 부모를 가지는 형제 노드이다.
  

특징

• 하나의 데이터에 단방향으로 연결되는 계층적 자료구조이다.
• 선형 구조가 아닌 비선형 구조이다.
• 아래로만 뻗기 때문에 사이클이 없다.
• 높이와 깊이를 잴 수 있다.

높이와 깊이 재기

• Level : 노드와 노드의 간격(거리)
  첫 번째 노드인 root를 Level1로 설정한다.

• Height : 루트로부터 가장 안쪽에 있는 노드까지의 레벨을 트리 높이라 한다.

• Depth : 특정 노트부터 시작해서 루트까지의 레벨을 노드의 깊이라 한다. 루트에서 특정 노드에 도달하기까지 거치는 간선의 수

• sub Tree : 큰 트리 내부에 트리 모양을 갖춪 트리를 말한다.
  

트리 실사용 예제

• 컴퓨터의 디렉토리 구조
• 월드컵 토너먼트 대진표
• 가계도, 조직도 등

그래프와 트리의 차이

참조 사이트
https://gmlwjd9405.github.io/2018/08/13/data-structure-graph.html
https://m.blog.naver.com/occidere/220923695595