[자료구조] 그래프와 트리
그루터기_산한
[자료구조] 그래프와 트리자료구조와 알고리즘2022. 4. 25. 15:57@그루터기_산한

그래프

인물 관계도, 먹이사슬, 지하철 노선도, 전국 도로망 등 일상 생활에서 연결 관계를 표현하거나 이해하는데 매우 많이 활용된다.

그래프의 구성 요소

⁃ 정점 (Node, Vertex)

그림에서 놀이기구에 해당한다.

⁃ 간선 (Edge)

놀이기구 사이의 경로에 해당한다.

 

그래프의 방향성

⁃ 방향 그래프 (Directed Graph)

⁃ 무방향 그래프 (Undirected Graph, 양방향 그래프)

 

 

 

방향성이 없다는 건 어느 쪽으로든 갈 수 있다는 의미.

 

 

 

 

그래프의 순환성

그래프 내 어떤 부분이라도 순환하는 부분이 있다면 순환 그래프, 한 군데도 없다면 비순환 그래프이다.

⁃ 순환 그래프 (Cyclic Graph)

⁃ 비순환 그래프 (ACyclic Graph)

 

 

그래프의 연결요소 (Connected Component)

이런 식으로 서로 완전히 분리된 요소들이 여럿 주어지는 그래프도 있다. 각각을 연결 요소라고 한다.
위 그림은 두 개의 연결 요소를 가진 그래프이다.

 

트리 (Tree)

 

그래프의 일종으로 순환성이 없는 무방향 그래프이다.
트리(tree) 구조는 나무를 뒤집은 모습으로 계층 구조를 표현하기에 적합하다.

 

 





 


수학적 개념상 그래프 이론에서의 트리는 무방향 그래프가 맞지만,

전산학에서 자료구조로 살용될 경우에는 계층이 있는 트리가 사용된다.

DAG (Directed Acyclic Graph).

 

 

트리의 특징

➤ 노드가 N개인 트리는 항상 N-1개의 간선(edge)를 가진다.  [노드개수 = 간선개수 + 1]

➤ 임의의 두 노드 간의 가는 경로는 유일하다. [두 개의 정점(node) 사이에는 반드시 1개의 경로(edge)만이 존재]

➤ 한 개의 루트 노드만이 존재하며, 모든 자식 노드는 한 개의 부모 노드만을 가진다.

➤ 순회는 Pre-order, In-order, Post-order로 이루어진다.

 

그래프와 트리의 차이

 

 

 

 

 

'자료구조와 알고리즘' 카테고리의 다른 글

[알고리즘] 너비 우선 탐색 (BFS, Breadth First Search)  (0) 2022.06.23
[알고리즘] 깊이 우선 탐색 (DFS, Depth First Search)  (0) 2022.06.18
[자료구조] 그래프를 코드로 나타내는 방법 (feat. C++)  (0) 2022.04.25
그루터기_산한
@그루터기_산한 :: Sanhan's Devlog

경영학 출신 개발자 Sanhan의 블로그 입니다. 개인적으로 공부한 내용이나, 모아두었던 글, 독서 내용 등을 틈틈이 정리하여 공유하려 합니다.

포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!

자료구조와 알고리즘 추천 글
more
image

티스토리툴바