그래프와 트리

그래프

노드와 노드 간을 연결하는 간선으로 구성된 자료 구조
이를 통해 노드 간의 관계를 표현할 수 있음

 

 

그래프 특징

• 순환 혹은 비순환 구조를 이룸
• 방향이 있는 그래프와 방향이 없는 그래프가 존재
• 루트 노드의 개념이 없음
• 부모-자식 관계라는 개념이 없음
• 2개 이상의 경로가 가능
• 네트워크 모델

 

 

그래프 역사

1800년대 오일러에 의하여 창안

• 오일러 문제
  • 모든 다리를 한번만 건너서 처음 출발했던 장소로 돌아오는 문제

 

 

그래프의 용어

그래프 G는 (V,E)로 표시

• 정점(vertices) : 여러가지 특성을 가질 수 있는 객체를 의미
  • V(G) : 그래프 G의 정점들의 집합
  • 노드라고도 함
• 간선(edge) : 정점들 간의 관계를 의미
  • E(G) : 그래프 G의 간선들의 집합
  • 링크라고도 함
• 인접 정점(adjacent vertex) : 간선에 직접 연결된 정점
• 차수(degree) : 한 정점에 연결된 간선의 수 (주로 무방향 그래프에서 사용)
• 입력 차수(in-degree) : 한 정점으로 들어오는 간선의 수 (주로 방향그래프에서 사용)
• 출력 차수(out-degree) : 한 정점에서 나가는 간선의 수(주로 방향그래프에서 사용)
• 사이클(cycle) : 한 정점에서 출발하여 시작했던 정점으로 돌아오는 경로
• 가중치 그래프 : 간선마다 가중치 값이 매겨져있는 그래프

 

 

트리

노드와 노드간을 연결하는 간선으로 구성된 자료구조
그래프 중에서도 특수한 경우에 해당하는 자료구조

 

 

트리의 특징

• 두 개의 노드 사이에 반드시 1개의 경로만을 가짐
• 사이클이 존재하지 않는 방향 그래프
• 부모-자식 관계가 존재해 레벨이 존재
• 노드가 N개이면 간선은 N-1개
• 방향성이 존재하고 사이클은 존재하지 않음

 

 

트리의 용어

• 루트 노드(root node) : 부모가 없는 노드, 트리는 하나의 루트 노드 만을 가짐
• 단말 노드(leaf node) : 자식이 없는 노드
• 간선(edge) : 노드를 연결하는 선
• 형제 노드(sibling) : 같은 부모를 가지는 노드
• 조상 노드(ancestors node) : 임의의 노드에서 루트 노드에 이르는 경로상에 있는 노드들
• 노드의 크기(size) : 자신을 포함한 모든 자손 노드의 개수
• 노드의 깊이(depth) : 루트에서 어떤 노드에 도달하기 위해 커쳐야하는 간선 수
• 노드의 레벨(level) : 트리의 특정 깊이를 가지는 노드의 집합
• 노드의 차수(degree) : 각 노드에서 뻗어나온 가지의 수
• 트리의 차수(degree of tree) : 트리에서 가장 큰 차수 
• 트리의 높이(height) : 가장 깊숙히 있는 노드의 깊이

 

 

그래프와 트리의 차이

	그래프	트리
방향성	방향, 무방향 모두 존재	방향만 존재
사이클	순환, 비순환, 자기순환	비순환
루트 노드	X	0
부모 - 자식 관계	X	1개의 부모노드
모델	네트워크 모델	계층 모델
순회	DFS, BFS	DFS, BFS의 전,중,후위 순회
간선의 수	자유	(총 노드의 수) - 1