그래프(Graph)

그래프는 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조다.

트리의 특성

• 위에 루트노드가 있고 아래로 자식노드가 있다.
• 노드를 연결하는 에지의 방향은 위 -> 아래이다.
• 트리는 그래프의 한 종류이다.
  👉 트리는 루트노드가 있고, 들어오는 곳이 한 곳이고, 싸이클이 없는, 아래로만 흐르는 방향(directed) 그래프이다.

그래프의 특성

방향성이 있는 directed graph, 방향성이 없는 그래프를 undirected graph라고 한다. 또한 자기 자신을 가리키는 self edge도 있다.
트리는 directed graph이지만 방향이 항상 위 -> 아래이기 때문에 화살표를 생략해 표현한다.

왼쪽 그림처럼 사이클이 있는 그래프를 cyclic graph, 오른쪽 처럼 사이클이 없는 그래프를 cyclic graph라고 한다.
트리는 acyclic graph에 해당한다.

그래프를 표현하는 방법

1) 인접 행렬(Adjacency Matrix)

왼쪽의 노드 4개로 구성된 방향성을 undirected graph를 인접 행렬로 나타내면 오른쪽 그림과 같다. 오른쪽 행렬의 각 인덱스는 노드를 의미하고, 노드가 직접적으로 인접한 에지가 있으면 1, 없으면 0을 적는다.

2) 인접 리스트(Adjacency List)

왼쪽의 노드 4개로 구성된 방향성을 undirected graph를 인접 리스트로 나타내면 오른쪽 그림과 같다. 리스트 안에 노드 인덱스를 적은 후, 노드와 연결이 있는 노드를 순서에 상관없이 오른쪽에 적는다.
👉 에지 m개가 존재하는 그래프를 인접 리스트로 표현하면 2m개의 노드가 존재한다.