Graph

노드와 노드를 연결하는 간선을 하나로 모아 놓은 자료구조
연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구조

• 네트워크 모델
• 루트 노드 개념이 없다.
• 부모-자식의 개념이 없다.

용어

• 정점(Vertex) : 하나의 객체를 표현(node)
• 간선(Edge) : 정점 간의 관계, 노드를 연결하는 선
• 차수(degree) : (무방향 그래프) 하나의 정점에 인접한 정점의 수
  • 진입 차수(in-degree) : (방향 그래프) 정점에 진입하는 간선의 수
  • 진출 차수(out-degree) : (방향 그래프) 정점에 진출하는 간선의 수
• 인접 정점(adjacent vertex) : 간선에 의해 직접 연결된 정점
• 자기 루프(self loop) : 정점에서 진출한 간선이 바로 자기 자신에게 진입하는 경우
• 사이클(cycle) : 한 정점에서 출발하여 다시 해당 정점으로 돌아가는 것

그래프 종류

• 무향 그래프(Undirected Graph) : 간선에 방향이 없는 그래프
• 유향 그래프(Directed Graph) : 간선에 방향이 존재하는 그래프
• 가중치 그래프(Weighted Graph) : 가중치를 갖는 간선으로 이루어진 그래프

그래프 구현

• 인접 리스트(Adjacency List) : 각 정점에 인접한 정점들을 연결리스트로 표현
• 인접 행렬(Adjacency Matrix) : 정점 간의 인접 관계를 나타내는 행렬

Tree

자료들 사이의 계층적 관계를 나타내는데 사용하는 자료구조로 부모-자식 관계로 표현

• 계층 모델
• 비순환 방향 그래프이다.
• 사이클/자기 루프 불가능
• 부모-자식 관계이다.

용어

• 루트 노드(root node) : 유일한 최상위 노드
• 내부 노드 (internal node) : 자식이 있는 노드
• 단말 노드(leaf node) : 자식이 없는 노드
• 깊이(Depth) : 루트 노드에서 해당 노드까지 도달하는데 사용하는 간선의 개수
• 레벨(Level) : 노드의 깊이 + 1
• 노드의 차수(degree) : 노드의 자식 수
• 트리의 차수(degree of tree): 트리의 최대 차수
• 높이(height) : 루트 노드에서 해당 노드까지 도달하는데 지나간 정점의 개수
  (가장 높은 노드의 높이가 트리의 높이)

Graph와 Tree의 차이?

	Graph	Tree
간선	둘 이상의 경로 허용(양반향, 단방향)	두 정점 사이에 하나만 존재(양방향)
루프/사이클	허용O	허용X
루트노드	X	하나의 루트 노드
모델 유형	네트워크 모델	계층 모델